深入探究：AVL树的平衡之道

文章目录

一、AVL树的原理
- AVL树的定义和特性
- 平衡因子的概念
二、AVL树的自平衡策略
- a. 单旋（single rotation）
- - 1. 左单旋（Left Rotation）：
  - 2. 右单旋（Right Rotation）：
- b. 双旋（Double Rotation）：
- - 1. 左右双旋（Left-Right Double Rotation）：
  - 2. 右左双旋（Right-Left Double Rotation）：
三、AVL树的插入与验证
- 1. 插入操作
- 2. AVL树的验证

本文将带领读者深入探索 AVL 树的奥秘，从基本概念到具体实现，逐步剖析 AVL 树的平衡之道。无论您是初学者还是资深程序员，相信通过本文的阅读，您都能对 AVL 树有更深入的理解，并能够运用它解决实际问题。

一、AVL树的原理

AVL 树（Adelson-Velsky and Landis tree），作为一种自平衡的二叉搜索树，由 G.M. Adelson-Velsky 和 E.M. Landis 在 1962 年提出。它承载着优雅而高效的数据结构设计理念。其独特之处在于通过旋转操作保持树的高度平衡，从而确保各种操作的时间复杂度始终保持在 $O(log n) $的水平。AVL 树的诞生源于对二叉搜索树的不足之处的思考和突破，是计算机科学领域中的重要里程碑之一。

AVL树的定义和特性

AVL树是一种自平衡的二叉搜索树，其在每个节点上维护一个平衡因子（Balance Factor），用于确保树的高度保持在较低水平（即保持在$O(log n) $）从而提高性能。下面详细解释AVL树的定义和特性：

定义：AVL树是一种满足以下性质的二叉搜索树：
- 每个节点的平衡因子（Balance Factor）是 -1、0 或 1。
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。
- 左子树和右子树都是AVL树。
我们给出如下代码来定义 AVL树：
```
template<class K,class V>
struct AVLTreeNode {
	AVLTreeNode<K, V>* _left;	// 该节点的左孩子
	AVLTreeNode<K, V>* _right;	// 该节点的右孩子
	AVLTreeNode<K, V>* _parent;	// 该节点的双亲
	int _bf;					// 该节点的平衡因子
	pair<K, V> _kv;

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv) {}
};
template<class K, class V>
class AVLTree {
	typedef AVLTreeNode<K, V> Node;
public:
    //...
private:
    Node* _root;
};
```
AVLTreeNode是AVL树的节点结构，包含节点的左孩子、右孩子、双亲，以及数据和平衡因子。AVLTree是AVL树的类，包含了根节点和其他操作方法。在AVLTree类中，_root成员变量表示根节点。
特性：
- 每个节点的平衡因子限制：在AVL树中，每个节点的平衡因子必须是 -1、0 或 1。这意味着任何节点的左子树高度和右子树高度之差的绝对值不超过1。
- 左右子树的高度差不超过1：AVL树的关键特点是保持树的高度平衡，即任意节点的左子树和右子树高度差不超过1。这确保了树的高度近似于$ log(n) $，其中 n 是节点数量，从而保证了插入、查找和删除等操作的平均时间复杂度为$ O(log n)$。

在这里插入图片描述

两个二叉搜索树，只有左边的树是 AVL 树。

AVL的优势（相对于普通二叉搜索树）：

平衡性保证：AVL树通过限制每个节点的平衡因子来保持树的平衡，相比普通二叉搜索树更加平衡，避免了出现极端不平衡的情况，提高了整体性能。
高效的插入和删除操作：由于AVL树具有平衡性质，插入和删除操作会触发自平衡机制，保持树的平衡状态，使得这些操作的时间复杂度为 $O (l o g n)$ ，相比普通二叉搜索树更加高效。
稳定的查找性能：AVL树的平衡性质确保了树的高度较低，从而保证了查找操作的稳定性能，使得在动态数据集合中仍能保持较快的查找速度。

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 $log_2 (N)$ 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

