概念
平衡因子:每个结点的平衡因子就是左右子树的高度之差,即可用如下公式表示:BF(T) = Hl-Hr 平衡二叉树:平衡二叉树可能是空树,也有可能是左右子树高度之差小于等于1的树,即平衡因子的绝对值小于等于1。 那么为了使整棵树基金可能平衡,那么在构造树的过程中必须随时检查每个结点的平衡因小于等于。那么针对各种情况,为了让树更加平衡,那么必须对不平衡的点进行旋转处理,根据不同情况可以分为单左旋(LL旋转),单右旋(RR旋转),左右旋转(LR旋转),右左旋转(RL旋转)这4种旋转技术。
下面通过图形来进行解释。如下图所示,不平衡的原因是因为A的左孩子B的左子树插入了新结点而导致了A的不平衡,那么就要利用LL旋转来调整不平衡结点A,由于平衡二叉树一定是二叉搜索树,设定插入结点为C,那么根据二叉搜索树的性质一定有,A>B>C,那么进行如下调整:把B当作根节点,A作为B的右子树(二叉搜索树的性质)。

算法如下:
//单左旋:左左旋函数
//左子树的左子树导致的失衡,把左子树与根结点进行调整
//根结点的左孩子做根结点,之前的根结点做现在根结点的右孩子
//这是因为平衡二叉树一定是二叉搜索树的缘故导致的
AVL* SingleLeftRotation(AVL* avl){
//注意:avl必须有一个左子结点tmp
//将avl与tmp做左单旋,更新avl与tmp的高度,返回新的根结点tmp
AVL* tmp = avl->lchild;
avl->lchild = tmp->rchild;
tmp->rchild = avl;
avl->height = this->Max(this->getHeight(avl->lchild),this->getHeight(avl->rchild))+1;
tmp->height = this->Max(this->getHeight(tmp->lchild),this->getHeight(avl))+1;
return tmp;
}下面通过图形来进行解释。如下图所示,不平衡的原因是因为A的右孩子B的右子树插入了新结点而导致了A的不平衡,那么就要利用RR旋转来调整不平衡结点A,由于平衡二叉树一定是二叉搜索树,设定插入结点为C,那么根据二叉搜索树的性质一定有,A>B>C,那么进行如下调整:把B当作根节点,A作为B的左子树(二叉搜索树的性质)。

算法如下:
//单右旋:右右旋函数
//右子树的右子树导致的失衡,把右子树与根结点进行调整
//根结点的右孩子做根结点,之前的根结点做现在根结点的左孩子
//这是因为平衡二叉树一定是二叉搜索树的缘故导致的
AVL* SingleRightRotation(AVL* avl){
//注意:avl必须有一个右子结点tmp
//将avl与tmp做右单旋,更新avl与tmp的高度,返回新的根结点tmp
AVL* tmp = avl->rchild;
avl->rchild = tmp->lchild;
tmp->lchild = avl;
avl->height = this->Max(this->getHeight(avl->lchild),this->getHeight(avl->rchild))+1;
tmp->height = this->Max(this->getHeight(tmp->rchild),this->getHeight(avl))+1;
return tmp;
}下面通过图形来进行解释。如下图所示,不平衡的原因是因为A的左孩子B的右子树插入了新结点而导致了A的不平衡,那么就要利用LR旋转来调整不平衡结点A,由于平衡二叉树一定是二叉搜索树,设定插入结点为C,那么根据二叉搜索树的性质一定有,A>B>C,那么进行如下调整:把A的左子树进行一次单右旋,然后对A进行一次单左旋。

算法如下:
//左右旋转:LR旋转,左子树的右子树插入导致对的失衡
AVL* DoubleLeftRightRotation(AVL* avl){
//注意:avl必须有一个左子结点B,且B必须有一个右子结点C
//将avl、B与C做两次单旋,返回新的根结点C
//首先对avl的左子树进行单右旋即RR旋转
avl->lchild = this->SingleRightRotation(avl->lchild);
//然后对avl进行单左旋即LL旋转
return this->SingleLeftRotation(avl);
}下面通过图形来进行解释。如下图所示,不平衡的原因是因为A的右孩子B的左子树插入了新结点而导致了A的不平衡,那么就要利用RL旋转来调整不平衡结点A,由于平衡二叉树一定是二叉搜索树,设定插入结点为C,那么根据二叉搜索树的性质一定有,A>B>C,那么进行如下调整:把A的右子树进行一次单左旋,然后对A进行一次单右旋。

