高度平衡的搜索二叉樹

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

該二叉樹，根結(jié)點(diǎn)的右子樹高度為3，左子樹高度為2。結(jié)點(diǎn)上方的數(shù)字為平衡因子，因?yàn)橛易訕涓叨缺茸笞訕涓叨却?，所以根結(jié)點(diǎn)的平衡因子為1。

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

平衡化旋轉(zhuǎn) 

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

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

單旋轉(zhuǎn)

左單旋

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

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

右單旋

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

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

雙旋轉(zhuǎn)

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

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

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

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

總結(jié)

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

最新評論