平衡二叉树

苏丙榅2025-02-182025-02-20

1. 平衡二叉树

1.1 概述

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树，它的每个节点的左右子树的高度差的绝对值不超过 1，并且左右子树也都是平衡二叉树。这意味着所有的平衡二叉树都必然是二叉搜索树，但并非所有的二叉搜索树都是平衡二叉树。平衡二叉树的主要目的是避免二叉搜索树（BST）在极端情况下退化为链表，从而保证查找、插入和删除操作的时间复杂度为 O(log⁡n)。

常见的平衡二叉树包括：

AVL 树（严格平衡）：通过旋转操作保持平衡。
红黑树（相对平衡）：通过颜色标记和旋转操作保持平衡。

AVL 树的全称是“Adelson-Velsky and Landis Tree”，它以苏联数学家 Georgy Adelson - Velsky 和 Evgenii Landis 的名字命名。这两位数学家在 1962 年的论文中首次提出了这种自平衡的二叉搜索树结构，通过在插入和删除操作时进行旋转操作来保持树的平衡，确保树的高度始终维持在对数级别，从而保证了各种操作（如查找、插入、删除）具有 O(log⁡n) 的时间复杂度。

1.2 平衡因子

AVL 树的每个节点都有一个平衡因子（Balance Factor），其定义为：

1	平衡因子 = 左子树高度 - 右子树高度

AVL 树要求每个节点的平衡因子的绝对值不超过 1，也就是平衡因子只能取 -1、0 或 1。

示例 1：平衡因子都为 0 的 AVL 树
1
2
3
4
5
5(0)
/ \
3(0) 7(0)
/ \ / \
2(0) 4(0) 6(0) 8(0)
各节点的平衡因子计算：
1. 节点 2：左子树高度为 0，右子树高度为 0，平衡因子 = 0 - 0 = 0。
2. 节点 4：左子树高度为 0，右子树高度为 0，平衡因子 = 0 - 0 = 0。
3. 节点 3：左子树（节点 2）高度为 1，右子树（节点 4）高度为 1，平衡因子 = 1 - 1 = 0。
4. 节点 6：左子树高度为 0，右子树高度为 0，平衡因子 = 0 - 0 = 0。
5. 节点 8：左子树高度为 0，右子树高度为 0，平衡因子 = 0 - 0 = 0。
6. 节点 7：左子树（节点 6）高度为 1，右子树（节点 8）高度为 1，平衡因子 = 1 - 1 = 0。
7. 节点 5：左子树（以节点 3 为根）高度为 2，右子树（以节点 7 为根）高度为 2，平衡因子 = 2 - 2 = 0。
示例 2：包含平衡因子为 -1 和 1 的 AVL 树
1
2
3
4
5
8(0)
/ \
4(1) 12(-1)
/ \
2(0) 14(0)
各节点的平衡因子计算：
1. 节点 2：左子树高度为 0，右子树高度为 0，平衡因子 = 0 - 0 = 0。
2. 节点 4：左子树（节点 2）高度为 1，右子树高度为 0，平衡因子 = 1 - 0 = 1。
3. 节点 14：左子树高度为 0，右子树高度为 0，平衡因子 = 0 - 0 = 0。
4. 节点 12：左子树高度为 0，右子树（节点 14）高度为 1，平衡因子 = 0 - 1 = -1。
5. 节点 8：左子树（以节点 4 为根）高度为 2，右子树（以节点 12 为根）高度为 2，平衡因子 = 2 - 2 = 0。
示例 3：平衡因子为 -2 的 BST 树，不是 AVL 树
1
2
3
4
5
10(-2)
/ \
5(0) 20(0)
/ \
15(0) 30(0)
各节点的平衡因子计算：
1. 节点 5：左子树高度为 0，右子树高度为 0，平衡因子 = 0 - 0 = 0。
2. 节点 15：左子树高度为 0，右子树高度为 0，平衡因子 = 0 - 0 = 0。
3. 节点 30：左子树高度为 0，右子树高度为 0，平衡因子 = 0 - 0 = 0。
4. 节点 20：左子树（节点 15）高度为 1，右子树（节点 30）高度为 1，平衡因子 = 1 - 1 = 0。
5. 节点 10：左子树（节点 5）高度为 1，右子树（以节点 15 为根的子树和节点 20 及其子树共同构成右子树部分）高度为 3，平衡因子 = 1 - 3 = -2。

