树论_平衡二叉树

平衡二叉树的定义

平衡因子：balance factor，一般定义为左子树高度减去右子树高度

平衡二叉树：AVL树，就是每个节点的balance factor的绝对值小于等于1的二叉树，需要在每次插入删除操作之后调整最小不平衡树以维护每个节点的balance factor在-1，0，1之间

最小不平衡树：插入后破坏平衡的节点为问题节点（trouble），离问题节点trouble最近的balance factor不正常的祖先节点就是发现者（finder），最小不平衡树就是以finder为根节点的不平衡的二叉树

实现原理

无论是插入还是删除都可能产生最小不平衡树，需要对最小不平衡树进行调整以维护平衡因子，有时即便不需要调整树的结构，也需要更改平衡因子

节点的结构

需要在节点中增加bf（平衡因子），以判断以这个节点为根节点的树是否平衡

struct TreeNode{ DataType data; struct TreeNoe* left,*right; int bf; }

调整策略

有左旋和右旋两种操作调整树的结构

这里把空节点也看作一个节点，即每个非空节点都有两个儿子，可能有“空儿子”

左旋

设需要调整的树的根节点为T，T的左儿子为L，L的右儿子为Lr，需要让Lr移给T作为T的左儿子，再让T作为L的右儿子，调整后原来的L作为调整后的树的根节点

[[左旋.png]]

图中三角形代表子树

若Lr为空：[[左旋_1.png]]，N代表“空儿子”

TreeNode* LeftRotate(TreeNode* T){ TreeNode* R=t->right; T->right=R->left; R->left=T; return R; }

右旋

设需要调整的树的根节点为T，T的右儿子为R，R的左儿子为Rl，需要让Rl作为T的右儿子，再让T作为R的左儿子，调整后原来的R作为调整后的树的根节点

[[右旋.png]]

TreeNode* RightRotate(TreeNode* T){ TreeNode* L=T->left; T->left=L->right; L->right=T; return L }

最小不平衡树的调整

最小不平衡树有两种情况，一种是左子树高度大于右子树高度，即根节点的bf大于1，另一种是右子树高度大于左子树高度，即根节点的bf小于-1

设最小不平衡树的根节点为finder

调整最小平衡树后需要维护bf值

根节点的bf大于1

很明显问题出在finder的左子树上，需要讨论finder的左儿子的bf

设finder的左儿子为L

由于finder是离trouble最近的bf不正常的节点，所以finder的子孙节点的bf都是正常的，也就是-1，0，1三种情况

finder的左儿子L的bf只可能为==-1或1==，不可能为0，假设插入前L的bf为1，finder的bf为1，插入节点插在L的右子树上，插入之后L的bf变为0，但以L为根节点的子树的高度没有改变，finder的bf就不会改变，也就是插入之后没有产生最小不平衡树

[[L的bf为0的假设.png]]

图中m表示子树的高度

根节点的左儿子的bf为1

说明插入节点在L的左儿子上，L的bf与finder的bf同号，只需要对finder进行右旋调整

调整之后原来的finder节点和L节点的bf变为0

[[L的bf为1.png]]

根节点的左儿子的bf为-1

说明插入节点在L的右儿子上，L的bf与finder的bf异号，若直接对finder进行右旋，调整之后仍然不平衡，需要先对L进行左旋，再对finder进行右旋调整

需要根据L的右儿子Lr的bf值来更改最终调整后的原来的L节点和finder节点的bf的值，Lr节点调整后的bf值为0

[[L的bf为-1.png]]

• Lr的bf为0，最终调整后L的bf和finder的bf都为0
• Lr的bf为1，最终调整后L的bf为0，finder的bf为-1
• Lr的bf为-1，最终调整后L的bf为1，finder的bf为0

实现

