平衡二叉樹的生成過程(已修改)
2025-04-21 11:42 本頁面
【正文】 二叉排序樹變成平衡二叉樹對于二叉查找樹，盡管查找、插入及刪除操作的平均運行時間為O(logn)，但是它們的最差運行時間都是O(n),原因在于對樹的形狀沒有限制。平衡二叉樹又稱為AVL樹，它或者是一棵空樹，或者是有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左右子樹的深度之差的絕對值不超過1。二叉樹的的平衡因子BF為：該結(jié)點的左子樹的深度減去它的右子樹的深度，則平衡二叉樹的所有結(jié)點的平衡因子為只可能是：0和1一棵好的平衡二叉樹的特征：（1）保證有n個結(jié)點的樹的高度為O(logn)（2）容易維護(hù)，也就是說，在做數(shù)據(jù)項的插入或刪除操作時，為平衡樹所做的一些輔助操作時間開銷為O(1)一、平衡二叉樹的構(gòu)造在一棵二叉查找樹中插入結(jié)點后，調(diào)整其為平衡二叉樹。若向平衡二叉樹中插入一個新結(jié)點后破壞了平衡二叉樹的平衡性。首先要找出插入新結(jié)點后失去平衡的最小子樹根結(jié)點的指針。然后再調(diào)整這個子樹中有關(guān)結(jié)點之間的鏈接關(guān)系，使之成為新的平衡子樹。當(dāng)失去平衡的最小子樹被調(diào)整為平衡子樹后，原有其他所有不平衡子樹無需調(diào)整，整個二叉排序樹就又成為一棵平衡二叉樹（1）插入點位置必須滿足二叉查找樹的性質(zhì)，即任意一棵子樹的左結(jié)點都小于根結(jié)點，右結(jié)點大于根結(jié)點（2）找出插入結(jié)點后不平衡的最小二叉樹進(jìn)行調(diào)整，如果是整個樹不平衡，才進(jìn)行整個樹的調(diào)整。（1）LL型LL型：插入位置為左子樹的左結(jié)點，進(jìn)行向右旋轉(zhuǎn)(LL表示的是在做子樹的左結(jié)點進(jìn)行插入)由于在A的左孩子B的左子樹上插入結(jié)點F，使A的平衡因子由1變?yōu)?，成為不平衡的最小二叉樹根結(jié)點。此時A結(jié)點順時針右旋轉(zhuǎn)，旋轉(zhuǎn)過程中遵循“旋轉(zhuǎn)優(yōu)先”的規(guī)則，A結(jié)點替換D結(jié)點成為B結(jié)點的右子樹，D結(jié)點成為A結(jié)點的左孩子。（2）RR型RR型：插入位置為右子樹的右孩子，進(jìn)行向左旋轉(zhuǎn)由于在A的右子樹C的右子樹插入了結(jié)點F，A的平衡因子由1變?yōu)?，成為不平衡的最小二叉樹根結(jié)點。此時，A結(jié)點逆時針左旋轉(zhuǎn)，遵循“旋轉(zhuǎn)優(yōu)先”的規(guī)則，A結(jié)點替換D結(jié)點成為C的左子樹，D結(jié)點成為A的右子樹。（3）LR型LR型：插入位置為左子樹的右孩子，要進(jìn)行兩次旋轉(zhuǎn)，先左旋轉(zhuǎn)，再右旋轉(zhuǎn)；第一次最小不平衡子樹的根結(jié)點先不動，調(diào)整插入結(jié)點所在的子樹，調(diào)整后的樹變成LL型樹，第二次再調(diào)整最小不平衡子樹(根據(jù)LL型的調(diào)整規(guī)則，調(diào)整為平衡二叉樹)。由于在A的左子樹B的右子樹上插入了結(jié)點F，A的平衡因子由1變?yōu)榱?，成為不平衡的最小二叉樹根結(jié)點。第一次旋轉(zhuǎn)A結(jié)點不動，先將B的右子樹的根結(jié)點D向左上旋轉(zhuǎn)提升到B結(jié)點的位置，然后再把該D結(jié)點向右上旋轉(zhuǎn)提升到A結(jié)點的位置。（4）RL型RL型：插入位置為右子樹的左孩子，進(jìn)行兩次調(diào)整，先右旋轉(zhuǎn)調(diào)整為RR型，再左旋轉(zhuǎn)，從RR型調(diào)整到平衡二叉樹；處理情況與LR類似。總結(jié)：RR型和LL型插入導(dǎo)致的樹失去平衡，只需要做一次旋轉(zhuǎn)調(diào)整即可。而RL型和LR型插入導(dǎo)致的結(jié)點失去平衡，要調(diào)整兩次。對于RL/LR的
公司管理相關(guān)推薦
鄂ICP備17016276號-1