数据结构——平衡二叉树

建议学习此数据结构可以先观看此视频

https://www.bilibili.com/video/BV1xE411h7dd

平衡二叉树的定义：

1.必须是一颗二叉查找树；

2.每一个节点的左子树和右子树的高度差至多为1。

平衡因子：二叉树节点的左子树高度减去右子树高度的值称为该节点的平衡因子（我在代码中的注释称为平衡度），一个平衡二叉树节点的平衡因子只能是0，1，-1.

平衡二叉树的节点结构：

typedef struct tree { int data; int height; tree*left; tree*right; } tree;

由于在平衡二叉树中插入或者删除一个元素会导致失去平衡，所以我们需要平衡二叉树的平衡调整：

1.LL型调整：需要LL型调整的树是k2为k1的左孩子，k3为k2的左孩子这种结构的树，他需要以k2为轴，顺时针转动k1，最终k2变成根节点，k1变成k2的右孩子，k3仍为k2的左孩子。

//LL类型的单向旋转 tree*AVL::SingleRotate_LL(tree*p2) { tree*p1; p1=p2->left; p2->left=p1->right; p1->right=p2; p2->height=max(HeightofTree(p2->left),HeightofTree(p2->right))+1; p1->height=max(HeightofTree(p1->left),HeightofTree(p1->right))+1; return p1; }

2.RR型调整：需要RR型调整的树是k2为k1的右孩子，k3为k2的右孩子这种结构的树，他需要以k2为轴，逆时针转动k1，最终k2变成根节点，k1变成k2的左孩子，k3仍为k2的右孩子。

//RR类型的单向旋转 tree*AVL::SingleRotate_RR(tree*p2) { tree*p1; p1=p2->right; p2->right=p1->left; p1->left=p2; p2->height=max(HeightofTree(p2->left),HeightofTree(p2->right))+1; p1->height=max(HeightofTree(p1->left),HeightofTree(p1->right))+1; return p1; }

3.LR型调整：需要LR型调整的树是k2为k1的左孩子，k3为k2的右孩子这种结构的树，他需要先以k2为轴进行一次RR类型的调整，k3变成k1的左孩子，k2变成k3的左孩子，再以调整之后的(k2——plus)为轴（调整之前是k3），顺时针转动k1（就是进行一次LL类型的调整），最终k3变成根节点，k2变成k3的左孩子，k1变成k3的右孩子。

//LR类型的双向旋转 tree*AVL::DoubleRotate_LR(tree*p) { p->left=SingleRotate_RR(p->left); return SingleRotate_LL(p); }

4.RL型调整：需要RL型调整的树是k2为k1的右孩子，k3为k2的左孩子这种结构的树，他需要先以k2为轴进行一次LL类型的调整，k3变成k1的右孩子，k2变成k3的右孩子，再以调整之后的(k2——plus)为轴（调整之前是k3），逆时针转动k1（就是进行一次LL类型的调整），最终k3变成根节点，k2变成k3的右孩子，k1变成k3的左孩子。

//RL类型的双向旋转 tree*AVL::DoubleRotate_RL(tree*p) { p->right=SingleRotate_LL(p->right); return SingleRotate_RR(p); }

其他的部分操作和二叉排序树一样，下面来说一些不一样的函数操作：

1.计算一棵树的高度：求树的高度——这里的高度默认空节点高度为0，单一的叶子节点高度为1，其他节点的高度为其左右子树高度最大值+1，所以同层的节点高度不一定相同！！

//求树的高度——这里的高度默认空节点高度为0，单一的叶子节点高度为1，其他节点的高度为其左右子树高度最大值+1，所以同层的节点高度不一定相同！！ int AVL::HeightofTree(tree*p) { if(p==nullptr) return 0; else return p->height; }

2.获取节点的平衡因子

int AVL::getBalance(tree*p) { if(p==nullptr) return 0; return HeightofTree(p->left)-HeightofTree(p->right); }

3.从一个数组创建一棵平衡二叉树

tree* AVL::create(vector<int>&data,tree*p) { for(int i=0; i<data.size(); i++) { p=insert(data[i],p); } return p; }

下面开始重头戏

1.插入操作

如果节点为空就创建一个叶子节点，高度赋值为1，并对数据域赋值插入值；

如果节点值大于插入值就去当前节点的左子树中寻找插入位置，并在插入完成之后检查当前树的平衡性，如果不平衡就判断类型并选择适当的旋转类型；

