平衡二叉樹的生成過程-wenkub
2023-04-24 11:42:36 本頁面
【正文】 樹是指最小不平衡結(jié)點(diǎn)的一顆子樹，且這棵子樹是插入結(jié)點(diǎn)的子樹)為RR型或者LL型，第二次再調(diào)整最小不平衡子樹(調(diào)整策略要么是RR型要么是LL型)。第一次旋轉(zhuǎn)A結(jié)點(diǎn)不動，先將B的右子樹的根結(jié)點(diǎn)D向左上旋轉(zhuǎn)提升到B結(jié)點(diǎn)的位置，然后再把該D結(jié)點(diǎn)向右上旋轉(zhuǎn)提升到A結(jié)點(diǎn)的位置。（2）RR型RR型：插入位置為右子樹的右孩子，進(jìn)行向左旋轉(zhuǎn)由于在A的右子樹C的右子樹插入了結(jié)點(diǎn)F，A的平衡因子由1變?yōu)?，成為不平衡的最小二叉樹根結(jié)點(diǎn)。然后再調(diào)整這個子樹中有關(guān)結(jié)點(diǎn)之間的鏈接關(guān)系，使之成為新的平衡子樹。平衡二叉樹又稱為AVL樹，它或者是一棵空樹，或者是有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左右子樹的深度之差的絕對值不超過1。二叉樹的的平衡因子BF為：該結(jié)點(diǎn)的左子樹的深度減去它的右子樹的深度，則平衡二叉樹的所有結(jié)點(diǎn)的平衡因子為只可能是：0和1一棵好的平衡二叉樹的特征：（1）保證有n個結(jié)點(diǎn)的樹的高度為O(logn)（2）容易維護(hù)，也就是說，在做數(shù)據(jù)項(xiàng)的插入或刪除操作時，為平衡樹所做的一些輔助操作時間開銷為O(1)一、平衡二叉樹的構(gòu)造在一棵二叉查找樹中插入結(jié)點(diǎn)后，調(diào)整其為平衡二叉樹。當(dāng)失去平衡的最小子樹被調(diào)整為平衡子樹后，原有其他所有不平衡子樹無需調(diào)整，整個二叉排序樹就又成為一棵平衡二叉樹（1）插入點(diǎn)位置必須滿足二叉查找樹的性質(zhì)，即任意一棵子樹的左結(jié)點(diǎn)都小于根結(jié)點(diǎn)，右結(jié)點(diǎn)大于根結(jié)點(diǎn)（2）找出插入結(jié)點(diǎn)后不平衡的最小二叉樹進(jìn)行調(diào)整，如果是整個樹不平衡，才進(jìn)行整個樹的調(diào)整。此時，A結(jié)點(diǎn)逆時針左旋轉(zhuǎn)，遵循“旋轉(zhuǎn)優(yōu)先”的規(guī)則，A結(jié)點(diǎn)替換D結(jié)點(diǎn)成為C的左子樹，D結(jié)點(diǎn)成為A的右子樹。（4）RL型RL型：插入位置為右子樹的左孩子，進(jìn)行兩次調(diào)整，先右旋轉(zhuǎn)調(diào)整為RR型，再左旋轉(zhuǎn)，從RR型調(diào)整到平衡二叉樹；處理情況與LR類似。includeiostreamincludefstreamincludeusing namespace std。 TreeNode *rchild。 void CreateTree(TreeNode *amp。r)。r)。r)。T)。}int AVLTree::GetHeight(TreeNode *root){ int len。}int AVLTree::GetBF(TreeNode *root){ int bf。root,int data){ if(root==NULL) { root=(TreeNode*)malloc(sizeof(TreeNode))。 // rootBF=GetBF(root)。//對樹進(jìn)行左平衡處理 break。 } } else if(datarootm_nValue) { CreateTree(rootrchild,data)。 break。 } if(rootl
公司管理相關(guān)推薦
鄂ICP備17016276號-1