平衡因子的概念

在AVL树中，平衡因子（Balance Factor）是指一个节点的左子树高度减去右子树高度的结果。具体而言，对于任意节点N，其平衡因子 BF(N) 的计算公式如下：

[ BF(N) = Height(leftSubtree) - Height(rightSubtree) ]

其中，Height(leftSubtree)表示节点N的左子树的高度，而Height(rightSubtree)表示节点N的右子树的高度。

在AVL树中，每个节点的平衡因子必须是 -1、0 或 1，否则就不符合AVL树的定义。如果某个节点的平衡因子绝对值大于1，那么这个节点就会导致其祖先节点失衡，需要通过旋转等操作来重新平衡整棵树。

我们通过控制每个节点的平衡因子，AVL树能够保持良好的平衡性质，确保在插入或删除节点后能够高效地进行自平衡操作，使得树的整体高度保持较低水平，从而提高查找、插入和删除等操作的效率。

二、AVL树的自平衡策略

AVL 树之所以被称为自平衡二叉搜索树，是因为它会在每次插入或删除操作后自动调整树的结构以保持平衡。

在插入以后，只有那些从插人点到根节点的路径上的节点的平衡可能被改变，因为只有这些节点的子树可能发生变化。当我们沿着这条路径上行到根并更新平衡信息时，我们可以找到一个节点，它的新平衡破坏了AVL条件。我们将指出如何在第一个这样的节点（即最深的节点）重新平衡这棵树，并证明，这一重新平衡保证整棵树满足AVL特性。

让我们把必须重新平衡的节点叫作a。由于任意节点最多有两个儿子，因此高度不平时，a点的两棵子树的高度差2。容易看出，这种不平衡可能出现在下面四种情况中:

对a的左儿子的左子树进行一次插入。
对a的左儿子的右子树进行一次插入,
对a的右儿子的左子树进行一次插入。
对a的右儿子的右子树进行一次插入。

情形1和4是关于a点的镜像对称，而情形2和3是关于a点的镜像对称。因此，理论上只有两种情况单旋转和双旋，当然从编程的角度来看还是四种情形：

左旋（Left Rotation），右旋（Right Rotation），左右双旋（Left-Right Double Rotation）和右左旋转（Right-Left Double Rotation），双旋是由两次单旋转组合而成的操作，用于处理更复杂的情况。下面详细介绍在AVL树如何根据节点的平衡因子进行相应的调整，以及中如何通过这些旋转操作来确保AVL树的平衡性（下图中括号内 1 代表在此处插入节点，A B C来形容其相对位置）：

a. 单旋（single rotation）

下面我们依次介绍左单旋和右单旋：

1. 左单旋（Left Rotation）：

左旋是针对某个节点的右子树过深而导致失衡的情况。即：新节点插入较高右子树的右侧—右右：左单旋。具体步骤如下：

在这里插入图片描述

假设失衡节点为A，A的右子节点为B，B的左子节点为C。
将B提升为新的根节点，A作为B的左子节点，C作为A的右子节点。
可以看到，经过左单旋后，树的高度变为插入之前了，即树的高度没有发生变化，所以左单旋后无需继续往上更新平衡因子。

根据上述内容，我们给出如下代码：

void RotateL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    parent->_right = subRL;
    if (subRL != nullptr) {
        subRL->_parent = parent;
    }
    
    subR->_left = parent;
    Node* ppnode = parent->_parent;
    parent->_parent = subR;

    if (parent == _root) {
        _root = subR;
        subR->_parent = nullptr;
    }
    else {
        if (ppnode->_left == parent)
            ppnode->_left = subR;
        else
            ppnode->_right = subR;
        subR->_parent = ppnode;
    }
    parent->_bf = 0;
    subR->_bf = 0;
}

首先将parent节点的右子节点subR的左子节点subRL作为parent节点的新右子节点，同时更新相关的指针和父节点标志位。然后根据parent节点是否为根节点进行相应的操作，将subR作为新的根节点或者将subR连接到原父节点ppnode上，并更新父节点指针，最后更新节点的平衡因子。

