在講到集合的時候，很容易讓人想到的是數(shù)組和鏈表孟岛。然后大家會討論這兩種數(shù)據(jù)結(jié)構(gòu)的差異似将。但是根據(jù)指定的內(nèi)容在集合中查找，這兩種數(shù)據(jù)結(jié)構(gòu)的性能卻沒有區(qū)別都是O(n)蚀苛，如何提高在集合中檢索指定內(nèi)容數(shù)據(jù)的性能在验，是我們在程序開發(fā)中面臨的問題。

二叉排序樹

二叉排序樹的性質(zhì)

1. 左子樹不空時堵未，左子樹上所有的結(jié)點(diǎn)關(guān)鍵字的值均小于根結(jié)點(diǎn)關(guān)鍵字的值腋舌；
2. 右子樹不空時，右子樹上所有的結(jié)點(diǎn)關(guān)鍵字的值均大于根結(jié)點(diǎn)關(guān)鍵字的值渗蟹；
3. 左右子樹同時有滿足性質(zhì)1块饺、性質(zhì)2

二叉樹的查找

1. 將給定的值與根結(jié)點(diǎn)相比較，若相等則查找成功雌芽；
2. 若小于根結(jié)點(diǎn)到左子樹進(jìn)行查找授艰，若大于根結(jié)點(diǎn)到右子樹進(jìn)行查找；
3. 左右子樹依次進(jìn)行步驟1世落、步驟2操作淮腾，直到找到相等的結(jié)點(diǎn)或找到null(查找失敗)
4. 二叉樹的查找與折半查找相似

二叉樹的操作

插入

BSTInsert.png

1. 從一個空樹出發(fā)來構(gòu)建二叉排序樹屉佳，新增結(jié)點(diǎn)是建立在查找二叉排序樹失敗的前提下谷朝，因此新增的結(jié)點(diǎn)一定是二叉排序樹的葉子結(jié)點(diǎn)
2. 中序遍歷二叉排序樹即可得到一個有序的集合

刪除

二叉排序樹的刪除規(guī)則：設(shè)，
*f為指向被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)的指針
*p為指向被刪除結(jié)點(diǎn)的指針

1. 若*p是葉子結(jié)點(diǎn)武花，那么就直接刪除

   • *p是*f的左子結(jié)點(diǎn)圆凰，如圖所示：
     *p左葉子節(jié)點(diǎn)
   • *p是*f的右子結(jié)點(diǎn)，如圖所示：
     
     *p節(jié)點(diǎn)是右葉子節(jié)點(diǎn)
2. 若刪除的*p結(jié)點(diǎn)只有左子樹或是右子樹体箕，刪除*p結(jié)點(diǎn)之后直接將子樹掛在*f結(jié)點(diǎn)上即可专钉，成為*f結(jié)點(diǎn)的子樹

   • *p是*f的左子結(jié)點(diǎn)挑童，如圖所示：
     *p節(jié)點(diǎn)有右子節(jié)點(diǎn)

   • *p是*f的右子結(jié)點(diǎn)，如圖所示：
     *p節(jié)點(diǎn)有左孩子節(jié)點(diǎn)
   • 說明：上述只是部分情況跃须，剩余情況最后都跟上圖顯示的刪除*p結(jié)點(diǎn)之后的結(jié)點(diǎn)情況一致炮沐。
3. 若刪除的*p結(jié)點(diǎn)同時擁有左、右子樹回怜，刪除節(jié)點(diǎn)有兩種可行性操作：
   • 若*p結(jié)點(diǎn)是*f的左子結(jié)點(diǎn)

     • 第一種操作：將*p點(diǎn)的左子樹PL直接掛載到*f結(jié)點(diǎn)上大年，成為*f結(jié)點(diǎn)的左子樹，然后將*p結(jié)點(diǎn)的右子樹PR掛載到中序遍歷時PL子樹中*p結(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)玉雾，成為該節(jié)點(diǎn)的右子樹翔试；如圖所示：
       *p節(jié)點(diǎn)是*f的左孩子且同時擁有左右子樹
     • 第二種操作：使用二叉排序樹的中序遍歷得到的結(jié)點(diǎn)順序，確定*p結(jié)點(diǎn)的直接前驅(qū)或直接后繼結(jié)點(diǎn)复旬，將該結(jié)點(diǎn)移到*p結(jié)點(diǎn)位置
       • 該結(jié)點(diǎn)滿足以下特性：
         1. 該結(jié)點(diǎn)是葉子結(jié)點(diǎn)或只有一個子樹(若是前驅(qū)節(jié)點(diǎn)只有左子樹垦缅；若是后繼節(jié)點(diǎn)只有右子樹)
         2. 該結(jié)點(diǎn)是*p前驅(qū)結(jié)點(diǎn)的話，就是該前驅(qū)結(jié)點(diǎn)父節(jié)點(diǎn)的右子結(jié)點(diǎn)驹碍；
         3. 該結(jié)點(diǎn)是*p后繼結(jié)點(diǎn)的話壁涎，就是該后繼結(jié)點(diǎn)父節(jié)點(diǎn)的左子結(jié)點(diǎn)。
       • 接下來以*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)進(jìn)行討論：
         • 若*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)是葉子結(jié)點(diǎn)則直接移動即可志秃，圖就略過了怔球。

         • 若*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)有左子樹的話，則將左子樹掛載到*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的父結(jié)點(diǎn)上浮还，成為*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的父結(jié)點(diǎn)的右子樹竟坛，如圖所示：
           *p節(jié)點(diǎn)是*f的左孩子且同時擁有左右子樹
       • 接下來以*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)進(jìn)行討論：
         • 若*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)是葉子結(jié)點(diǎn)則直接移動即可，圖(略)

         • 若*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)有右子樹的話钧舌，則將右子樹掛載到*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)的父結(jié)點(diǎn)上担汤，成為*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)的父結(jié)點(diǎn)的左子樹，如圖所示：
           *p節(jié)點(diǎn)是*f節(jié)點(diǎn)的左子樹同時擁有左右子樹
       • 上述是在*p是*f的左孩子的前提下進(jìn)行的討論洼冻，接下來是以*p是*f的右孩子進(jìn)行討論崭歧，直接上圖了

         • 第一種操作：
           *p節(jié)點(diǎn)是*f節(jié)點(diǎn)的右孩子同時擁有左右子節(jié)點(diǎn)
         • 第二種轉(zhuǎn)換：
           • 以*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)進(jìn)行討論
             
             *p節(jié)點(diǎn)是*f節(jié)點(diǎn)右孩子同時擁有左右子節(jié)點(diǎn)
           • 以*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)進(jìn)行討論
             *p節(jié)點(diǎn)是*f節(jié)點(diǎn)右孩子同時擁有左右子節(jié)點(diǎn)