平衡二叉树的生成过程

1、请下载支持!3蝴睛荽二叉排序树变成平衡二叉树蒯靖芨羁蜗薄对于二叉查找树，尽管查找、插入及删除操作的平均运行时间为O(logn)，但是它们的最差运行时间都是 O(n),原因在于对树的形状没有限制。袅滕螃嵋苗聿平衡二叉树又称为 AVL树，它或者是一棵空树，或者是有下列性质的二叉树：它 的左子树和右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。二叉树的的平衡因子BF为：该结点的左子树的深度减去它的右子树的深度，则平衡二叉树的所有结点 的平衡因子为只可能是：-1、0和1 m精冗n腿方艘一棵好的平衡二叉树的特征：赚建瞧蜗唐蚂n (1)保证有n个结点的树的高度为 O(logn)黜澹鬻战菜(2)

2、容易维护，也就是说，在做数据项的插入或删除操作时，为平衡树所做的一些辅助操作时间开销为 0(1) 荒肆蝇羁黄芾筮一、平衡二叉树的构造 袈量螃薄聿蓬前在一棵二叉查找树中插入结点后，调整其为平衡二叉树。若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树膈筮蝴蜗蚁先妨1.调整方法膂袄爵獭袄莅(1)插入点位置必须满足二叉查找树的性质，即任意一棵子树的左结点都小于根 结点

3、，右结点大于根结点肃噩霄肄腿芈(2)找出插入结点后 不平衡的最小二叉树 进行调整，如果是整个树不平衡，才进 行整个树的调整。蜘膀屋疆量曹耀2.调整方式点裂蒂薇袂蒂凡(1 ) LL型蔓募菽屋充募黄LL型：插入位置为左子树的左结点，进行向右旋转(LL表示的是在做子树的左结点进行插入)赣祎荒袁蒲肇凌由于在A的左孩子B的左子树上插入结点 F,使A的平衡因子由1变为2,成为不 平衡的最小二叉树根结点。此时 A结点顺时针右旋转，旋转过程中遵循 旋转优先”的规则， A结点替换D结点成为B结点的右子树，D结点成为A结点的左孩子。妍筮董肆量去节RR型英赚滕藏衿肄肆RR型：插入位置 为右子树的右孩子，进行向左旋转

4、籍莆方聿Q黄由于在A的右子树C的右子树插入了结点 F, A的平衡因子由-1变为-2,成为不平 衡的最小二叉树根结点。此时， A结点逆时针左旋转，遵循 旋转优先”的规则，A结点替换 D结点成为C的左子树，D结点成为A的右子树。菱嫌膈第荽肇量(3) LR型誉芨羁蜗踌蟹薄LR型：插入位置为 左子树的右孩子，要进行两次旋转，先左旋转，再右旋转；第一次最小不平衡子树的根结点先不动，调整插入结点所在的子树， 调整后的树变成LL型树,第二次再调整最小不平衡子树 (根据LL型的调整规则，调整为平衡二叉树)。螃嵋苗聿莉蛔由于在A的左子树B的右子树上插入了结点 F, A的平衡因子由1变为了 2,成为 不平衡的最小

5、二叉树根结点。第一次旋转 A结点不动，先将 B的右子树的根结点 D向左上 旋转提升到B结点的位置，然后再把该 D结点向右上旋转提升到 A结点的位置。请下载支持!黄箍腿方艘袅滕（4） RL型瞧期唐蚂mI辐RL型：插入位置为右子树的左孩子，进行两次调整，先右旋转调整为RR型，再左旋转，从RR型调整到平衡二叉树；处理情况与LR类似。曹凌墓芍翱瞬总结：RR型和LL型插入导致的树失去平衡，只需要做一次旋转调整即可。而 RL 型和LR型插入导致的结点失去平衡，要调整两次。对于 RL/LR的调整策略是：蝇羁黄芾筮薄芍第一次调整，最小不平衡子树的根结点先不动，调整插入结点所在的子树（这个子树是指最小不平衡结点

6、的一颗子树，且这棵子树是插入结点的子树）为RR型或者LL型，第二次再调整最小不平衡子树（调整策略要么是 RR型要么是LL型）。螃薄聿蓬前蔻肆#include<iostream>#include<fstream>#include<malloc.h>using namespace std;# defineLH 1/ 左高# defineEH 0/ 等高# define RH -1 右高struct TreeNode int m_nValue;int BF;/平衡因子TreeNode *lchild;TreeNode *rchild;刷蜗蚁先妨袈量class AV