下面是对代码中各部分的功能和逻辑的解释：

首先，保存当前节点的右子节点（subR）和右子节点的左子节点（subRL）。然后，将当前节点的右子节点指向subRL，如果subRL不为空，则更新subRL的父节点指针为parent。接着，将subR的左子节点指向当前节点（parent），完成左旋操作。其次，更新受影响的父节点指针，确保树的连接正确性：

将parent的父节点指针指向subR。
如果parent是根节点，需要更新根节点指针为subR，并将subR的父节点指针置为空。
否则，更新父节点（ppnode）的左子树或右子树指针为subR，并更新subR的父节点指针为ppnode。

最后，将调整后的节点的平衡因子设置为0，表示平衡。

这段代码实现了AVL树中左旋操作的所有必要步骤，包括旋转、节点指针的更新以及平衡因子的设置，以确保树的平衡性得到维护。左旋和右旋是 AVL 树中用于保持树平衡的重要操作，通过这些操作可以调整树的结构以维持平衡因子的要求。

2. 右单旋（Right Rotation）：

右旋是针对某个节点的左子树过深而导致失衡的情况。即：新节点插入较高左子树的左侧—左左：右单旋。具体步骤如下：

在这里插入图片描述

设失衡节点为A，A的左子节点为B，B的右子节点为C。
将B提升为新的根节点，A作为B的右子节点，C作为A的左子节点。

根据上述内容，我们给出如下代码：

void RotateR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR != nullptr) {
        subLR->_parent = parent;
    }
    subL->_right = parent;

    Node* ppnode = parent->_parent;
    parent->_parent = subL;
    if (parent == _root) {
        _root = subL;
        subL->_parent = nullptr;
    }
    else {
        if (ppnode->_left == parent)
            ppnode->_left = subL;
        else
            ppnode->_right = subL;
        subL->_parent = ppnode;
    }
    parent->_bf = 0;
    subL->_bf = 0;
}

首先，保存当前节点的左子节点（subL）和左子节点的右子节点（subLR）。然后，将当前节点的左子节点指向subLR，如果subLR不为空，则更新subLR的父节点指针为parent。接着，将subL的右子节点指向当前节点（parent），完成右旋操作。其次，更新受影响的父节点指针，确保树的连接正确性：

将parent的父节点指针指向subL。
如果parent是根节点，需要更新根节点指针为subL，并将subL的父节点指针置为空。
否则，更新父节点（ppnode）的左子树或右子树指针为subL，并更新subL的父节点指针为ppnode。

最后，将调整后的节点的平衡因子设置为0，表示平衡。

b. 双旋（Double Rotation）：

双旋是针对某个节点的子树同时向左或向右倾斜而导致失衡的情况。一般需要进行两次单旋操作来恢复平衡。具体步骤可以是左旋后再进行右旋，或者右旋后再进行左旋。

1. 左右双旋（Left-Right Double Rotation）：

当在某个节点的左子树中的右子树更深时，需要进行右左旋转操作。这种情况下，首先对当前节点的左子节点进行左旋转，然后再对当前节点进行右旋转，以实现树的平衡。即：新节点插入较高左子树的右侧—左右：先左单旋再右单旋。具体步骤如下：

首先，获取当前节点的左子节点 subL 和左子节点的右子节点 subLR。
然后，获取 subLR 的平衡因子 bf。
接下来，调用 RotateL 函数对当前节点的左子节点进行左旋转。

再次，调用 RotateR 函数对当前节点进行右旋转。

Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);