1.3 旋转操作

要将一棵普通的二叉搜索树（BST）转换为平衡的 AVL 树，可以通过以下几个关键步骤来实现，主要思路是在 BST 的基础上，对不满足平衡条件（节点平衡因子绝对值大于 1）的节点进行旋转操作，使得树重新达到平衡状态。要有四种旋转情况：

LL情况（左左情况）

在某个节点的左子树的左子树上插入新节点，导致该节点的平衡因子大于 1。例如，插入顺序为 10 -> 5 -> 2，导致节点 10 的平衡因子为 2。

     10 (失衡节点)
    /
   5
  /
2

解决上面的失衡问题需要对树进行右旋，具体步骤如下：

以失衡节点（10）为轴，进行右旋。
将失衡节点的左子节点（5）提升为新的根节点。
失衡节点（10）成为新根节点的右子节点。
如果新根节点（5）原本有右子节点（T2），则将其挂到失衡节点（10）的左子节点。

1
2
3

  5
 / \
2  10

RR 情况（右右情况）

在某个节点的右子树的右子树上插入新节点，导致该节点的平衡因子小于 -1。例如，插入顺序为 10 -> 15 -> 20，导致节点 10 的平衡因子为 -2。

10 (失衡节点)
 \
  15
    \
     20

解决上面的失衡问题需要对树进行左旋，具体步骤如下：

以失衡节点（10）为轴，进行左旋。
将失衡节点的右子节点（15）提升为新的根节点。
失衡节点（10）成为新根节点的左子节点。
如果新根节点（15）原本有左子节点（T2），则将其挂到失衡节点（10）的右子节点。

1
2
3

   15
  /  \
10   20

LR 情况（左右情况）

在某个节点的左子树的右子树上插入新节点，导致该节点的平衡因子大于 1。例如，插入顺序为 10 -> 5 -> 7，导致节点 10 的平衡因子为 2。

  10 (失衡节点)
 /
5
 \
  7

解决上面的失衡问题需要对树进行的操作是先左旋后右旋，具体步骤如下：

对失衡节点的左子节点（5）进行左旋，将 LR 情况转换为 LL 情况。
对失衡节点（10）进行右旋。

对节点 5 进行左旋：

对节点 10 进行右旋：

1
2
3

  7
 / \
5  10

RL 情况（右左情况）

在某个节点的右子树的左子树上插入新节点，导致该节点的平衡因子小于 -1。例如，插入顺序为 10 -> 15 -> 12，导致节点 10 的平衡因子为 -2。

10 (失衡节点)
 \
  15
 /
12

解决上面的失衡问题需要对树进行的操作是先右旋后左旋，具体步骤如下：

对失衡节点的右子节点（15）进行右旋，将 RL 情况转换为 RR 情况。
对失衡节点（10）进行左旋。

对节点 15 进行右旋：

对节点 10 进行左旋：

1
2
3

   12
  /  \
10   15

2. AVL树的实现

2.1 节点的定义

首先我们需要定义了一个名为 AVLNode 的结构体，用于表示 AVL 树（一种自平衡的二叉搜索树）中的节点。

struct AVLNode 
{
    int val;
    int height;
    AVLNode* left;
    AVLNode* right;
    AVLNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {}
};

结构体中各成员的作用如下:

val：存储节点数据，类型为 int
height：记录以当前节点为根的子树的高度，用于计算平衡因子
left：指向当前节点的左子节点
right：指向当前节点的右子节点

2.2 定义AVL树类

下面我们定义一个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;
};