TreeNode* LeftAdjust(TreeNode* finder){ TreeNode* L=finder->left; if(L->bf==1){ T->bf=L->bf=0; return RightRotate(finder); //直接对finder右旋 } else { //L->bf==-1 TreeNode* Lr=L->right; if(Lr->bf==0){ L->bf=finder->bf=0; } else if(Lr->bf==1){ L->bf=0; finder->bf=-1; } else if(Lr->bf==-1){ L->bf=1; finder->bf=0; } Lr->bf=0; finder->left=LeftRotate(L); //对L左旋 return RightRotate(finder); //对finder右旋 } }

根节点的bf小于-1

与根节点的bf大于1的LeftAdjust类似

设R为根节点finder的右儿子

根节点的右儿子的bf为-1

R的bf和finder的bf同号，直接将finder左旋

根节点的右儿子的bf为1

R的bf和finder的bf不同号，先将R右旋，再将finder左旋

Rl为R的左儿子

• Rl的bf为0，最终调整后R的bf和finder的bf都为0
• Rl的bf为-1，最终调整后R的bf为0，finder的bf为1
• Rl的bf为1，最终调整后R的bf为-1，finder的bf为0

实现

TreeNode* RightAdjuct(TreeNode* finder){ TreeNode* R=finder->right; if(R->bf==-1){ finder->bf=R->bf=0; return LeftRotate(finder); } else { //R->bf==1 TreeNode* Rl=R->left; if(Rl->bf==0){ R->bf=finder->bf=0; } else if(Rl->bf==-1){ R->bf=0; finder->bf=1; } else if(Rl->bf==1){ R->bf=-1; finder->bf=0; } Rl->bf=0; finder->right=RightRotate(R); return LeftRotate(finder); } }

AVL树的插入

继承二叉树递归插入的思想，若需要插入的树为空，则增加一个节点并插入

思路

为了找到finder，需要增加一个布尔型变量isTaller，若树增高了，isTaller为true，否则为false，每次调用插入函数都需要更改isTaller来表示以当前的节点为根节点的子树高度是否增加，特殊的，在一个空树插入节点后原本是空树的高度增加了（0->1）

finder是离trouble最近的bf不正常的祖先节点，为了找到finder可以利用递归插入的特性：每次深一层的函数结束后退回浅一层的函数，实际上就是从儿子节点的插入函数退回到父节点的插入函数，只需要在父节点的插入函数（浅一层的函数）调用子节点的插入函数（深一层的函数）后，检查isTaller是否为真

isTall若为真，说明插入的子树的高度增加了，需要再检查当前的节点的bf

• 若插在了左子树上
  • 若该节点的bf为1，左子树高度增加后bf会失衡，需要对该节点LeftAdjust，调整以后以该节点为根节点的子树的高度不变（与插入前一样）
  • 若该节点的bf为0，左子树高度增加后bf变为1，仍然平衡，但以该节点为根节点的子树高度增加了
  • 若该节点的bf为-1，左子树高度增加后bf变为0，仍然平衡，且以该节点为根节点的子树高度不变
• 若插在了右子树上
  • 若该节点的bf为-1，右子树高度增加后bf会失衡，需要对该节点RightAdjust，调整以后以该节点为根节点的子树高度不变（与插入前一样）
  • 若该节点的bf为0，右子树高度增加后bf变为-1，仍然平衡，但以该节点为根节点的子树高度增加了
  • 若该节点的bf为1，右子树高度增加后bf变为0，仍然平衡，且以该节点为根节点的子树高度不变

实现

bool isInsert=true; //是否插入成功 bool isTaller; //树高度是否增加 TreeNode* InsertAVL(TreeNode* t,DataType key){ if(!t){ TreeNode* p=new TreeNode; p->data=key; p->left=p->right=nullptr; p->bf=0; isTaller=ture; //树高增加 return p; } if(key<t->data){ //递归在左子树插入 t->left=InsertAVL(t->left,key); if(!isInsert)return t; //插入失败就不做处理直接返回 if(isTaller){ if(t->bf==1){ t->bf=0; isTaller=false; return LeftAdjust(t); } else if(t->bf==0){ t->bf=1; isTaller=true; } else if(t->bf==-1){ t->bf=0; isTaller=false; } } } else if(key>t->data){ //递归在右子树插入 t->right=Insert(t->right,key); if(!isInsert)return t; //插入失败就直接返回 if(isTaller){ if(t->bf==-1){ t->bf=0; isTaller=0; return RightAdjust(t); } else if(t->bf==0){ t->bf=-1; isTaller=true; } else if(t->bf==1){ t->bf=0; isTaller=false; } } } else { //插入失败 isInsert=false; isTaller=false; } return t; }

AVL树的删除

也是继承二叉树的删除思想

思路

二叉树的删除有两种情况：

• 要删除的节点左右子树至少有一个为空，让另一个儿子替换要删除的节点（即便另一个儿子也是空的）
• 要删除的节点左右子树都不空，对于一般的二叉树来说用左子树的最小值或右子树的最大值来替换该节点的方案都可以，但对于AVL树，需要先检查该节点的bf
  • 若该节点的bf为1，说明左子树比右子树高，假设找右子树的最大值与该节点交换data，再删除右子树原来最大值的那个节点，可能造成右子树高度减小，导致该节点的bf大于1，所以选择左子树的最小值与该节点交换
  • 若该节点的bf为0，处理方式就设置为与bf为1时一样
  • 若该节点的bf为-1，同理，需要找右子树的最大值与该节点交换

与插入类似，需要一个isShorter来记录树的高度是否降低，每次递归的调用子树的删除函数后，检查isShorter是否为真

若isShorter为真，说明删除后的子树高度减小了，需要再检查当前节点的bf，根据bf（-1，0，1）和在哪个子树上删除（左子树，右子树）来决定删除后以该节点为根节点的子树高度是否减小，删除后该节点的bf如何改变

实现

bool isDelete=ture; bool isShorter; TreeNode* DeleteAVL(TreeNode* t,key){ if(!t){ //删除失败 isDelete=false; isShorter=false; return t; } if(key<t->left){ t->left=DeleteAVL(t->left,key); if(!isDelete)return t; //删除失败直接返回 if(isShorter){ if(t->bf==-1){ t->bf=0; isShorter=false; return RightAdjust(t); } else if(t->bf==0){ t->bf=-1; isShorter=false; } else if(t->bf==1){ t->bf=0; isShorter=true; } } } else if(key>t->left){ t->right=DeleteAVL(t->right,key); if(!isDelete)return t; //删除失败直接返回 if(isShorter){ if(t->bf==1){ t->bf=0; isShorter=false; return LeftAdjust(t); } else if(t->bf==0){ t->bf=1; isShorter=false; } else if(t->bf==-1){ t->bf=0; isShorter=true; } } } else { //找到了需要删除的节点 if(t->left&&t->right){ //左右子树都存在 if(t->bf==1){ TreeNode* leftMin=findMin(t->left); t->data=left->data; t->left=Delete(t->left,left->data); if(isShorter)t->bf=0; //根据isShorter修改bf值 } else if(t->bf==0){ TreeNode* leftMin=findMin(t->left); t->data=left->data; t->left=Delete(t->left,left->data); if(isShorter)t->bf=-1; //根据isShorter修改bf值 } else if(t->bf==-1){ TreeNode* rightMax=findMax(t->right); t->data=rightMax->data; t->right=Delete(t->right,rightMax->data); if(isShorter)t->bf=0; //根据isShorter修改bf值 } } else if(t->left){ //左子树存在 TreeNode* tmp=t; t=t->left; delete tmp; isShort=true; } else { //右子树存在(即便为空) TreeNode* tmp=t; t=t->right; delete tmp; isShort=ture; } } return t; }

由BST建AVL

利用二叉查找树已经有序的特性

• 通过对原来的BST中序遍历得到有序序列（从小到大）
• 通过有序序列递归地建树，每次选取序列段中的下标在中间的节点进行插入，然后递归地通过这个节点在序列中的左边的序列段建立这个节点的左子树，通过这个节点在序列中的右边的序列段建立这个节点的右子树

假设给定一颗二叉查找树root，需要建立avl树

vector<TreeNode*> inorder; //记录有序序列 TreeNode* getAVL(TreeNode* root){ InOrderTraversal(root); return buildAVL(0,inorder.size()-1); } void InOrderTraversal(TreeNode* root){ InOrderTraversal(root->left); inorder.push_back(); InOrderTraversal(root->right); } TreeNode* buildAVL(int left,int right){ if(left>right)return nullptr; int middle=(left+right)/2; TreeNode* t=new TreeNode; t->val=inorder[middle]->val; t->left=buildAVL(left,middle-1); t->right=buildAVL(middle+1,right); return t; }