根据 subLR 的平衡因子 bf 的不同情况，进行平衡因子的更新：
- 如果 bf 为 0，表示左右子树高度相等，将当前节点和左子节点的平衡因子都设置为 0。
- 如果 bf 为 1，表示左子树高度大于右子树，将当前节点的平衡因子设置为 0，左子节点的平衡因子设置为 -1。
- 如果 bf 为 -1，表示右子树高度大于左子树，将当前节点的平衡因子设置为 1，左子节点的平衡因子设置为 0。
- 如果以上情况都不满足，抛出异常。
```
if (bf == 0) {
    parent->_bf = 0;
    subL->_bf = 0;
}
else if (bf == 1) {
    parent->_bf = 0;
    subL->_bf = -1;
}
else if (bf == -1) {
    parent->_bf = 1;
    subL->_bf = 0;
}
else {
    assert(false);
}
```

总结上述代码如下：

void RotateLR(Node* parent) {
    if (bf == 0) {
        parent->_bf = 0;
        subL->_bf = 0;
    }
    else if (bf == 1) {
        parent->_bf = 0;
        subL->_bf = -1;
    }
    else if (bf == -1) {
        parent->_bf = 1;
        subL->_bf = 0;
    }
    else {
        assert(false);
    }
}

2. 右左双旋（Right-Left Double Rotation）：

当在某个节点的右子树中的左子树更深时，需要进行左右旋转操作。这种情况下，首先对当前节点的右子节点进行右旋转，然后再对当前节点进行左旋转，以恢复树的平衡性。即：新节点插入较高右子树的左侧—右左：先右单旋再左单旋。具体步骤如下：

首先，获取当前节点的右子节点 subR 和右子节点的左子节点 subRL。
然后，获取 subRL 的平衡因子 bf。
接下来，调用 RotateR 函数对当前节点的右子节点进行右旋转。
再次，调用 RotateL 函数对当前节点进行左旋转。

Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);

根据 subLR 的平衡因子 bf 的不同情况，进行平衡因子的更新：
- 如果 bf 为 0，表示右左子树高度相等，将当前节点和右子节点的平衡因子都设置为 0。
- 如果 bf 为 1，表示左子树高度大于右子树，将当前节点的平衡因子设置为 -1，右子节点的平衡因子设置为 0。
- 如果 bf 为 -1，表示右子树高度大于左子树，将当前节点的平衡因子设置为 0，右子节点的平衡因子设置为 1。
- 如果以上情况都不满足，抛出异常。
```
if (bf == 0) {
    parent->_bf = 0;
    subR->_bf = 0;
}
else if (bf == 1) {
    parent->_bf = -1;
    subR->_bf = 0;
}
else if (bf == -1) {
    parent->_bf = 0;
    subR->_bf =  1;
}
else {
    assert(false);
}
```

总结上述代码如下：

void RotateLR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    RotateL(parent->_left);
    RotateR(parent);
    if (bf == -1) {
        subL->_bf = 0;
        parent->_bf = 1;
    }
    else if (bf == 1) {
        subL->_bf = -1;
        parent->_bf = 0;
    }
    else if (bf == 0) {
        subL->_bf = 0;
        parent->_bf = 0;
    }
    else {
        assert(false);
    }
}

在旋转过程中，左右双旋的 subLR->_bf 在进行左单旋和右单旋函数调用时旋已置为0；右左双旋的 subRL->_bf 在进行右单旋和左单旋函数调用时旋已置为0。观察旋转后的结果我们可以得知 subLR->_bf 和 subRL->bf 在上述各种情况里都是 0，因此双旋函数不需要再对其平衡因子进行处理。

三、AVL树的插入与验证

1. 插入操作

AVL 树的插入操作主要包含两个步骤：插入新节点和平衡性调整。

A. 插入新节点：

从根节点开始，循环比较要插入节点的键值和当前节点的键值大小关系，确定插入位置。
如果要插入的节点小于当前节点，则继续在当前节点的左子树中插入；如果大于当前节点，则在右子树中插入。
当找到插入位置时，在对应的子树中插入新节点。

bool Insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new Node(kv);
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first > kv.first) {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_kv.first < kv.first) {
            parent = cur;
            cur = cur->_right;
        }
        else {
            return false;
        }
    }

    cur = new Node(kv);
    if (parent->_kv.first > kv.first) {
        parent->_left = cur;
    }
    else {
        parent->_right = cur;
    }
    cur->_parent = parent;
	//....
}

