高度平衡的搜索二叉樹

一棵平衡樹，或是空樹，或是具有以下性質(zhì)的二叉搜索樹：左子樹和右子樹都是AVL樹，且左右子樹的高度之差的絕對值不超過1。 

該二叉樹，根結(jié)點的右子樹高度為3，左子樹高度為2。結(jié)點上方的數(shù)字為平衡因子，因為右子樹高度比左子樹高度大1，所以根結(jié)點的平衡因子為1。

一顆平衡二叉樹，如果有n個結(jié)點，其高度可保持O(log2^n),平均搜索長度也可以保持在O(log2^n)

平衡化旋轉(zhuǎn) 

AVL樹相較于普通的二叉搜索樹，自主要的就是做了平衡化處理，使得二叉樹變的平衡，高度降低。

在插入一個結(jié)點后應該沿搜索路徑將路徑上的結(jié)點平衡因子進行修改，當平衡因子大于1時，就需要進行平衡化處理。從發(fā)生不平衡的結(jié)點起，沿剛才回溯的路徑取直接下兩層的結(jié)點，如果這三個結(jié)點在一條直線上，則采用單旋轉(zhuǎn)進行平衡化，如果這三個結(jié)點位于一條折線上，則采用雙旋轉(zhuǎn)進行平衡化。

單旋轉(zhuǎn)

左單旋

動圖演示，圖片內(nèi)容可以無視，看懂操作進行了

將右子樹的左子樹鏈接到父親節(jié)點的右孩子結(jié)點，父親節(jié)點作為ptr結(jié)點的左孩子結(jié)點便完成了旋轉(zhuǎn)

右單旋

右單旋是左單旋的鏡像旋轉(zhuǎn). 

當前節(jié)點ptr，與父親節(jié)點和當前節(jié)點的左孩子結(jié)點位于一條直線上時，使用右單旋進行平衡。

雙旋轉(zhuǎn)

先左后右雙旋轉(zhuǎn)

當在ptr的左子樹的右子樹中插入一個結(jié)點后，造成了ptr平衡因子為-2的不平衡，將ptr向下找到當前結(jié)點的左孩子的右孩子，先進行左單旋ptr->left = subL，然后將ptr的右子樹斷開指向subR，此時便完成了旋轉(zhuǎn)，最后將平衡因子進行更新。

先右后左雙旋轉(zhuǎn)

先右單旋再左單旋，是先左后右的鏡像旋轉(zhuǎn)，這里就不做贅述了。

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接

最新評論