二叉查找樹描述
二叉查找樹的性質:對於樹中的每個結點X,它的左子樹中所有關鍵字值小於X的關鍵值,而它的右子樹中所有關鍵字大於X的關鍵值。由於樹的遞歸定義,通常是遞歸的編寫查找樹的常用操作例程。對這些常用例程中,主要需要考慮的是插入和刪除節點。下面將簡要說明。(二叉查找樹的平均深度是O(logN),所以一般不需要擔心棧空間用盡。)
Insert:為了將X插入到樹T中,可以像用Find那樣沿著樹查找。如果找到X,則什麼也不用做。否則,將X插入到遍歷的路徑上的最後一點上。如下圖所示,為了插入5,因而遍歷該樹,就好像在運行Find。在具有關鍵字4的節點處需要向右行進,但4的右子樹不存在,因此5不在這棵樹上,從而這個位置就是所要插入的位置。
Delete:一旦發現要刪除的節點,考慮以下三種情況:如果該節點是一片樹葉,那麼它可以被立即刪除;如果節點只有一個兒子,則該節點可以在其父節點調整指針繞過該節點後被刪除,如下圖:刪除只有一個左孩子節點的元素:4。
復雜的情況是處理具有兩個兒子的節點。一般的刪除策略是用其右子樹關鍵字最小的元素或左子樹關鍵字最大的元素代替該節點的數據並遞歸的刪除那個節點。因為右子樹中最小節點不可能有左孩子(左子樹的最大值節點則不可能有右孩子),所以第二次Delete變要容易一些。下圖是一顆初始的二叉查找樹即刪除關鍵字為2的節點後的狀態。