int height(AVLNode* root)：计算树的高度
int balance(AVLNode* root)：计算平衡因子
AVLNode* rightRotate(AVLNode* root)：右旋函数
- 参数：失衡节点
- 返回值：旋转之后的这棵树的根节点
AVLNode* leftRotate(AVLNode* root)：
- 参数：失衡节点
- 返回值：旋转之后的这棵树的根节点
AVLNode* rotate(AVLNode* root)：将当前树旋转为一棵AVL树

2.3 类的API实现

构造和析构

AVLTree::AVLTree() : m_root(nullptr)
{
}

AVLTree::~AVLTree()
{
    clear(m_root);
}

void AVLTree::clear(AVLNode* root)
{
    if (root == nullptr)
    {
        return;
    }
    clear(root->left);
    clear(root->right);
    cout << "释放节点: " << root->data << endl;
    delete root;
}

void AVLTree::clear(AVLNode* root)：递归地删除 AVL 树中的所有节点，并释放它们占用的内存。

如果使用递归的方式对二叉树中的节点进行释放，使用的遍历方式一定是后序遍历：释放左子树 -> 释放右子树 -> 释放根节点。

计算平衡因子

通过平衡因子可以判断当前的二叉树是否已经失衡，它的有效值为 -1、0 或 1。在程序中计算平衡因子值的时候需要知道以当前节点为根节点的这棵子树的高度。

int AVLTree::height(AVLNode* root)
{
    return root ? root->height : 0;
}

int AVLTree::balance(AVLNode* root)
{
    return root ? height(root->left) - height(root->right) : 0;
}

左旋

左旋操作主要用于处理 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; 
}

AVLNode* right = root->right;：把 root 节点的右子节点存储在 right 指针中。
AVLNode* child = right->left;：将 right 节点的左子节点存储在 child 指针里。
right->left = root;：把 root 节点作为 right 节点的左子节点。
root->right = child;：将 child 节点作为 root 节点的右子节点。

旋转完毕之后root成为了right的子节点，所有在更新节点高度的时候应该先计算root再计算right。

通过上述操作，完成了左旋的结构调整。返回该子树的新根节点 right。

右旋

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; 
}

AVLNode* left = root->left;：将 root 节点的左子节点存储在 left 指针中。
AVLNode* child = left->right;：把 left 节点的右子节点存储在 child 指针中。
left->right = root;：将 root 节点作为 left 节点的右子节点。
root->left = child;：把 child 节点作为 root 节点的左子节点。

旋转完毕之后root成为了left的子节点，所有在更新节点高度的时候应该先计算root再计算left。

通过这一系列操作，完成了右旋的结构调整。返回该子树的新根节点 left。

将当前树旋转为一棵AVL树

rotate 函数会根据节点的平衡因子和其子节点的平衡因子，判断当前树的不平衡类型（LL、LR、RR、RL），并执行相应的旋转操作来恢复平衡。

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;
}

LL 情况（左左情况）

if (curBalance > 1 && balance(root->left) >= 0)
{
    return rightRotate(root);
}

当 curBalance > 1 时，说明 root 节点的左子树比右子树高至少 2 层。
当 balance(root->left) >= 0 时，说明 root 左子节点的左子树高度大于等于其右子树高度。
这种情况属于 LL 型不平衡，需要对 root 节点进行右旋操作，调用 rightRotate(root) 函数，并返回新的根节点。

