©2020-2024 ioDraw All rights reserved,
Privacy Policy
平衡二叉树是一种二叉排序树，其中每一个节点的左子树和右子树的高度差不会大于
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; } }
函数使用示例：