总结
-
什么是平衡二叉树：
- 基于二叉排序树
- 左右子树的深度之差的绝对值不超过1
- 左右子树都是平衡二叉树
-
为什么要修改二叉排序树为平衡二叉树：因为查找二叉树的比较次数和层数有关
-
在构造二叉排序树的过程中，会出现四种失衡现象
-
如何进行调整：找到最小不平衡子树，将其调平衡
- 最小不平衡子树：离插入节点最近且平衡因子绝对值超过1的结点，以这个结点为根节点的子树
-
LL型：右旋，原本橙点是root，右旋后，绿点是root，橙点为绿点的right
- 注意：绿点的right可能有结点，所以要用橙点的left接上
- 以上图第三个为例
-
RR型：左旋，原本橙点是root，左旋后，绿点是root，橙点为绿点的left
- 注意：绿点的left可能有结点，所以要用橙点的right接上
- 以上图第三个为例
-
LR型：双旋，先对绿点（LL中的橙点）和蓝点（LL中的绿点）进行RR左旋，在对橙点进行LL右旋
- 解释：左旋使LR型变为LL型，右旋使LL型平衡
- 注意：对两个点也能进行RR左旋
-
RL型：和LR型对称操作
代码思路
- 注意过程中要对树进行操作的函数的参数一定要传入指针的引用
- 递归插入结点insert
- 如果curr为空，即找到最终位置，申请内存新建节点
- 如果传入参数num小于当前结点的data，递归进入左子树
- 如果传入参数num大于当前节点的data，递归进入右子树
- 插入结点后，就要退出递归，进行平衡因子的更新
- 通过getHeight即可得到左子树和右子树的高度
- 若平衡因子<1，继续退出递归
- 若平衡因子>1，即不平衡，就要判断不平衡的类型了
- 由第一张图可得，RX型橙点-2，LX型橙点2
- RL型绿点1，RR型绿点-1，LR型绿点-1，LL型绿点1
- 每个类型都有自己的特征，进入if判断
- 右旋要注意绿点的right，左旋要注意绿点的left
- 插入节点后和调平衡后，要更新改变过的结点的高度，绿点和橙点
代码
#include <iostream>
#include <vector>
using namespace std;
struct treeNode {
int data;
int height;
treeNode* left, * right;
};
//中序遍历
void inorderTra(treeNode* curr) {
if (!curr) return;
inorderTra(curr->left);
cout << curr->data << " ";
inorderTra(curr->right);
}
//递归获取高度
int getHeight(treeNode* curr) {
if (!curr) return -1;
return curr->height;
}
//LL型，右旋单旋
treeNode* LL(treeNode*& curr) {
treeNode* leftNode = curr->left;
curr->left = leftNode->right;
leftNode->right = curr;
curr = leftNode;
curr->height = max(getHeight(curr->left), getHeight(curr->right)) + 1;
//可能为空，但不为空要重新判断高度
if(curr->left) curr->left->height = max(getHeight(curr->left->left), getHeight(curr->left->right)) + 1;
return curr;
}
//RR型，左旋单旋
treeNode* RR(treeNode*& curr) {
treeNode* rightNode = curr->right;
curr->right = rightNode->left;
rightNode->left = curr;
curr = rightNode;
curr->height = max(getHeight(curr->left), getHeight(curr->right)) + 1;
//可能为空，但不为空要重新判断高度
if(curr->right) curr->right->height = max(getHeight(curr->right->left), getHeight(curr->right->right)) + 1;
return curr;
}
//LR型，先对左子树右旋再左旋
treeNode* LR(treeNode*& curr) {
RR(curr->left);
return LL(curr);
}
//RL型，先对右子树左旋再右旋
treeNode* RL(treeNode*& curr) {
LL(curr->right);
return RR(curr);
}
//插入叶子结点，递归
//注意使用指针的引用
void insert(int num, treeNode*& curr) {
//如果为空，即找到了叶子结点的位置，分配空间
if (!curr) {
curr = new treeNode();
curr->data = num;
curr->left = NULL;
curr->right = NULL;
}
//如果数字比当前结点的值小，即进入当前结点的左子树继续判断
else if (num < curr->data) {
insert(num, curr->left);
//递归出来后，要判断平衡因子，决定是否调平衡
if (getHeight(curr->left) - getHeight(curr->right) == 2) {
//如果上面递归是进入了左子树的左子树，则是LL型
if (num < curr->left->data) curr = LL(curr);
//如果进入左子树的右子树，则是LR型
else curr = LR(curr);
}
}
//如果数字比当前节点的值大，即进入当前节点的右子树继续判断
else if (num > curr->data) {
insert(num, curr->right);
//递归出来后，要判断平衡因子，决定是否调平衡
if (getHeight(curr->left) - getHeight(curr->right) == -2) {
//如果上面递归是进入了右子树的右子树，则是RR型
if (num > curr->right->data) curr = RR(curr);
//如果进入右子树的左子树，则是RL型
else curr = RL(curr);
}
}
curr->height = max(getHeight(curr->left), getHeight(curr->right)) + 1;
}
void createTree(vector<int> v, treeNode*&pRoot) {
for (int i = 0; i < v.size(); i++) {
insert(v[i], pRoot);
}
//中序遍历，平衡二叉树是特殊的二叉排序树
inorderTra(pRoot);
}
int main() {
vector<int> v = { 49,38,65,97,76,13,27 };
treeNode* pRoot = NULL;
createTree(v,pRoot);
return 0;
}