算法如下:
//右左旋转:RL旋转,右子树的左子树插入导致对的失衡
AVL* DoubleRightLeftRotation(AVL* avl){
//注意:avl必须有一个左子结点B,且B必须有一个右子结点C
//将avl、B与C做两次单旋,返回新的根结点C
//首先对avl的左子树进行单左旋即LL旋转
avl->rchild = this->SingleLeftRotation(avl->rchild);
//然后对avl进行单右旋即RR旋转
return this->SingleRightRotation(avl);
}由于平衡二叉树一定是二叉搜索树,那么只需在二叉搜索树的插入操作上添加判断结点是否平衡需要进行旋转处理即可。 算法如下: 1)若树空,那么直接构造根节点 2)若树不空,那么若x大于根节点的键值,那么插入到左子树上。插入后检查根节点的平衡因子。如果左子树比右子树高2,那么比较x与根节左孩子的键值大小,如果x小于根节左孩子的键值,那么x一定是插在根节点的左孩子的左子树上,则进行单左旋(LL旋转)。否则x一定插在根节点的左孩子的右子树上,则进行左右旋(LR旋转)。 3)若x大于根节点的键值,那么插入到右子树上。插入后检查根节点的平衡因子。如果右子树比左子树高2,那么比较x与根节右孩子的键值大小,如果x小于根节右孩子的键值,那么x一定是插在根节点的右孩子的右子树上,则进行单右旋(RR旋转)。否则x一定插在根节点的右孩子的左子树上,则进行右左旋(RL旋转)。 4)最后对根节点的高度进行更新
//插入函数
AVL* Insert(AVL* avl,int data){
//平衡二叉树为空,则构建根节点
if(!avl){
avl = new AVL;
avl->data = data;
avl->height = 0;
avl->lchild = avl->rchild = NULL;
}else if(data < avl->data){//若data小于根节点的值,则插入到左子树
avl->lchild = avl->Insert(avl->lchild,data);
int rheight = this->getHeight(avl->rchild); //右子树高度
int lheight = this->getHeight(avl->lchild); //左子树高度
//如果插入导致左子树失衡,即左子树比右子树高2
if(lheight - rheight == 2){
if(data <avl->lchild->data){
//插入的结点比左孩子的键值小
//那么一定是插入到左孩子的左子树上,故进行LL旋转
avl = this->SingleLeftRotation(avl);
}else{//否则是插入到左孩子的右子树上,故要进行LR旋转
avl = this->DoubleLeftRightRotation(avl);
}
}
}else if(data > avl->data){//若data小于根节点的值,则插入到左子树
avl->rchild = avl->Insert(avl->rchild,data);
int rheight = this->getHeight(avl->rchild); //右子树高度
int lheight = this->getHeight(avl->lchild); //左子树高度
//如果插入导致右子树失衡,即右子树比左子树高2
if(rheight - lheight == 2){
if(data > avl->rchild->data){
//插入的结点比右孩子的键值大
//那么一定是插入到右孩子的右子树上,故进行RR旋转
avl = this->SingleRightRotation(avl);
}else{//否则是插入到右孩子的左子树上,故要进行RL旋转
avl = this->DoubleRightLeftRotation(avl);
}
}
}
//更新结点的高度
avl->height = this->Max(this->getHeight(avl->lchild),this->getHeight(avl->rchild))+1;
return avl;
} 算法如下: 1)若树空,则直接返回NULL 2)若树不空,对x与根节点的键值进行比。若x小于根结点的键值,那么递归在左子树删x。删除完毕后,检查根结点的平衡因子。若右子树比左子树高2,那么继续比较x与右孩子的键值大小。若x比右孩子的键值大,那么x在根节点的右孩子的右子树上,则进行单右旋(RR旋转),反之,x在根节点的右孩子的左子树上,则进行右左旋(RL旋转)。 3)若x大于根结点的键值,那么递归在右子树删x。删除完毕后,检查根结点的平衡因子。若左子树比右子树高2,那么继续比较x与左孩子的键值大小。若x比左孩子的键值小,那么x在根节点的左孩子的左子树上,则进行单左旋(LL旋转),反之,x在根节点的左孩子的右子树上,则进行左右旋(LR旋转)。 4)若X与根结点的键值相等,那么判断左右孩子是否存在。若左右孩子都非空,那么拿右孩子的右子树的最小结点来代替根节点。若左孩子非空,右孩子为空,那么把根节点直接赋值为左子树。若右孩子非空,左孩子为空,那么把根节点直接赋值为右子树。
//删除操作
AVL* Delete(AVL* avl,int data){
if(!avl){//树空时,直接返回NULL
return avl;
}else if(data < avl->data){
//data小于根节点时,到左子树去删除data,则有可能使右子树比左子树高2
avl->lchild = this->Delete(avl->lchild,data);
int rheight = this->getHeight(avl->rchild); //右子树高度
int lheight = this->getHeight(avl->lchild); //左子树高度
if(rheight - lheight == 2){//右子树比左子树高2时
if(data > avl->rchild->data){
//如果是data比右子树的键值大,在右子树的右子树上,则进行RR旋转
avl = this->SingleRightRotation(avl);
}else{//否则是data比右子树的键值小,在右子树的左子树上,则进行RL旋转
avl = this->DoubleRightLeftRotation(avl);
}
}
}else if(data > avl->data){
//data大于根节点时,到右子树去删除data
avl->rchild = this->Delete(avl->rchild,data);
int rheight = this->getHeight(avl->rchild); //右子树高度
int lheight = this->getHeight(avl->lchild); //左子树高度
if(lheight - rheight == 2){//左子树比右子树高2时
if(data < avl->lchild->data){
//如果是data比左子树的键值小,在左子树的左子树上,则进行LL旋转
avl = this->SingleLeftRotation(avl);
}else{//否则是data比左子树的键值大,在左子树的右子树上,则进行LR旋转
avl = this->DoubleLeftRightRotation(avl);
}
}
}else{//data等于根节点时
if(avl->lchild && avl->rchild){
//左右子树都不空时,用右子树的最小来代替根节点
AVL* tmp = this->FindMin(avl->rchild);
avl->data = tmp->data;
//删除右子树的最小结点
avl->rchild = this->Delete(avl->rchild,tmp->data);
}else{//当左右子树都为空或者有一个空时
AVL* tmp = avl;
if(!avl->lchild){//左子树为空时
avl = avl->rchild;
}else if(!avl->rchild){//右子树为空时
avl = avl->lchild;
}
delete tmp;
}
}
return avl;
}下面对依次把1,2,3,4,5插入到二叉平衡树中,并对相关操作进行验证。 全部代码如下:
#include <iostream>
using namespace std;
class AVL{
private:
int data; //结点的键值
int height; //结点的高度
AVL* lchild; //左孩子
AVL* rchild; //右孩子
public:
//查找最小值
AVL* FindMin(AVL* avl){
AVL* cur = avl;
//搜索树为空时,返回NULL
if(cur == NULL){
return NULL;
}
while(cur){
//左子树为空时,返回该节点
if(cur->lchild == NULL){
return cur;
}else{//否则在左子树里找最小值
cur = cur->lchild;
}
}
}
//查找最大值
AVL* FindMax(AVL* avl){
AVL* cur = avl;
//搜索树为空时,返回NULL
if(cur == NULL){
return NULL;
}
while(cur){
//右子树为空时,返回该节点
if(cur->rchild == NULL){
return cur;
}else{//否则在左子树里找最小值
cur = cur->rchild;
}
}
}
//插入函数
AVL* Insert(AVL* avl,int data){
//平衡二叉树为空,则构建根节点
if(!avl){
avl = new AVL;
avl->data = data;
avl->height = 0;
avl->lchild = avl->rchild = NULL;
}else if(data < avl->data){//若data小于根节点的值,则插入到左子树
avl->lchild = avl->Insert(avl->lchild,data);
int rheight = this->getHeight(avl->rchild); //右子树高度
int lheight = this->getHeight(avl->lchild); //左子树高度
//如果插入导致左子树失衡,即左子树比右子树高2
if(lheight - rheight == 2){
if(data <avl->lchild->data){
//插入的结点比左孩子的键值小
//那么一定是插入到左孩子的左子树上,故进行LL旋转
avl = this->SingleLeftRotation(avl);
}else{//否则是插入到左孩子的右子树上,故要进行LR旋转
avl = this->DoubleLeftRightRotation(avl);
}
}
}else if(data > avl->data){//若data小于根节点的值,则插入到左子树
avl->rchild = avl->Insert(avl->rchild,data);
int rheight = this->getHeight(avl->rchild); //右子树高度
int lheight = this->getHeight(avl->lchild); //左子树高度
//如果插入导致右子树失衡,即右子树比左子树高2
if(rheight - lheight == 2){
if(data > avl->rchild->data){
//插入的结点比右孩子的键值大
//那么一定是插入到右孩子的右子树上,故进行RR旋转
avl = this->SingleRightRotation(avl);
}else{//否则是插入到右孩子的左子树上,故要进行RL旋转
avl = this->DoubleRightLeftRotation(avl);
}
}
}
//更新结点的高度
avl->height = this->Max(this->getHeight(avl->lchild),this->getHeight(avl->rchild))+1;
return avl;
}
//二叉搜索树的构造,利用data数组构造二叉搜索树
AVL* Create(int* data,int size){
AVL* avl = NULL;
for(int i = 0 ; i < size ; i++){
avl = this->Insert(avl,data[i]);
}
return avl;
}
//删除操作
AVL* Delete(AVL* avl,int data){
if(!avl){//树空时,直接返回NULL
return avl;
}else if(data < avl->data){
//data小于根节点时,到左子树去删除data,则有可能使右子树比左子树高2
avl->lchild = this->Delete(avl->lchild,data);
int rheight = this->getHeight(avl->rchild); //右子树高度
int lheight = this->getHeight(avl->lchild); //左子树高度
if(rheight - lheight == 2){//右子树比左子树高2时
if(data > avl->rchild->data){
//如果是data比右子树的键值大,在右子树的右子树上,则进行RR旋转
avl = this->SingleRightRotation(avl);
}else{//否则是data比右子树的键值小,在右子树的左子树上,则进行RL旋转
avl = this->DoubleRightLeftRotation(avl);
}
}
}else if(data > avl->data){
//data大于根节点时,到右子树去删除data
avl->rchild = this->Delete(avl->rchild,data);
int rheight = this->getHeight(avl->rchild); //右子树高度
int lheight = this->getHeight(avl->lchild); //左子树高度
if(lheight - rheight == 2){//左子树比右子树高2时
if(data < avl->lchild->data){
//如果是data比左子树的键值小,在左子树的左子树上,则进行LL旋转
avl = this->SingleLeftRotation(avl);
}else{//否则是data比左子树的键值大,在左子树的右子树上,则进行LR旋转
avl = this->DoubleLeftRightRotation(avl);
}
}
}else{//data等于根节点时
if(avl->lchild && avl->rchild){
//左右子树都不空时,用右子树的最小来代替根节点
AVL* tmp = this->FindMin(avl->rchild);
avl->data = tmp->data;
//删除右子树的最小结点
avl->rchild = this->Delete(avl->rchild,tmp->data);
}else{//当左右子树都为空或者有一个空时
AVL* tmp = avl;
if(!avl->lchild){//左子树为空时
avl = avl->rchild;
}else if(!avl->rchild){//右子树为空时
avl = avl->lchild;
}
delete tmp;
}
}
return avl;
}
//单左旋:左左旋函数
//左子树的左子树导致的失衡,把左子树与根结点进行调整
//根结点的左孩子做根结点,之前的根结点做现在根结点的右孩子
//这是因为平衡二叉树一定是二叉搜索树的缘故导致的
AVL* SingleLeftRotation(AVL* avl){
//注意:avl必须有一个左子结点tmp
//将avl与tmp做左单旋,更新avl与tmp的高度,返回新的根结点tmp
AVL* tmp = avl->lchild;
avl->lchild = tmp->rchild;
tmp->rchild = avl;
avl->height = this->Max(this->getHeight(avl->lchild),this->getHeight(avl->rchild))+1;
tmp->height = this->Max(this->getHeight(tmp->lchild),this->getHeight(avl))+1;
return tmp;
}
//单右旋:右右旋函数
//右子树的右子树导致的失衡,把右子树与根结点进行调整
//根结点的右孩子做根结点,之前的根结点做现在根结点的左孩子
//这是因为平衡二叉树一定是二叉搜索树的缘故导致的
AVL* SingleRightRotation(AVL* avl){
//注意:avl必须有一个右子结点tmp
//将avl与tmp做右单旋,更新avl与tmp的高度,返回新的根结点tmp
AVL* tmp = avl->rchild;
avl->rchild = tmp->lchild;
tmp->lchild = avl;
avl->height = this->Max(this->getHeight(avl->lchild),this->getHeight(avl->rchild))+1;
tmp->height = this->Max(this->getHeight(tmp->rchild),this->getHeight(avl))+1;
return tmp;
}
//左右旋转:LR旋转,左子树的右子树插入导致对的失衡
AVL* DoubleLeftRightRotation(AVL* avl){
//注意:avl必须有一个左子结点B,且B必须有一个右子结点C
//将avl、B与C做两次单旋,返回新的根结点C
//首先对avl的左子树进行单右旋即RR旋转
avl->lchild = this->SingleRightRotation(avl->lchild);
//然后对avl进行单左旋即LL旋转
return this->SingleLeftRotation(avl);
}
//右左旋转:RL旋转,右子树的左子树插入导致对的失衡
AVL* DoubleRightLeftRotation(AVL* avl){
//注意:avl必须有一个左子结点B,且B必须有一个右子结点C
//将avl、B与C做两次单旋,返回新的根结点C
//首先对avl的右子树进行单左旋即LL旋转
avl->rchild = this->SingleLeftRotation(avl->rchild);
//然后对avl进行单右旋即RR旋转
return this->SingleRightRotation(avl);
}
//获得树的高度
int getHeight(AVL* avl){
if(!avl){
return 0;
}
return avl->height;
}
//求两个数的最大值
int Max(int a,int b){
return (a>b)?a:b;
}
//递归前序遍历
void PreorderTraversal(AVL* T){
if(T == NULL){
return;
}
cout<<T->data<<" "; //访问根节点并输出
T->PreorderTraversal(T->lchild); //递归前序遍历左子树
T->PreorderTraversal(T->rchild); //递归前序遍历右子树
}
//递归中序遍历
void InorderTraversal(AVL* T){
if(T == NULL){
return;
}
T->InorderTraversal(T->lchild); //递归中序遍历左子树
cout<<T->data<<" "; //访问根节点并输出
T->InorderTraversal(T->rchild); //递归中序遍历左子树
}
//递归后序遍历
void PostorderTraversal(AVL* T){
if(T == NULL){
return;
}
T->PostorderTraversal(T->lchild); //递归后序遍历左子树
T->PostorderTraversal(T->rchild); //递归后序遍历右子树
cout<<T->data<<" "; //访问并打印根节点
}
int getdata(AVL* avl){
return avl->data;
}
};
int main()
{
int size;
cout<<"请输入结点个数:"<<endl;
cin>>size;
int* data;
data = new int[size];
cout<<"请输入每个结点的值:"<<endl;
for(int i = 0 ; i < size ; i++){
cin>>data[i];
}
AVL* avl;
avl = new AVL;
avl = avl->Create(data,size);
cout<<"前序遍历(递归):"<<endl;
avl->PreorderTraversal(avl);
cout<<endl;
cout<<"中序遍历(递归):"<<endl;
avl->InorderTraversal(avl);
cout<<endl;
cout<<"后序遍历(递归):"<<endl;
avl->PostorderTraversal(avl);
cout<<endl;
AVL* avl_max;
avl_max = avl->FindMax(avl);
cout<<"二叉搜索树的最大值为:"<<endl;
cout<<avl_max->getdata(avl_max);
cout<<endl;
cout<<"二叉搜索树的最小值为:"<<endl;
AVL* avl_min;
avl_min = avl->FindMin(avl);
cout<<avl_min->getdata(avl_min);
cout<<endl;
int num;
cout<<"请输入要删除的结点:"<<endl;
cin>>num;
avl = avl->Delete(avl,num);
cout<<"删除之后:"<<endl;
cout<<"前序遍历(递归):"<<endl;
avl->PreorderTraversal(avl);
cout<<endl;
cout<<"中序遍历(递归):"<<endl;
avl->InorderTraversal(avl);
cout<<endl;
cout<<"后序遍历(递归):"<<endl;
avl->PostorderTraversal(avl);
cout<<endl;
cout<<"请输入要删除的结点:"<<endl;
cin>>num;
avl = avl->Delete(avl,num);
cout<<"删除之后:"<<endl;
cout<<"前序遍历(递归):"<<endl;
avl->PreorderTraversal(avl);
cout<<endl;
cout<<"中序遍历(递归):"<<endl;
avl->InorderTraversal(avl);
cout<<endl;
cout<<"后序遍历(递归):"<<endl;
avl->PostorderTraversal(avl);
cout<<endl;
cout<<"请输入要删除的结点:"<<endl;
cin>>num;
avl = avl->Delete(avl,num);
cout<<"删除之后:"<<endl;
cout<<"前序遍历(递归):"<<endl;
avl->PreorderTraversal(avl);
cout<<endl;
cout<<"中序遍历(递归):"<<endl;
avl->InorderTraversal(avl);
cout<<endl;
cout<<"后序遍历(递归):"<<endl;
avl->PostorderTraversal(avl);
cout<<endl;
return 0;
} 截图如下:
