高度平衡的搜索二叉樹(shù)

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

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

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

平衡化旋轉(zhuǎn) 

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

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

單旋轉(zhuǎn)

左單旋

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

將右子樹(shù)的左子樹(shù)鏈接到父親節(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)位于一條直線上時(shí)，使用右單旋進(jìn)行平衡。

雙旋轉(zhuǎn)

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

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

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

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

總結(jié)

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

最新評(píng)論