平衡二叉树是一种二叉排序树,其中每一个节点的左子树和右子树的高度差不会大于
1。平衡二叉树的产生是为了解决二叉树的退化的,众所周知,二叉树之所以被广泛使用,因为二叉树具有良好的查找性能,但是在数据排列不合理的情况下,二树的这种性能就会得到退化,例如,以元素
35,37,47,51,58,62,73,88,93,99 去建立一颗二叉树,就会得到这样的一棵二叉树

        这样的二叉树就退化成一个链表,查找的最大时间复杂度变成了 O(n),显然已经违背了我们的意愿,我们希望建立的二叉树应该为
 

         
这样的二叉树才符合二分查找的思想,能够在最短时间内完成查找,但是我们怎么才能让程序自动去帮我们生成一个这样的二叉树呢,下面我们就来一起通过程序去熟悉平衡二叉树的建立。

不平衡处理
        当二叉树出现不平衡时,有四种不平衡的情况,分别如下 LL 型不平衡 RR 型不平衡
 
LR 型不平衡 RL 型不平衡
 

LL 型不平衡处理
        LL 型不平衡是因为节点的左孩子插入一个左孩子引发的左偏不平衡,可以看到 A的左子树高度比右子树高度多了
2,形成左长右短的不平衡,处理这种不平衡,只需要使这个不平衡的子树右旋转就行了,俗称右旋操作。

案例:

 
        备注:很多人认为如果新插入节点在 2 节点的右孩子处就是 LR 型不平衡了,其实不是,还是 LL
型不平衡,因为当节点插入进来时,不平衡的节点是 5,新插入的节点不管在2 节点的左还是右都是相对于 5 节点还是左孩子的左孩子上引发的不平衡,所以还是LL
型不平衡,只有插入位置在 4 节点上时才会是 LR 型不平衡,下面就不解释了
 简单程序示例:
BTNode *ll_rotate(BTNode *y) { BTNode *x = y->left; //定义一个节点保存不平衡节点的左孩子
y->left = x->right; //不平衡节点的左孩子现在指向原左孩子的右孩子 x->right = y;
//不平衡节点的左孩子的右孩子指向不平衡节点 //更新变化节点的高度 y->height = max(height(y->left),
height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1;
return x; //返回新的平衡子树根节点 }
RR 型不平衡处理
        RR 型不平衡是因为节点的右孩子插入一个右孩子引发的右偏不平衡,可以看到 A的右子树高度比左子树高度多了
2,形成左短右长的不平衡,处理这种不平衡,只需要使这个不平衡的子树左旋转就行了,俗称左旋操作。

案例:  

简单程序示例:
BTNode *rr_rotate(struct Node *y) { BTNode *x = y->right; //保存不平衡节点的右孩子
y->right = x->left; //不平衡节点的右孩子指向不平衡节点右孩子的左孩子 x->left = y;
//不平衡节点右孩子的左孩子指向不平衡节点 //更新变化节点高度 y->height = max(height(y->left),
height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1;
return x; //返回新的平衡子树根节点 }
 LR 型不平衡处理
        LR 型不平衡是因为节点的左孩子插入一个右孩子引发的不平衡,处理这种不平衡,只需要让不平衡节点的左节点左旋转,然后形成 LL
型不平衡,再对不平衡节点进行右旋转就能解决。

案例:
 简单程序示例:
BTNode* lr_rotate(BTNode* y) { BTNode* x = y->left; //指向不平衡节点的左孩子 y->left =
rr_rotate(x); //让不平衡节点左孩子左旋处理形成 LL 不平衡 return ll_rotate(y); //然后不平衡节点右旋处理 }  
RL 型不平衡处理
        RL 型不平衡是因为节点的右孩子插入一个左孩子引发的不平衡,处理这种不平衡,只需要让不平衡节点的右节点右旋转,然后形成 RR
型不平衡,再对不平衡节点进行左旋转就能解决。

案例: 简单程序示例:  
Node* rl_rotate(Node* y) { Node * x = y->right; //保存不平衡节点的右孩子 y->right =
ll_rotate(x); //让右孩子右旋处理得到 RR 型不平衡 return rr_rotate(y); //不平衡节点左旋处理 }
整体设计示例

AVL 树节点结构设计示例
typedef char TYPE; typedef struct tnode { TYPE date; //节点元素 int height; //节点深度
struct tnode *lchild; //左子树 struct tnode *rchild; //右子树 }TNode;
建立 AVL 树设计示例
/** * @brief 向平衡二叉树中插入元素 * * @param t 平衡二叉树根节点指针 * @param x 插入元素 * @return
TNode* 返回经过平衡处理后的新根节点 */ TNode* establish_balance_tree(TNode *t,TYPE x) {
if(t==NULL) //如果根节点为空,说明首次插入 { TNode *t=(TNode*)malloc(sizeof(TNode)); //建立节点
t->date=x; t->lchild=t->rchild=NULL; t->height=1; return t; } if(x>t->date)
//如果插入元素大于根节点元素,则右边插入 { t->rchild=establish_balance_tree(t->rchild,x);
//递归寻找插入位置 if(t->rchild->height>=t->height) //更新节点高度
t->height=t->rchild->height+1; if(Height_Poor(t->lchild,t->rchild))
//判断该节点左右子树高度是否不平衡,如果不平衡的话 { if(x>t->rchild->date) //如果插入位置在不平衡节点的右节点的右边 {
t=SingleRotateWithLeft(t); //为 RR 型不平衡,进行单向左旋平衡处理 return t; } else
//否则插入位置在不平衡节点的右节点的左边 { t=DoubleRotateRightLeft(t); //为 RL
型不平衡,进行双向旋转(先右后左)平衡处理 return t; } } return t; } else //否则插入元素小于根节点元素,插入在左边 {
t->lchild=establish_balance_tree(t->lchild,x); //递归寻找插入位置
if(t->lchild->height>=t->height) //更新节点高度 t->height=t->lchild->height+1;
if(Height_Poor(t->lchild,t->rchild)) //判断该节点左右子树高度是否不平衡,如果不平衡的话 {
if(x<t->lchild->date) //如果插入位置在不平衡节点的左节点的左边 { t=SingleRotateWithRight(t); //为
LL 型不平衡,进行单向右旋平衡处理 return t; } else //否则插入位置在不平衡节点的左节点的右边 {
t=DoubleRotateLeftRight(t); //为 LR 型不平衡,进行双向旋转(先左后右)平衡处理 return t; } } return
t; } }
函数使用示例:

 

技术
今日推荐
阅读数 169685
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信