4.平衡二叉树
1.平衡二叉树
1.1概述
平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树，它的每个节点的左右子树的高度差的绝对值不超过 1，并且左右子树也都是平衡二叉树。这意味着所有的平衡二叉树都必然是二叉搜索树，但并非所有的二叉搜索树都是平衡二叉树。平衡二叉树的主要目的是避免二叉搜索树（BST）在极端情况下退化为链表，从而保证查找、插入和删除操作的时间复杂度为 O(logn)。
常见的平衡二叉树包括：
AVL 树（严格平衡）：通过旋转操作保持平衡。
红黑树（相对平衡）：通过颜色标记和旋转操作保持平衡。
AVL树，通过在插入和删除操作时进行旋转操作来保持树的平衡，确保树的高度始终维持在对数级别，从而保证了各种操作（如查找、插入、删除）具有 O(logn) 的时间复杂度。
1.2平衡因子
平衡因子 = 左子树高度 - 右子树高度
AVL 树要求每个节点的平衡因子的绝对值不超过 1，也就是平衡因子只能取 -1、0 或 1。
1.3旋转操作
要将一棵普通的二叉搜索树（BST）转换为平衡的 AVL 树，可以通过以下几个关键步骤来实现，主要思路是在 BST 的基础上，对不满足平衡条件（节点平衡因子绝对值大于 1）的节点进行旋转操作，使得树重新达到平衡状态。要有四种旋转情况：
LL情况（左左情况）
10 (失衡节点)
/
5
/
2
右旋
5
/ \
2 10
RR 情况（右右情况）
10 (失衡节点)
\
15
\
20
左旋
15
/ \
10 20
LR 情况（左右情况）
10 (失衡节点)
/
5
\
7
对节点 5 进行左旋：
10
/
7
/
5
对节点 10 进行右旋：
7
/ \
5 10
RL 情况（右左情况）
10 (失衡节点)
\
15
/
12
对节点 15 进行右旋：
10
\
12
\
15
对节点 10 进行左旋：
12
/ \
10 15
2.AVL树的实现
2.1节点的定义
首先我们需要定义了一个名为 AVLNode 的结构体，用于表示 AVL 树（一种自平衡的二叉搜索树）中的节点。
struct AVLNode
{
int val;//存储节点数据，类型为 int
int height;//记录以当前节点为根的子树的高度，用于计算平衡因子
AVLNode* left;//指向当前节点的左子节点
AVLNode* right;//指向当前节点的右子节点
AVLNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {}
};
2.2定义AVL树类
下面我们定义一个AVL树类，并且为这个类提供节点的插入、删除和中序遍历功能。
点击查看代码
class AVLTree
{
public:
AVLTree();/* 构造函数 */
~AVLTree();/* 析构函数 */
bool insert(int value);/* 插入节点 */
bool remove(int value);/* 删除节点 */
void inorder();/* 中序遍历 */
private:
int height(AVLNode* root);/* 获取节点高度 */
int balance(AVLNode* root);/* 获取节点平衡因子 */
AVLNode* rightRotate(AVLNode* root);/* 右旋转 */
AVLNode* leftRotate(AVLNode* root);/* 左旋转 */
AVLNode* rotate(AVLNode* root);/* 旋转操作 */
void inorder(AVLNode* root);/* 中序遍历辅助函数 */
AVLNode* insert(AVLNode* root, int value);/* 插入节点辅助函数 */
AVLNode* remove(AVLNode* root, int value);/* 删除节点辅助函数 */
private:
// 根节点
AVLNode* m_root;
};
##2.3类的API实现
###2.3.1构造和析构
点击查看代码
/* AVL 树的构造函数 */
AVLTree::AVLTree() : m_root(nullptr)
{
}
/* AVL 树的析构函数 */
AVLTree::~AVLTree()
{
clear(m_root);
}
/* 释放节点 */
void AVLTree::clear(AVLNode* root)
{
if (root == nullptr)
{
return;
}
clear(root->left);/* 递归释放左子树 */
clear(root->right);/* 递归释放右子树 */
cout << "释放节点: " << root->val << endl;
delete root;
}
###2.3.2计算平衡因子
点击查看代码
/* 获取节点高度 */
int AVLTree::height(AVLNode* root)
{
return root ? root->height : 0;
}
/* 获取节点平衡因子 */
int AVLTree::balance(AVLNode* root)
{
return root ? height(root->left) - height(root->right) : 0;
}
###2.3.3左旋
左旋操作主要用于处理 RR（右右）型失衡，当某个节点的右子树高度比左子树高度大 2 且右子节点的平衡因子为 -1 或 0 时，需要进行左旋操作来恢复树的平衡。
点击查看代码
/* 左旋转 */
AVLNode* AVLTree::leftRotate(AVLNode* root)
{
AVLNode* right = root->right;/* 右子节点 */
AVLNode* child = right->left;/* 右子节点的左子节点 */
right->left = root;/* 右子节点的左子节点指向根节点 */
root->right = child;/* 根节点的右子节点指向右子节点的左子节点 */
root->height = std::max(height(root->left), height(root->right)) + 1;/* 更新根节点高度 */
right->height = std::max(height(right->left), height(right->right)) + 1;/* 更新右子节点高度 */
return right;
}
###2.3.4右旋
点击查看代码
/* 右旋转 */
AVLNode* AVLTree::rightRotate(AVLNode* root)
{
AVLNode* left = root->left;/* 左子节点 */
AVLNode* child = left->right;/* 左子节点的右子节点 */
left->right = root;/* 左子节点的右子节点指向根节点 */
root->left = child;/* 根节点的左子节点指向左子节点的右子节点 */
root->height = std::max(height(root->left), height(root->right)) + 1;/* 更新根节点高度 */
left->height = std::max(height(left->left), height(left->right)) + 1;/* 更新左子节点高度 */
return left;
}
###2.3.5将当前树旋转为一颗AVL树
rotate 函数会根据节点的平衡因子和其子节点的平衡因子，判断当前树的不平衡类型（LL、LR、RR、RL），并执行相应的旋转操作来恢复平衡。
点击查看代码
/* 将当前树旋转为一棵AVL树 */
AVLNode* AVLTree::rotate(AVLNode* root)
{
int curBalance = balance(root);/* 当前节点的平衡因子 */
if (curBalance > 1 && balance(root->left) >= 0)/* 左-左情况 */
{
return rightRotate(root);/* 右旋转 */
}
if (curBalance > 1 && balance(root->left) < 0)/* 左-右情况 */
{
root->left = leftRotate(root->left);/* 先左旋转左子节点 */
return rightRotate(root);/* 再右旋转根节点 */
}
if (curBalance < -1 && balance(root->right) <= 0)/* 右-右情况 */
{
return leftRotate(root);/* 左旋转 */
}
if (curBalance < -1 && balance(root->right) > 0)/* 右-左情况 */
{
root->right = rightRotate(root->right);/* 先右旋转右子节点 */
return leftRotate(root);/* 再左旋转根节点 */
}
return root;
}
###2.3.6插入
AVL 树是一种自平衡的二叉搜索树，插入操作不仅要遵循二叉搜索树的插入规则，还要在插入后通过旋转操作来保证树的平衡性，使得树的左右子树高度差不超过 1，从而保证树的查找、插入和删除操作的时间复杂度始终保持在 O(logn)。
点击查看代码
/* 外部插入节点函数 */
bool AVLTree::insert(int value)
{
m_root = insert(m_root, value);
return m_root != nullptr;
}
/* 内部插入节点函数 */
AVLNode* AVLTree::insert(AVLNode* root, int value)
{
// 空树
if (root == nullptr)
{
return new AVLNode(value);
}
if (value < root->val)/* 插入左子树 */
{
root->left = insert(root->left, value);
}
else if (value > root->val)/* 插入右子树 */
{
root->right = insert(root->right, value);
}
else/* 已存在该节点 */
{
return root;
}
root->height = std::max(height(root->left), height(root->right)) + 1;/* 更新节点高度 */
return rotate(root);/* 旋转为AVL树 */
}
#2.3.7删除
和插入操作类似，删除操作不仅要遵循二叉搜索树的删除规则，还要在删除节点后通过旋转操作来保证树的平衡性，以维持 AVL 树高效的查找、插入和删除性能（时间复杂度保持在 O(logn)）。
点击查看代码
/* 外部删除节点函数 */
bool AVLTree::remove(int value)
{
return remove(m_root, value);
}
/* 内部删除节点函数 */
AVLNode* AVLTree::remove(AVLNode* root, int value)
{
if (root == nullptr)
{
return root;
}
if (value < root->val)/* 在左子树中删除节点 */
{
root->left = remove(root->left, value);
}
else if (value > root->val)/* 在右子树中删除节点 */
{
root->right = remove(root->right, value);
}
else/* 找到要删除的节点 */
{
if (root->left == nullptr || root->right == nullptr)/* 只有一个子节点或没有子节点 */
{
AVLNode* node = root->left ? root->left : root->right;/* 获取非空子节点 或 都是空节点*/
if (node == nullptr)/* 没有子节点 */
{
node = root;/* 保存要删除的节点 */
root = nullptr;/* 删除节点后变为空树 */
}
else/* 只有一个子节点 */
{
*root = *node;/* 用子节点覆盖当前节点 */
}
delete node;/* 释放节点 */
}
else/* 有两个子节点 */
{
AVLNode* current = root->right;/* 找到右子树的最小节点 */
while (current->left != nullptr)/* 一直往左走 */
{
current = current->left;
}
root->val = current->val;/* 用右子树的最小节点覆盖当前节点 */
root->right = remove(root->right, current->val);/* 删除右子树的最小节点 */
}
}
if (root == nullptr)/* 删除后变为空树 */
{
return root;
}
root->height = std::max(height(root->left), height(root->right)) + 1;/* 更新节点高度 */
return rotate(root);/* 旋转为AVL树 */
}
###2.3.8中序遍历
点击查看代码
/* 外部中序遍历函数 */
void AVLTree::inorder(AVLNode* root)
{
if (root == nullptr)
{
return;
}
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}