LR 情况（左右情况）
1
2
3
4
5
if (curBalance > 1 && balance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
- 当 curBalance > 1 时，表明 root 节点的左子树比右子树高至少 2 层。
- 当 balance(root->left) < 0 时，说明 root 左子节点的右子树比其左子树高。
- 这种情况属于 LR 型不平衡，需要先对 root 的左子节点进行左旋操作，即 root->left = leftRotate(root->left)，然后再对 root 节点进行右旋操作，最后返回新的根节点。
RR 情况（右右情况）
1
2
3
4
if (curBalance < -1 && balance(root->right) <= 0)
{
return leftRotate(root);
}
- 当 curBalance < -1 时，说明 root 节点的右子树比左子树高至少 2 层。
- 当 balance(root->right) <= 0 时，说明 root 右子节点的右子树高度大于等于其左子树高度。
- 这种情况属于 RR 型不平衡，需要对 root 节点进行左旋操作，调用 leftRotate(root) 函数，并返回新的根节点。
RL 情况（右左情况）
1
2
3
4
5
if (curBalance < -1 && balance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
- 当 curBalance < -1 时，表明 root 节点的右子树比左子树高至少 2 层。
- 当 balance(root->right) > 0 时，说明 root 右子节点的左子树比其右子树高。
- 这种情况属于 RL 型不平衡，需要先对 root 的右子节点进行右旋操作，即 root->right = rightRotate(root->right)，然后再对 root 节点进行左旋操作，最后返回新的根节点。
平衡情况
1
return root;
如果 root 节点的平衡因子在 -1 到 1 之间，说明该节点所在子树已经平衡，直接返回 root 节点。

插入

AVL 树是一种自平衡的二叉搜索树，插入操作不仅要遵循二叉搜索树的插入规则，还要在插入后通过旋转操作来保证树的平衡性，使得树的左右子树高度差不超过 1，从而保证树的查找、插入和删除操作的时间复杂度始终保持在 O(log⁡n)。

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->data)
    {
        root->left = insert(root->left, value);
    }
    else if (value > root->data)
    {
        root->right = insert(root->right, value);
    }
    else
    {
        return root;
    }
    root->height = std::max(height(root->left), height(root->right)) + 1;
    return rotate(root);
}

处理空树情况
1
2
3
4
if (root == nullptr)
{
return new AVLNode(value);
}
如果当前传入的 root 指针为空，说明当前位置是插入新节点的位置，创建一个新的 AVLNode 对象，其数据值为 value，并返回该新节点的指针。
确定插入位置
1
2
3
4
5
6
7
8
9
10
11
12
if (value < root->data)
{
root->left = insert(root->left, value);
}
else if (value > root->data)
{
root->right = insert(root->right, value);
}
else
{
return root;
}
- 如果 value 小于 root 节点的数据值，递归调用 insert 函数将 value 插入到 root 的左子树中，并将插入后的左子树指针更新给 root->left。
- 如果 value 大于 root 节点的数据值，递归调用 insert 函数将 value 插入到 root 的右子树中，并将插入后的右子树指针更新给 root->right。
- 如果 value 等于 root 节点的数据值，由于 AVL 树中不允许有重复节点，直接返回 root 节点的指针。
更新当前节点的高度
1
root->height = std::max(height(root->left), height(root->right)) + 1;
在插入新节点后，需要更新当前 root 节点的高度。节点的高度定义为其左右子树高度的最大值加 1。这里调用 height 函数获取左右子树的高度，该函数应该是 AVLTree 类中用于获取节点高度的成员函数。
旋转操作以保持树的平衡
1
return rotate(root);
插入新节点可能会破坏 AVL 树的平衡性，因此调用 rotate 函数对 root 节点进行平衡调整。rotate 函数会根据节点的平衡因子和其子节点的平衡因子，判断当前树的不平衡类型（LL、LR、RR、RL），并执行相应的旋转操作来恢复平衡，最后返回调整后的子树的根节点指针。

删除

和插入操作类似，删除操作不仅要遵循二叉搜索树的删除规则，还要在删除节点后通过旋转操作来保证树的平衡性，以维持 AVL 树高效的查找、插入和删除性能（时间复杂度保持在 O(log⁡n)）。

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->data)
    {
        root->left = remove(root->left, value); 
    }
    else if (value > root->data)
    {
        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->data = current->data;
            root->right = remove(root->right, current->data);
        }
    }
    if (root == nullptr)
    {
        return root;
    }
    root->height = std::max(height(root->left), height(root->right)) + 1;
    return rotate(root);
}