7、LTreepublic:AVLTree();AVLTree();void CreateTree(TreeNode *&root,int data);/ 创建 AVLvoid PreTraver(TreeNode *root);/先序遍历void RR_Rotate(TreeNode *&r);右旋转处理int GetHeight(TreeNode *root);/获得树的高度int GetBF(TreeNode *root);/获得树的平衡因子void LL_Rotate(TreeNode *&r);/左旋转处理void RL_Rotate(TreeNode *&

8、;r);/双旋处理，先右旋转，再左旋转void LR_Rotate(TreeNode *&r);/双旋处理，先左旋转，再右旋转void LeftBalance(TreeNode *&T);/ 左平衡处理void RightBalance(TreeNode *&T);/右平衡处理曹神腿袄莅膈筮;int Max(int a,int b)if(a>b)return a;else return b;int AVLTree:GetHeight(TreeNode *root)请下载支持!(int len;if(root=NULL)len=0;else(len=Max(GetH

9、eight(root->lchild),GetHeight(root->rchild)+1;)return len;)int AVLTree:GetBF(TreeNode *root)(int bf;/平衡因子bf=GetHeight(root->lchild)-GetHeight(root->rchild);return bf;)void AVLTree:CreateTree(TreeNode *&root,int data)(if(root=NULL)(root=(TreeNode*)malloc(sizeof(TreeNode);root->m_nV

10、alue=data;root->lchild=NULL;root->rchild=NULL;/ root->BF=GetBF(root);root->BF=EH;/初始叶子结点的平衡因子为等高)else if(data<root->m_nValue)(CreateTree(root->lchild,data);switch(root->BF) 检查 root 的平衡度 case，现在左子树更高LeftBalance(root);/对树进行左平衡处理break; case，现在左子树高root->BF=LH;/root 的平衡因子由0变为1

11、break; case ,现在左右子树等高root->BF=EH;)else if(data>root->m_nValue)CreateTree(root->rchild,data);switch(root->BF) case LH:root->BF=EH;/ 原来树 root 的左子树比右子树高，现在root的左右子树等高break; case ,现在root的右子树更高root->BF=RH; break; case ,现在 root 右子树高RightBalance(root);/ 对称if root 作右平衡处理请下载支持!)void AVLT

12、ree:PreTraver(TreeNode *root)(if(root) cout.width(3);cout<<root->m_nValue;)if(root->lchild)PreTraver(root->lchild);if(root->rchild)PreTraver(root->rchild);)void AVLTree:LL_Rotate(TreeNode *&r)/TreeNode *p;p=r->rchild;/p指向r的右孩子结点r->rchild=p->lchild;/r结点左旋转成为p->lch

13、ild=r;/r成为p的左孩子r=p;)void AVLTree:RR_Rotate(TreeNode *&r)/ TreeNode *p;p=r->lchild;r->lchild=p->rchild;p->rchild=r;r=p;)void AVLTree:RL_Rotate(TreeNode *&r)/ 行左旋转TreeNode *p;插入位置为右子树右孩子，要进行左旋转p的左子树，p原来的左子树成为r的右子树插入位置为左子树左孩子，进行右旋转插入位置为右子树左孩子，先进行右旋转，再进p=r->rchild;RR_Rotate(p);/最小

14、失衡树的根结点的右子树根结点进行右旋转r->rchild=p;/更新最小失衡树根结点的右孩子LL_Rotate(r);/最小失衡树的根结点进行左旋转)void AVLTree:LR_Rotate(TreeNode *&r)/插入位置为左子树右孩子，先进行左旋转，再进行右旋转TreeNode *p;p=r->lchild;请下载支持!LL_Rotate(p);/最小失衡树根结点的左子树根结点进行左旋转r->lchild=p;/更新最小失衡树根结点的左孩子 RR_Rotate(r);/最小失衡树根结点进行右旋转 ) void AVLTree:LeftBalance(Tre

15、eNode *&T)/左平衡处理初始条件：原来平衡的二叉排序树 T的左子树比右子树高(T->bf=1)/又在左子树中插入了结点，并导致左子树更高，破坏了树T的平衡性/操作结果：对不平衡的树T作左平衡旋转处理，使树T的重心右移实现新的平衡 TreeNode *lc,*rd; lc=T->lchild;/lc 指向T的左孩子结点switch(lc->BF)/检查T左子树的平衡因子 case ,导致左子树的平衡因子为左高，进行右旋转处理T->BF=lc->BF=EH;旋转后，原根结点和左孩子结点平衡因子都为0 RR_Rotate(T);/右旋转处理 break;

16、 case ,导致左子树的平衡因 子为右高，进行 LR 处理 rd=lc->rchild; switch(rd->BF) case T->BF=RH;/ 旋转后，原根结点的平衡因子为右高lc->BF=EH;/旋转后，原根结点的左孩子结点平衡因子为等高 break; case T->BF=lc->BF=EH;/旋转后，原根和左孩子结点的平衡 因子都为等高 break; case T->BF=EH;/旋转后，原根结点的平衡因子为等高 lc->BF=LH;/旋转后，原根结点的左孩子结点平衡因子为左高 rd->BF=EH;/旋转后的新结点的平衡因子

17、为等高 霄w肄腿芈膂袄/双旋转处理LL_Rotate(T->lchild);/ 对T的左子树左旋转处理RR_Rotate(T);/对T作右旋转处理 犀股量普耀肃黑 希薇袂蒂ms膀void AVLTree:RightBalance(TreeNode *&T)/右平衡处理初始条件：原来平衡二叉排序树T的右子树比左子树高，又在右子树中插入结点，导致右子树更高操作结果：对不平衡的树 T 作右平衡旋转处理TreeNode *rc,*ld; rc=T->rchild; switch(rc->BF) case导致右子平衡因子为右高，进行左旋车t处理T->BF=rc->B

18、F=EH;/旋转后，原根结点和右孩子结点的平衡因子均为 0 LL_Rotate(T); break; case ,导致右子树的平衡因子为左高， 进行双旋处理 ld=rc->lchild; switch(ld->BF) case T->BF=LH;/ 旋转后，原根结点 的平衡因子为左高rc->BF=EH;/旋转后，原根结点的右孩子结点平衡因子为等高break; case T->BF=rc->BF=EH;/旋转后，原根和右孩子结点的平衡因子等高 break; case T->BF=EH;/旋转后，原根结点的平衡因子等高rc->BF=RH;/旋转后，原根结点的右孩子结点的平衡因子为右高 ld->BF=EH;/旋转后的新根结点的平衡因子为等高放犀先蒙黄鼠裂/双旋转处理RR_Rotate(T->rchild);/对T的右子树作右旋转处理LL_Rotate(T);/对T作左旋转处理 范袁蒲肇德盆募in