平衡二叉树的生成过程.doc

二叉排序树变成平衡二叉树对于二叉查找树，尽管查找、插入及删除操作的平均运行时间为O(logn)，但是它们的最差运行时间都是O(n),原因在于对树的形状没有限制。平衡二叉树又称为AVL树，它或者是一棵空树，或者是有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。二叉树的的平衡因子BF为：该结点的左子树的深度减去它的右子树的深度，则平衡二叉树的所有结点的平衡因子为只可能是：-1、0和1一棵好的平衡二叉树的特征：（1）保证有n个结点的树的高度为O(logn)（2）容易维护，也就是说，在做数据项的插入或删除操作时，为平衡树所做的一些辅助操作时间开销为O(1)一、平衡二叉树的构造在一棵二叉查找树中插入结点后，调整其为平衡二叉树。若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树1.调整方法（1）插入点位置必须满足二叉查找树的性质，即任意一棵子树的左结点都小于根结点，右结点大于根结点（2）找出插入结点后不平衡的最小二叉树进行调整，如果是整个树不平衡，才进行整个树的调整。2.调整方式（1）LL型LL型：插入位置为左子树的左结点，进行向右旋转(LL表示的是在做子树的左结点进行插入)由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1变为2，成为不平衡的最小二叉树根结点。此时A结点顺时针右旋转，旋转过程中遵循“旋转优先”的规则，A结点替换D结点成为B结点的右子树，D结点成为A结点的左孩子。（2）RR型RR型：插入位置为右子树的右孩子，进行向左旋转由于在A的右子树C的右子树插入了结点F，A的平衡因子由-1变为-2，成为不平衡的最小二叉树根结点。此时，A结点逆时针左旋转，遵循“旋转优先”的规则，A结点替换D结点成为C的左子树，D结点成为A的右子树。（3）LR型LR型：插入位置为左子树的右孩子，要进行两次旋转，先左旋转，再右旋转；第一次最小不平衡子树的根结点先不动，调整插入结点所在的子树，调整后的树变成LL型树，第二次再调整最小不平衡子树(根据LL型的调整规则，调整为平衡二叉树)。由于在A的左子树B的右子树上插入了结点F，A的平衡因子由1变为了2，成为不平衡的最小二叉树根结点。第一次旋转A结点不动，先将B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。（4）RL型RL型：插入位置为右子树的左孩子，进行两次调整，先右旋转调整为RR型，再左旋转，从RR型调整到平衡二叉树；处理情况与LR类似。总结：RR型和LL型插入导致的树失去平衡，只需要做一次旋转调整即可。而RL型和LR型插入导致的结点失去平衡，要调整两次。对于RL/LR的调整策略是：第一次调整，最小不平衡子树的根结点先不动，调整插入结点所在的子树(这个子树是指最小不平衡结点的一颗子树，且这棵子树是插入结点的子树)为RR型或者LL型，第二次再调整最小不平衡子树(调整策略要么是RR型要么是LL型)。#include#include#includeusing namespace std;#define LH 1/左高#define EH 0/等高#define RH -1/右高struct TreeNode int m_nValue; int BF;/平衡因子 TreeNode *lchild; TreeNode *rchild;class AVLTreepublic: AVLTree(); AVLTree(); void CreateTree(TreeNode *&root,int data);/创建AVL void 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 *&r);/双旋处理，先右旋转，再左旋转 void LR_Rotate(TreeNode *&r);/双旋处理，先左旋转，再右旋转 void LeftBalance(TreeNode *&T);/左平衡处理 void RightBalance(TreeNode *&T);/右平衡处理;int Max(int a,int b) if(ab)return a; else return b;int AVLTree:GetHeight(TreeNode *root) int len; if(root=NULL)len=0; else len=Max(GetHeight(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_nValue=data; root-lchild=NULL; root-rchild=NULL; / root-BF=GetBF(root); root-BF=EH;/初始叶子结点的平衡因子为等高 else if(datam_nValue) CreateTree(root-lchild,data); switch(root-BF)/检查root的平衡度 case LH:/原来树root的左子树比右子树高，现在左子树更高 LeftBalance(root);/对树进行左平衡处理 break; case EH:/原来树root的左右子树等高，现在左子树高 root-BF=LH;/root的平衡因子由0变为1 break; case RH:/原来树root的右子树比左子树高，现在左右子树等高 root-BF=EH; else if(dataroot-m_nValue) CreateTree(root-rchild,data); switch(root-BF) case LH:root-BF=EH;/原来树root的左子树比右子树高，现在root的左右子树等高 break; case EH:/原来树root的左右子树等高，现在root的右子树更高 root-BF=RH; break; case RH:/原来右子树比左子树高，现在root右子树高 RightBalance(root);/对树root作右平衡处理 void AVLTree:PreTraver(TreeNode *root) if(root) cout.width(3); coutm_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的左子树，p原来的左子树成为r的右子树 p-lchild=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=r-rchild; RR_Rotate(p);/最小失衡树的根结点的右子树根结点进行右旋转 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(TreeNode *&T)/左平衡处理/初始条件：原来平衡的二叉排序树T的左子树比右子树高(T-bf=1) / 又在左子树中插入了结点，并导致左子树更高，破坏了树T的平衡性 /操作结果：对不平衡的树T作左平衡旋转处理，使树T的重心右移实现 新的平衡 TreeNode *lc,*rd; lc=T-lchild;/lc指向T的左孩子结点 switch(lc-BF)/检查T左子树的平衡因子 case LH:/新结点插入在T的左孩子的左子树上，导致左子树的平衡因子为左高，进行右旋转处理 T-BF=lc-BF=EH;/旋转后，原根结点和左孩子结点平衡因子都 为0 RR_Rotate(T);/右旋转处理 break; case RH:/新结点插入在T的左孩子的右子树上，导致左子树的平衡因子为右高，进行LR处理 rd=lc-rchild; switch(rd-BF) case LH:/新结点插入在T的左孩子的右子树的左子树上 T-BF=RH;/旋转后，原根结点的平衡因子为右高 lc-BF=EH;/旋转后，原根结点的左孩子结点平衡因子为等高 break; case EH:/新结点插入到T的左孩子的右孩子（叶子） T-BF=lc-BF=EH;/旋转后，原根和左孩子结点的平衡因子都为等高 break; case RH:/新结点插入在T的左孩子的右子树的右子树上 T-BF=EH;/旋转后，原根结点的平衡因子为等高 lc-BF=LH;/旋转后，原根结点的左孩子结点平衡因子为左高 rd-BF=EH;/旋转后的新结点的平衡因子为等高 /双旋转处理 LL_Rotate(T-lchild);/对T的左子树左旋转处理 RR_Rotate(T);/对T作右旋转处理 void AVLTree:RightBalance(TreeNode *&T)/右平衡处理/初始条件：原来平衡二叉排序树T的右子树比左子树高，又在右子树中插入结点，导致右子树更高 /操作结果：对不平衡的树T作右平衡旋转处理 TreeNode *rc,*ld; rc=T-rchild; switch(rc-BF) case RH:/新结点插入在T的右孩子的右子树上，导致右子平衡因子为右高,进行左旋转处理 T-BF=rc-BF=EH;/旋转后，原根结点和右孩子结点的平衡因子均为0 LL_Rotate(T); break; case LH:/新结点插入在T的右孩子的左子树上，导致右子树的平衡因子为左高，进行双旋处理 ld=rc-lchild; switch(ld-BF) case RH:/新结点插入在T的右孩子的左子树的右子树上 T-BF=LH;/旋转后，原根结点的平衡因子为左高 rc-BF=EH;/旋转后，原根结点的右孩子结点平衡因子为等高 break; case EH:/新结点插入到T的右孩子的左孩子（叶子） T-BF=rc-BF=EH;/旋转后，原根和右孩子结点的平衡因子等高 break; case LH:/新结点插入到T的右孩子的左子树的左子树 T-BF=EH;/旋转后，原根结点的平衡因子等高 rc-BF=RH;/旋转后，原根结点的右孩子结点的平衡因子为右高 ld-BF=EH;/旋转后的新根结点的平衡因子为等高 /双旋转处理 RR_Rotate(T-rchild);/对T的右子树作右旋转处理 LL_Rotate(