講了二元樹的走訪,接下來要進入搜尋了,尋找森林深處的密寶~
先來說說 二元搜尋樹 (Binary Search Tree),又稱 有序二元樹 或 排序二元樹。如若不是空樹,則有以下幾個特點:
簡單來說就是,任一個節點的左子樹都比父節點小,右子樹都比父節點大,且每一個節點的值都不重複。所以當我們要查找資料的時候,就可以從根節點開始,比根節點小的就從左子樹開始找,比較大的就從右子樹開始找。相對於其他資料結構而言,尋找、插入的時間複雜度較低,為O(logN)。
那有關節點的插入呢?和搜尋很像,從根節點開始比大小,比較小的往左子樹走,比較大的往右子樹走,一樣的則返回,直到插入為止。這邊就不多做解釋。
而刪除節點的話就比較複雜了。刪除的節點要從右子樹中找到對大的值來接替。
假設我們要刪除節點 6,就要找節點 5 來替換。如果找 2 的話,那 3~5 都比二大,卻在 2 的左子樹中,於定義相左。因此我們要找 6 的右子樹中,最大的節點來接替。