处理空树情况
1
2
3
4
if (root == nullptr)
{
return root;
}
如果当前传入的 root 指针为空，说明树为空，没有要删除的节点，直接返回 root（即 nullptr）。
确定要删除的节点位置
1
2
3
4
5
6
7
8
if (value < root->data)
{
root->left = remove(root->left, value);
}
else if (value > root->data)
{
root->right = remove(root->right, value);
}
- 如果 value 小于 root 节点的数据值，递归调用 remove 函数在 root 的左子树中删除值为 value 的节点，并将删除后的左子树指针更新给 root->left。
- 如果 value 大于 root 节点的数据值，递归调用 remove 函数在 root 的右子树中删除值为 value 的节点，并将删除后的右子树指针更新给 root->right。

找到要删除的节点

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->data = current->data;
        root->right = remove(root->right, current->data);
    }
}

情况一：要删除的节点最多只有一个子节点
- 若 root 的左子节点或右子节点为空，用非空子节点（如果存在）替换 root 节点。具体做法是：若 root 有左子节点则 node 指向左子节点，否则指向右子节点。
- 如果 node 为空，说明 root 是叶子节点，直接将 root 置为 nullptr；否则将 node 的内容复制到 root。
- 最后删除 node 节点，释放其占用的内存。
情况二：要删除的节点有两个子节点
- 找到 root 右子树中的最小节点（即右子树中最左边的节点），用该最小节点的值替换 root 节点的值。
- 递归调用 remove 函数在 root 的右子树中删除这个最小节点。

处理删除后根节点为空的情况
1
2
3
4
if (root == nullptr)
{
return root;
}
如果删除操作后 root 变为 nullptr，直接返回 root。
更新当前节点的高度
1
root->height = std::max(height(root->left), height(root->right)) + 1;
在删除节点后，需要更新当前 root 节点的高度。节点的高度定义为其左右子树高度的最大值加 1。这里调用 height 函数获取左右子树的高度，该函数应该是 AVLTree 类中用于获取节点高度的成员函数。
旋转操作以保持树的平衡
1
return rotate(root);
删除节点可能会破坏 AVL 树的平衡性，因此调用 rotate 函数对 root 节点进行平衡调整。rotate 函数会根据节点的平衡因子和其子节点的平衡因子，判断当前树的不平衡类型（LL、LR、RR、RL），并执行相应的旋转操作来恢复平衡，最后返回调整后的子树的根节点指针。

中序遍历

按照中序的方式对AVL树进行遍历，最终会得到一个升序序列。

void AVLTree::inorder(AVLNode* root)
{
    if (root == nullptr)
    {
        return;
    }
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

2.4 测试

在下面的测试代码中提供了20条数据，用于构建一棵AVL树，并测试了节点的插入和删除功能，最后使用中序的方式对AVL树进行了遍历用于验证插入和删除操作的正确性。

int main()
{
    AVLTree tree;
    vector<int> data = { 10,5,15,3,7,12,18,1,4,6,8,11,13,16,19,2,9,14,17,20 };
    for (auto it : data)
    {
        tree.insert(it);
    }
    cout << "中序遍历AVL树: ";
    tree.inorder();
    cout << endl;
    cout << "删除节点7, 14, 16" << endl;
    tree.remove(7);
    tree.remove(14);
    tree.remove(16);
    tree.inorder();
    cout << endl;
    return 0;
}

终端输出的结果为：

中序遍历AVL树: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
删除节点7, 14, 16
1 2 3 4 5 6 8 9 10 11 12 13 15 17 18 19 20
释放节点: 2
释放节点: 1
释放节点: 4
释放节点: 3
释放节点: 6
释放节点: 9
释放节点: 8
释放节点: 5
释放节点: 11
释放节点: 13
释放节点: 12
释放节点: 17
释放节点: 20
释放节点: 19
释放节点: 18
释放节点: 15
释放节点: 10