二叉搜索樹，也稱二叉排序樹或二叉查找樹
(資料圖片僅供參考)
二叉搜索樹：一棵二叉樹，可以為空，如果不為空，應(yīng)該滿足以下性質(zhì)：
非空左子樹的所有結(jié)點小于其根結(jié)點的鍵值非空右子樹的所有結(jié)點大于其根結(jié)點的鍵值左右子樹都是二叉搜索樹對于二叉樹的查找，其實沿用的是分治法的思想，所以我們的樹一定是要排序好的，這樣才能使用每次檢索都少一半的數(shù)據(jù)量
我們可以看到上面的二叉樹，它滿足根結(jié)點的左邊都比根結(jié)點小，而右邊又都比根結(jié)點大，所以它就是可以使用二叉樹查找的
當我們要查找6時
首先，我們對根節(jié)點進行比較，發(fā)現(xiàn)6是大于5的所以，我們需要去根結(jié)點的右邊也就是結(jié)點8
然后，結(jié)點8進行對比，發(fā)現(xiàn)它比結(jié)點8小，所以去結(jié)點的額左邊也就是結(jié)點6
最后，結(jié)點6和查找鍵值6是一樣的，所以找到了
以下是代碼實現(xiàn)：Position Find(ElementType x, BinTree BST) { if (!BST) { return NULL; } if (x > BST->Data) { return Find(x, BST->Right); } else if (xData){ return Find(x, BST->Left); } else{ return BST; }} 我們可以發(fā)現(xiàn)，使用遞歸實現(xiàn)的代碼查找，其實是尾遞歸，對于尾遞歸，我們可以直接使用循環(huán)來做
利用循環(huán)的代碼實現(xiàn)：//將尾遞歸轉(zhuǎn)換為循環(huán)，效率高Position IterFind(ElementType x, BinTree BST) { while (BST) { if (x > BST->Data) { BST = BST->Right; } else if(xData){ BST = BST->Left; } else return BST; } return NULL;} 二叉樹的插入插入結(jié)點的關(guān)鍵在于要找到結(jié)點的位置，我們可以使用查找函數(shù)的思維，找到它的位置，然后再對應(yīng)插入
上面的圖片，我們要插入元素7到樹中去，
首先，元素7是大于根節(jié)點5的，所以元素7應(yīng)該處于根結(jié)點的右邊位置，就和結(jié)點8進行比較
然后，發(fā)現(xiàn)結(jié)點8是大于元素7的，所以我們元素7因該在結(jié)點8的左邊，也就是到了結(jié)點6的位置，
最后，結(jié)點6左右無元素，且元素7大于結(jié)點6，所以元素7位于結(jié)點6的右子結(jié)點
然后是代碼實現(xiàn)：BinTree Insert(ElementType x, BinTree BST) { if (!BST) { BST = malloc(sizeof(struct TreeNode)); BST->Data = x; BST->Left = BST->Right = NULL; } else { if (x < BST->Data) { BST = Insert(x, BST->Left); } else if (x>BST->Data) { BST = Insert(x, BST->Right); } return BST; }}二叉樹的刪除刪除的情況要復(fù)雜一些，因為我們的樹分有子結(jié)點和無子結(jié)點，當然無子結(jié)點的肯定是很好刪除的，主要是有子結(jié)點的怎么刪除呢？
這就需要我們分情況討論：
無子結(jié)點時：直接刪除需要刪除的結(jié)點，并修改其父結(jié)點的指針，置為NULL
如上圖，
當我們要刪除結(jié)點4的時候，結(jié)點4自己是沒有子結(jié)點的，
所以我們可以直接釋放結(jié)點4，并且把結(jié)點3的右結(jié)點指針指向NULL
當有一個子結(jié)點的時候：需要把要刪除的結(jié)點的父結(jié)點指針，指向它的孩子結(jié)點，相當于中間少了一層
如上圖，
我們要刪除結(jié)點3的時候，發(fā)現(xiàn)它是有一個結(jié)點4的，我們就不能直接把結(jié)點3刪除了
而是要先把結(jié)點5的指向結(jié)點3的指針指向結(jié)點4
然后再釋放結(jié)點3
當有兩個子節(jié)點的時候：這種情況使用的方法是，要么使用左子樹的最大元素頂上去，要么使用右子樹的最小元素頂上去
這里需要刪除的結(jié)點是8，
我們可以在左子樹中去找到最大的元素，然后替換到結(jié)點8的值，然后刪除結(jié)點7就可以了
還可以去右子樹中找到最小的元素，然后替換掉結(jié)點8為最小結(jié)點的值，然后刪除最小結(jié)點
注意：
刪除結(jié)點時需要改變父結(jié)點指針指向為NULL
當刪除的結(jié)點后面還有結(jié)點時，要一個一個的連接到前面來
然后就是代碼實現(xiàn)：// 查找最小結(jié)點Position FindMin(BinTree BST) { if (!BST) return NULL; else if (!BST->Left) return BST; else { return FindMin(BST->Left); }}//刪除結(jié)點BinTree Delete(ElementType x, BinTree BST) { Position Temp; if (!BST) printf("要刪除的元素未找到！"); else if (x < BST->Data) { BST->Left = Delete(x, BST->Left); //在左子樹查找要刪除的元素 } else if (x > BST->Data) { BST->Right = Delete(x, BST->Right); //在右子樹查找要刪除的元素 } else //找到要刪除的結(jié)點 { if (BST->Left && BST->Right){ //左右都有結(jié)點 Temp = FindMin(BST->Right); //找右子樹的最小元素 BST->Data = Temp->Data; //把右子樹最小元素覆蓋到要刪除的元素上 BST->Right = Delete(BST->Data, BST->Right); //刪除右子樹的最小元素 } else {// 只有一個結(jié)點的情況，或沒有結(jié)點的情況 Temp = BST; if (!BST->Left) { //右結(jié)點存在，或沒有結(jié)點存在 BST = BST->Right; } else if (!BST->Right) { //左結(jié)點存在，或沒有結(jié)點存在 BST = BST->Left; } free(Temp); } } return BST;}二.進階之平衡二叉樹（AVL樹）什么是平衡二叉樹？
平衡二叉樹（AVL樹）：空樹，或者任一結(jié)點左，右子樹的高度差絕對值不超過1，即| BF（T）<=1 |
平衡因子：BF(T)= hL- hR ，其中hL，hR是T的左子樹高度和右子樹高度
我們可以來看幾個圖分別一下是不是平衡二叉樹：
上圖，對于結(jié)點5來說，左子樹高度2，右子樹高度3
3 - 2 = 1 滿足 | BF（T）<= 1 |
但是對于右子樹的結(jié)點8來說，它的左子樹高度是2，右子樹高度為0
2-0 = 2就不滿足| BF（T）<=1 |
所以這不是一棵平衡二叉樹
對于這顆樹來說，
結(jié)點5 的左子樹高度是2，右子樹高度是 3，滿足最小高度為小于等于 1
結(jié)點8 的左子樹高度是2，右子樹高度是1，滿足最小高度為小于等于 1
所以它是一棵平衡的二叉樹
平衡二叉樹的調(diào)整平衡二叉樹在建樹的時候其實是平衡的，主要是在后期的插入和刪除中，會破壞掉它的平衡，最常見的就是插入就破壞了平衡，即| BF（T）>1 | ，它就不滿足平衡二叉樹了
所以我們在插入的時候，會有一個二叉樹的平衡調(diào)整的過程
RR旋轉(zhuǎn)（右單旋轉(zhuǎn)）------RR旋轉(zhuǎn)指的就是，破壞發(fā)生在右子樹的右子樹，
解決方式就是把被破環(huán)的結(jié)點，也就是結(jié)點7的右子樹作為它們的父結(jié)點，相當于把結(jié)點7提起來做父結(jié)點
由于我們的平衡二叉樹在調(diào)整的時候也需要注意滿足查找二叉樹的準則，所以對被提起來的結(jié)點，它左邊的結(jié)點需要掛到它父結(jié)點的左邊
也就是說，把結(jié)點8做父結(jié)點提起來的時候，結(jié)點8的左子樹要掛在結(jié)點7的右邊
LL旋轉(zhuǎn)（左單旋轉(zhuǎn)）------LL旋轉(zhuǎn)指的是，破壞發(fā)生在左子樹的左子樹
解決方式就是把被破壞的結(jié)點的子結(jié)點，提起來當作父結(jié)點，而原來的父結(jié)點當作子結(jié)點
也就是結(jié)點8被當作父結(jié)點，而原來的結(jié)點7被落下去當子結(jié)點了
由于平衡二叉樹在被調(diào)整以后依然要滿足查找二叉樹的準則，所以我們需要把被提起來的結(jié)點的右子樹，放在落下去結(jié)點的左子樹
也就是，原來結(jié)點8的右子樹要放在現(xiàn)在結(jié)點9的左子樹（存在的情況下）
LR旋轉(zhuǎn) ----------LR旋轉(zhuǎn)指的是，破壞發(fā)生在左子樹的右子樹上
解決方式就是發(fā)生把發(fā)生破壞的結(jié)點提起來左父結(jié)點，而原來的左子樹結(jié)點繼續(xù)做左子樹結(jié)點，原來的父結(jié)點做右結(jié)點
注意這時的波壞結(jié)點可能是插入了結(jié)點的，如果它插入在左邊，那么他就是原來左子樹結(jié)點的右子樹，如果它插在破壞結(jié)點的右邊，那么它就應(yīng)該在原父結(jié)點的左邊
也就是，在結(jié)點8，結(jié)點5，結(jié)點7中，結(jié)點7要被提起來做父結(jié)點，結(jié)點5繼續(xù)做它的左子樹結(jié)點，而原來的父結(jié)點8做新父結(jié)點的右子樹
對于新插入的元素6，由于它是插入在結(jié)點7的左邊，所以它是結(jié)點5的右子樹，當然他要是插在了結(jié)點7的右邊，那么它就是結(jié)點8的左子樹
解釋如下：
RL旋轉(zhuǎn) ---------RL旋轉(zhuǎn)指的就是，破壞在右子樹的左子樹
解決方式就是把破壞結(jié)點提起來做父結(jié)點，原來的父結(jié)點做新父結(jié)點的左子樹，而原來的右子樹還是新父結(jié)點的右子樹
由于我們平衡二叉樹調(diào)整后還要滿足查找二叉樹，所以對于插入破壞結(jié)點左邊的數(shù)要在新的左子樹的右邊，而插入到破壞結(jié)點右邊的數(shù)要在新的右子樹的左邊
也就是，把結(jié)點6提起來做新的父結(jié)點，原父結(jié)點3做結(jié)點6的左子樹，而右結(jié)點則還是結(jié)點7，
對于原來插入到結(jié)點6左邊的數(shù)要在新的左子樹3的右邊，而插入在結(jié)點6的右邊的，要在新的右子樹的左邊
解釋如下：
三.樹的應(yīng)用對于一棵二叉樹來說，它可以有多個輸入序列，但是，構(gòu)成的可能是同一棵二叉樹，那么我們怎么根據(jù)輸入序列來判斷是不是同一棵二叉樹呢？
不建樹的判別方法：如 ：
3，1，2，4
vs
3，4，1，2
由于第一個元素肯定是根結(jié)點，所以根結(jié)點就是3，并且比根結(jié)點小的在左邊，比它大的在右邊
所以被分成了
{1，2} ，3，{4}
{1，2} ，3，{4}
我們可以看到它們此時的序列是完全一樣的，所以可以構(gòu)成一棵二叉樹
在如：
3，1，2，4
vs
3，2，4，1
一樣的方法劃分，3為根結(jié)點
{1，2}，3，{4}
{2，1}，3，{4}
對于左邊來說，第一個元素是下一層的根結(jié)點，
所以一個是1為父結(jié)點，一個是2為父結(jié)點，顯然不是同一顆二叉樹
建一棵二叉樹，其它序列來依次對比：typedef struct TreeNo* Tree;struct TreeNo{ int v; Tree Left, Right; int flag;};這是我們需要使用到的結(jié)構(gòu)
我們對于多個輸入序列，只會構(gòu)建一棵二叉樹，然后就是讓序列 對已經(jīng)構(gòu)建好的二叉樹進行遍歷，其中flag有重要的作用
這種方法來判定二叉樹是否同構(gòu)的思想是，
我們已經(jīng)構(gòu)建好了一棵二叉樹，然后只需要對輸入序列依次訪問，
如果被訪問的結(jié)點flag為0，那么就給flag賦值為1，
如果不是被訪問結(jié)點，但是訪問過了也就是flag為1，那么可以向下尋找，
如果不是被訪問的結(jié)點，但是flag也不為1，那么則表示不同構(gòu)
原因是，它們兩個結(jié)點的構(gòu)建的位置不一樣，可以看上面的圖片，輸入序列要先構(gòu)建3為父結(jié)點，而已構(gòu)建的二叉樹則使用結(jié)點5作為父結(jié)點，說以兩個二叉樹不同構(gòu)
四.紅黑樹--拓展紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實現(xiàn)關(guān)聯(lián)數(shù)組
紅黑樹的特性：
根結(jié)點是黑色的葉子結(jié)點（null值）黑結(jié)點紅結(jié)點的子結(jié)點必須是黑結(jié)點新插入的結(jié)點是紅色的結(jié)點父結(jié)點到任一葉子結(jié)點黑結(jié)點數(shù)相同紅黑樹也是一種自平衡的二叉樹，但是它比二叉平衡樹的條件更加寬泛，
二叉平衡樹所要求的平衡是左子樹和右子樹的高度相差小于等于1
而紅黑樹的要求是父結(jié)點到葉子結(jié)點的黑節(jié)點數(shù)相同就可以了，這個條件其實是很寬泛的了，我們可以找出它的一種極端情況，那么就是左子樹都是黑色，而右子樹黑紅交叉，
這種情況構(gòu)建的紅黑樹，它右半邊的結(jié)點數(shù)其實是左邊的2n-1
假如有一顆這樣的樹，其實不存在，因為很多右子樹，左子樹都沒數(shù)據(jù)，是構(gòu)成不了紅黑樹的，
我們看到它左邊的長度是3，而右邊則是6，很顯然比左邊多出了一倍，那么還能叫自平衡樹嗎？
這就是紅黑樹的平衡，我們可以把紅結(jié)點都去掉，發(fā)現(xiàn)黑節(jié)點其實是平衡的，更重要的是，就算加上紅結(jié)點，其實上面的查找的時間復(fù)雜度也是O(2 * log2n)
由于我們的常量是不用記錄到時間復(fù)雜度的，所以依舊是 log2n
所以紅黑樹給出的平衡指的是：左子樹和右子樹的結(jié)點相等或相差一倍，都是可以的
為什么紅黑樹這樣定義平衡呢？
我們可以直到AVL二叉樹它的平衡過于嚴格，所以每次插入都可能有很大的變化，大多數(shù)插入的時間都花在了維持那嚴格的平衡上了
而寬泛的紅黑樹，則變動更少，它的平均性能又很高，它能保證很高的性能，而又插入不會頻繁的發(fā)生變更，所以紅黑樹就使用自己定義的那套平衡機制
紅黑樹的構(gòu)造過程：上面的圖片就是紅黑樹的構(gòu)造規(guī)則，我們可以簡單的來實現(xiàn)一下：
--
--
--
標簽：
參與評論