B. 平衡性调整：

在插入新节点后，从插入点向上回溯到根节点，检查沿途节点的平衡因子是否失衡（绝对值大于1）。
如果某个节点失衡，根据其子树的情况，进行相应的旋转操作（单旋转或双旋转）来保持树的平衡。
旋转操作可能会影响祖先节点的平衡因子，因此需要继续向上回溯，直到整棵树恢复平衡为止。

bool Insert(const pair<K, V>& kv) {
	// ... 
    while (parent) {
        if (cur == parent->_left) {
            parent->_bf--;
        }
        else {
            parent->_bf++;
        }
        if (parent->_bf == 0) {
            break;
        }
        else if (parent->_bf == 1 || parent->_bf == -1) {
            cur = cur->_parent;
            parent = parent->_parent;
        }
        else if (parent->_bf == 2 || parent->_bf == -2) {
            if (parent->_bf == 2 && cur->_bf == 1) {
                RotateL(parent);
            }
            else if (parent->_bf == -2 && cur->_bf == -1) {
                RotateR(parent);
            }
            else if (parent->_bf == 2 && cur->_bf == -1) {
                RotateRL(parent);
            }
            else if (parent->_bf == -2 && cur->_bf == 1) {
                RotateLR(parent);
            }
            break;
        }
        else {
            assert(false);//插入前就出错！
        }
    }
    return true;
}

通过以上两个步骤，可以实现在 AVL 树中插入新节点并保持树的平衡性（把两个代码块中内容合在一起看）。 AVL 树的平衡性调整是通过旋转操作来实现的，旋转操作包括左旋、右旋、左右双旋和右左双旋。使 AVL 树的每个节点的左右子树高度差不超过 1，以保持树的平衡性。

2. AVL树的验证

为了证明二叉树是AVL树还需验证二叉树的平衡性，在该过程中我们需要检查每个结点的平衡因子是否正确：

bool _IsBalance(Node* root, int& height) {// 后序
    if (root == nullptr) {
        height = 0;
        return true;
    }
    int leftHeight = 0, rightHeight = 0;
    
    if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight))
        return false;
    
    if (abs(leftHeight - rightHeight) >= 2) {
        cout <<root->_kv.first<< " height warning!" << endl;
        return false;
    }
    if (rightHeight - leftHeight != root->_bf) {
        cout << root->_kv.first << " balance factor warning!" << endl;
        return false;
    }
    height = max(leftHeight, rightHeight) + 1;
    return true;
}

bool IsBalance() {
    int heght = 0;
    return _IsBalance(_root, heght);
}

在函数 _IsBalance 中，它首先判断当前节点是否为空，如果是空节点，则将高度设置为 0，并返回 true。然后分别递归检查左右子树，并获取它们的高度。接着，它会判断左右子树的高度差是否大于等于 2，如果是则输出警告并返回 false。然后它会再次判断当前节点的平衡因子是否与左右子树的高度差相符，如果不符则输出警告并返回 false。最后，更新当前节点的高度为左右子树中较大的高度加 1，并返回 true。

在 IsBalance 函数中，它调用了 _IsBalance 函数，并传入根节点和一个用于记录树高度的变量。最终返回 _IsBalance 函数的结果。

总的来说，这段代码通过递归后序遍历的方式来检查整棵树的平衡性，并在发现不平衡的情况下输出相应的警告信息。这样的实现方式是典型的检查 AVL 树平衡性的方法，但需要保证树的平衡因子 _bf 在每次插入、删除后得到正确更新。

通过以上内容，我们将全面探索 AVL 树的内涵与外延，逐步揭示其平衡之道。希望本文能为读者提供清晰而全面的 AVL 树知识体系，帮助大家更好地理解和运用 AVL 树这一重要的数据结构。
本文代码的完整实现在此处，AVL树 · 比奇堡的Zyb/每日学习 - 码云 - 开源中国 (gitee.com)。