如果节点值小于插入值就去当前节点的右子树中寻找插入位置，并在插入完成之后检查当前树的平衡性，如果不平衡就判断类型并选择适当的旋转类型。

最后更新当前节点的高度数据，并返回当前节点的指针。

tree*AVL::insert(int x,tree*p) { if(p==nullptr) { p=new tree; p->data=x; p->height=1; p->left=nullptr; p->right=nullptr; } else if(x<p->data) { p->left=insert(x,p->left); if(HeightofTree(p->left)-HeightofTree(p->right)==2) { if(x<(p->left->data)) p=SingleRotate_LL(p); else p=DoubleRotate_LR(p); } } else if(x>p->data) { p->right=insert(x,p->right); if(HeightofTree(p->right)-HeightofTree(p->left)==2) { if(x>(p->right->data)) p=SingleRotate_RR(p); else p=DoubleRotate_RL(p); } } //如果x==p->data.说明x的值已经在树中，不用做处理 p->height=max(HeightofTree(p->left),HeightofTree(p->right))+1; return p; }

2.删除操作

如果传入的指针为空指针，说明查找到最后并没有找到应该被删除的值，所以当前树中没有要删除的值；

如果节点值大于删除值就去当前节点的左子树中寻找应当要删除的节点的位置；

如果节点值小于删除值就去当前节点的右子树中寻找应当要删除的节点的位置；

如果节点值等于删除值，那么就开始执行删除操作；

（1）如果删除节点既有左孩子又有右孩子：

就先在当前节点左右子树中高度更高的那一棵树t中进行操作；

如果t是当前节点的左子树，就寻找t中的最大值x，并把t中的最大值x赋值给当前节点，然后递归的去左子树中删除x的节点；

如果t是当前节点的右子树，就寻找t中的最小值x，并把t中的最小值x赋值给当前节点，然后递归的去右子树中删除x的节点；

（2）如果删除节点并非有两个孩子，那么有三种情况：

  1.如果左为空，那么用当前节点的右子树来代替删除后当前节点的位置；   2.如果右为空，那么用当前节点的左子树来代替删除后当前节点的位置；   3.如果左右子树都为空的话，那么“？：”的表达式就会使p等于p->right，同样为空。

之后，判断如果删除的是叶子节点（删除节点既没有左孩子，也没有右孩子）那么直接返回空指针；

否则更新被删除的节点的新节点的高度数据，然后判断当前树是否平衡，如果平衡就直接返回新节点的指针，否则就判断导致不平衡的类型，然后根据类型来执行旋转，并返回旋转之后的新指针。

tree* AVL::Delete(int x,tree*p) { if(p==nullptr) { cout<<"树中没有要删除的值!"<<endl; return nullptr; } if(x<p->data)//目标值小于节点值，去左边寻找 { p->left=Delete(x,p->left); } else if(x>p->data)//目标值大于节点值，去右边寻找 { p->right=Delete(x,p->right); } else//目标值等于节点值，开始执行删除操作 { if((p->left!=nullptr)&&(p->right!=nullptr))//左右子树都非空 { //在高度更大的那个树上进行删除操作 if(HeightofTree(p->left)>HeightofTree(p->right)) { p->data=findmax(p->left)->data; p->left=Delete(p->data,p->left); } else { p->data=findmin(p->right)->data; p->right=Delete(p->data,p->right); } } else//左右子树中有空的 { /* 这里的处理比较巧妙，三种情况 1.如果左为空，那么用当前节点的右子树来代替删除后当前节点的位置 2.如果右为空，那么用当前节点的左子树来代替删除后当前节点的位置 3.如果左右子树都为空的话，那么“？：”的表达式就会使p等于p->right，同样为空 */ tree*temp=p; p=p->left?p->left:p->right; delete temp; } } if(p==nullptr) return nullptr; //跟新节点高度数据 p->height=max(HeightofTree(p->left),HeightofTree(p->right))+1; //计算当前节点的平衡度 int balance=getBalance(p); //使树恢复平衡 if(balance>1&&getBalance(p->left)>=0)//如果左树比右树高的多导致的不平衡，并且左孩子的左子树仍然比他的右子树要高，说明是LL类型 return SingleRotate_LL(p); if(balance>1&&getBalance(p->left)<0)//如果左树比右树高的多导致的不平衡，并且左孩子的右子树比他的左子树要高，说明是LR类型 return DoubleRotate_LR(p); if(balance<-1&&getBalance(p->right)<=0)//如果右树比左树高的多导致的不平衡，并且右孩子的右子树仍然比他左子树要高，说明是RR类型 return SingleRotate_RR(p); if(balance<-1&&getBalance(p->right)>0)//如果右树比左树高的多导致的不平衡，并且右孩子的左子树比他的右子树要高，说明是RL类型 return DoubleRotate_RL(p); return p; }

整体代码：

#include<iostream> #include<cstdlib> #include<vector> using namespace std; typedef struct tree { int data; int height; tree*left; tree*right; } tree; class AVL { private: tree*root; tree*find(int x,tree*p);//查找算法 tree*findmax(tree*p);//树中最大值 tree*findmin(tree*p);//树中最小值 void perish(tree*p);//销毁二叉树 void midLook(tree*p);//中序遍历 void frontLook(tree*p);//前序遍历 int getBalance(tree*p);//获取节点的平衡度 int HeightofTree(tree*p);//计算一棵树的高度 tree*SingleRotate_LL(tree*p2);//LL类型的单向旋转 tree*SingleRotate_RR(tree*p2);//RR类型的单向旋转 tree*DoubleRotate_LR(tree*p);//LR类型的双向旋转 tree*DoubleRotate_RL(tree*p);//RL类型的双向旋转 tree*create(vector<int>&data,tree*p);//创建二叉树 tree*insert(int x,tree*p);//插入算法 tree*Delete(int x,tree*p);//删除算法 public: AVL(vector<int > & data); void Look(); void search(int x); void Extremum(); void add(int x); void sub(int x); ~AVL(); }; AVL::AVL(vector<int>&data) { root=nullptr; root=create(data,root); } void AVL::Look() { cout<<"当前树的中序遍历："; midLook(root); cout<<endl; cout<<"当前树的前序遍历："; frontLook(root); } void AVL::search(int x) { tree*dd=find(x,root); if(dd!=nullptr) { cout<<"已经搜索到目标值!"<<endl; cout<<"目标值："<<dd->data<<endl; } else { cout<<"目标值不在树中！"<<endl; } } void AVL::Extremum() { tree*dd=findmax(root); cout<<"当前树中的最大值："; cout<<dd->data<<endl; dd=findmin(root); cout<<"当前树中的最小值："; cout<<dd->data<<endl; } void AVL::add(int x) { cout<<"向平衡二叉树中添加元素"<<x<<endl; insert(x,root); } void AVL::sub(int x) { cout<<"删除平衡二叉树中的元素"<<x<<endl; Delete(x,root); } AVL::~AVL() { if(root!=nullptr) perish(root); } tree*AVL::findmax(tree*p) { if(p!=nullptr) while(p->right!=nullptr) p=p->right; return p; } tree*AVL::find(int x,tree*p) { if(p==nullptr) return nullptr; if(x<(p->data)) return find(x,p->left); else if(x>(p->data)) return find(x,p->right); else return p; } tree*AVL::findmin(tree*p) { if(p==nullptr) return nullptr; else if(p->left==nullptr) return p; else if(p->left!=nullptr) return findmin(p->left); } void AVL::perish(tree*p) { if(p==nullptr) return ; perish(p->left); perish(p->right); delete p; } void AVL::midLook(tree*p) { if(p==nullptr) return; midLook(p->left); cout<<p->data<<" "; midLook(p->right); } void AVL::frontLook(tree*p) { if(p==nullptr) return; cout<<p->data<<" "; frontLook(p->left); frontLook(p->right); } //求树的高度——这里的高度默认空节点高度为0，单一的叶子节点高度为1，其他节点的高度为其左右子树高度最大值+1，所以同层的节点高度不一定相同！！ int AVL::HeightofTree(tree*p) { if(p==nullptr) return 0; else return p->height; } //LL类型的单向旋转 tree*AVL::SingleRotate_LL(tree*p2) { tree*p1; p1=p2->left; p2->left=p1->right; p1->right=p2; p2->height=max(HeightofTree(p2->left),HeightofTree(p2->right))+1; p1->height=max(HeightofTree(p1->left),HeightofTree(p1->right))+1; return p1; } //RR类型的单向旋转 tree*AVL::SingleRotate_RR(tree*p2) { tree*p1; p1=p2->right; p2->right=p1->left; p1->left=p2; p2->height=max(HeightofTree(p2->left),HeightofTree(p2->right))+1; p1->height=max(HeightofTree(p1->left),HeightofTree(p1->right))+1; return p1; } //LR类型的双向旋转 tree*AVL::DoubleRotate_LR(tree*p) { p->left=SingleRotate_RR(p->left); return SingleRotate_LL(p); } //RL类型的双向旋转 tree*AVL::DoubleRotate_RL(tree*p) { p->right=SingleRotate_LL(p->right); return SingleRotate_RR(p); } int AVL::getBalance(tree*p) { if(p==nullptr) return 0; return HeightofTree(p->left)-HeightofTree(p->right); } tree*AVL::insert(int x,tree*p) { if(p==nullptr) { p=new tree; p->data=x; p->height=1; p->left=nullptr; p->right=nullptr; } else if(x<p->data) { p->left=insert(x,p->left); if(HeightofTree(p->left)-HeightofTree(p->right)==2) { if(x<(p->left->data)) p=SingleRotate_LL(p); else p=DoubleRotate_LR(p); } } else if(x>p->data) { p->right=insert(x,p->right); if(HeightofTree(p->right)-HeightofTree(p->left)==2) { if(x>(p->right->data)) p=SingleRotate_RR(p); else p=DoubleRotate_RL(p); } } //如果x==p->data.说明x的值已经在树中，不用做处理 p->height=max(HeightofTree(p->left),HeightofTree(p->right))+1; return p; } tree* AVL::create(vector<int>&data,tree*p) { for(int i=0; i<data.size(); i++) { p=insert(data[i],p); } return p; } tree* AVL::Delete(int x,tree*p) { if(p==nullptr) { cout<<"树中没有要删除的值!"<<endl; return nullptr; } if(x<p->data)//目标值小于节点值，去左边寻找 { p->left=Delete(x,p->left); } else if(x>p->data)//目标值大于节点值，去右边寻找 { p->right=Delete(x,p->right); } else//目标值等于节点值，开始执行删除操作 { if((p->left!=nullptr)&&(p->right!=nullptr))//左右子树都非空 { //在高度更大的那个树上进行删除操作 if(HeightofTree(p->left)>HeightofTree(p->right)) { p->data=findmax(p->left)->data; p->left=Delete(p->data,p->left); } else { p->data=findmin(p->right)->data; p->right=Delete(p->data,p->right); } } else//左右子树中有空的 { /* 这里的处理比较巧妙，三种情况 1.如果左为空，那么用当前节点的右子树来代替删除后当前节点的位置 2.如果右为空，那么用当前节点的左子树来代替删除后当前节点的位置 3.如果左右子树都为空的话，那么“？：”的表达式就会使p等于p->right，同样为空 */ tree*temp=p; p=p->left?p->left:p->right; delete temp; } } if(p==nullptr) return nullptr; //跟新节点高度数据 p->height=max(HeightofTree(p->left),HeightofTree(p->right))+1; //计算当前节点的平衡度 int balance=getBalance(p); //使树恢复平衡 if(balance>1&&getBalance(p->left)>=0)//如果左树比右树高的多导致的不平衡，并且左孩子的左子树仍然比他的右子树要高，说明是LL类型 return SingleRotate_LL(p); if(balance>1&&getBalance(p->left)<0)//如果左树比右树高的多导致的不平衡，并且左孩子的右子树比他的左子树要高，说明是LR类型 return DoubleRotate_LR(p); if(balance<-1&&getBalance(p->right)<=0)//如果右树比左树高的多导致的不平衡，并且右孩子的右子树仍然比他左子树要高，说明是RR类型 return SingleRotate_RR(p); if(balance<-1&&getBalance(p->right)>0)//如果右树比左树高的多导致的不平衡，并且右孩子的左子树比他的右子树要高，说明是RL类型 return DoubleRotate_RL(p); return p; } int main() { vector<int>data={16,3,7,11,9,26,18,14,15}; AVL avl(data); avl.Look(); cout<<endl; avl.Extremum(); avl.search(14); avl.add(20); avl.Look(); cout<<endl; avl.Extremum(); avl.search(20); avl.sub(20); avl.Look(); cout<<endl; avl.Extremum(); avl.search(20); return 0; }

测试数据：16,3,7,11,9,26,18,14,15

运行：