一篇文章教会你什么是高度平衡二叉搜索(AVL)树（上）

AVL树的概念

AVL树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logN)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

1.操作

AVL树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL旋转"。

以下图表以四列表示四种情况，每行表示在该种情况下要进行的操作。在左左和右右的情况下，只需要进行一次旋转操作；在左右和右左的情况下，需要进行两次旋转操作。

下面动画演示了不断将节点插入AVL树时的情况，并且演示了左旋（Left Rotation）、右旋（Right Rotation）、右左旋转（Right-Left Rotation）、左右旋转（Left-Right Rotation）以及带子树的右旋（Right Rotation with children）

2.删除

从AVL树中删除，可以通过把要删除的节点向下旋转成一个叶子节点，接着直接移除这个叶子节点来完成。因为在旋转成叶子节点期间最多有log n个节点被旋转，而每次AVL旋转耗费固定的时间，所以删除处理在整体上耗费O(log n) 时间。

3.搜索

可以像普通二叉查找树一样的进行，所以耗费O(log n)时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查找而改变。（这是与伸展树搜索相对立的，它会因为搜索而变更树结构。）

4.实现描述

假设平衡因子是左子树的高度减去右子树的高度所得到的值，又假设由于在二叉排序树上插入节点而失去平衡的最小子树根节点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先节点），则失去平衡后进行的规律可归纳为下列四种情况：

1. 单向右旋平衡处理LL：由于在*a的左子树根节点的左子树上插入节点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需进行一次右旋转操作；
2. 单向左旋平衡处理RR：由于在*a的右子树根节点的右子树上插入节点，a的平衡因子由-1变为-2，致使以a为根的子树失去平衡，则需进行一次左旋转操作；
3. 双向旋转（先左后右）平衡处理LR：由于在*a的左子树根节点的右子树上插入节点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
4. 双向旋转（先右后左）平衡处理RL：由于在*a的右子树根节点的左子树上插入节点，a的平衡因子由-1变为-2，致使以a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

在平衡二叉排序树AVL树（Adelson-Velsky and Landis Tree）上插入一个新的数据元素e的递归算法可描述如下：

1. 若AVL树为空树，则插入一个数据元素为e的新节点作为AVL树的根节点，树的深度增1；
2. 若e的关键字和AVL树的根节点的关键字相等，则不进行；
3. 若e的关键字小于AVL树的根节点的关键字，而且在AVL树的左子树中不存在和e有相同关键字的节点，则将e插入在AVL树的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之：

1. AVL树的根节点的平衡因子为-1（右子树的深度大于左子树的深度，则将根节点的平衡因子更改为0，BBST的深度不变；
2. AVL树的根节点的平衡因子为0（左、右子树的深度相等）：则将根节点的平衡因子更改为1，BBST的深度增1；
3. AVL树的根节点的平衡因子为1（左子树的深度大于右子树的深度）：则若AVL树的左子树根节点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根节点和其右子树根节点的平衡因子更改为0，树的深度不变；

4. 若e的关键字大于AVL树的根节点的关键字，而且在AVL树的右子树中不存在和e有相同关键字的节点，则将e插入在AVL树的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。

AVL树的实现

1.AVL树节点的定义

template<class K, class V>
struct AVLTreeNode
{
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;
  pair<K, V> _kv;
  int _bf;
  AVLTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
    , _bf(0)
  {}
};

这个C++模板结构体，表示一个AVL树的节点（AVLTreeNode），AVL树是一种自平衡二叉搜索树。这个结构体包含了以下成员：

1. _left：指向左子节点的指针。
2. _right：指向右子节点的指针。
3. _parent：指向父节点的指针。
4. _kv：一个键值对，用来存储节点的关键字和关联的值。
5. _bf：平衡因子（Balance Factor），用来表示节点的平衡状态。通常，平衡因子是左子树的高度减去右子树的高度。AVL树要求每个节点的平衡因子在[-1, 1]范围内，以保持树的平衡。

这个结构体表示了AVL树中的一个节点，通常在AVL树的实现中，你会有一个指向根节点的指针来访问整个树。AVL树的节点结构包括平衡因子 _bf 是为了帮助维持树的平衡，当插入或删除节点时，需要根据平衡因子来进行相应的旋转操作，以确保树的平衡性。

2.AVL树的插入

这里我们首先定义结构体struct AVLTree

包含下面的成员:

typedef AVLTreeNode<K, V> Node;
private:
  Node* _root = nullptr;

定义插入成员函数:

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->_right;
        }
        else if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            return false;
        }
    }
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }
    cur->_parent = parent;
    // 控制平衡
    while (parent)
    {
        if (cur == parent->_right)
        {
            parent->_bf++;
        }
        else
        {
            parent->_bf--;
        }
        if (parent->_bf == 0)
        {
            break;
        }
        else if (abs(parent->_bf) == 1)
        {
            parent = parent->_parent;
            cur = cur->_parent;
        }
        else if (abs(parent->_bf) == 2)
        {
            // 说明parent所在子树已经不平衡了，需要旋转处理
            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)
            {
                RotateLR(parent);
            }
            else if (parent->_bf == 2 && cur->_bf == -1)
            {
                RotateRL(parent);
            }
            else
            {
                assert(false);
            }
            break;
        }
        else
        {
            assert(false);
        }
    }
    return true;
}

这段代码的主要功能是往AVL树中插入一个新的键值对 kv，并在插入后维护树的平衡性。下面是代码的主要步骤：

1. 如果树为空（_root == nullptr），则直接创建一个新的根节点 _root 并插入 kv，然后返回。
2. 如果树不为空，进入插入节点的逻辑：

• 使用 parent 和 cur 指针来遍历树，找到应该插入的位置。
• 如果当前节点 cur 的关键字小于 kv 的关键字，则向右子树移动，否则向左子树移动，直到找到一个空位置插入新节点。

3. 插入新节点后，需要更新节点的父节点指针 _parent。
4. 接下来是维护树的平衡性的逻辑：

• 在插入过程中，通过循环向上更新父节点的平衡因子 _bf。
• 如果某个节点的平衡因子为0，表示它的子树高度没有变化，可以停止更新平衡因子，因为父节点的平衡因子也不会改变。
• 如果某个节点的平衡因子为1或-1，表示它的子树高度发生了变化，需要向上继续更新平衡因子。
• 如果某个节点的平衡因子为2或-2，表示树已经不平衡了，需要进行旋转操作来恢复平衡。

5. 旋转操作的选择取决于不平衡节点及其子节点的平衡因子情况。通常，AVL树有四种旋转操作，分别是左旋（RotateL）、右旋（RotateR）、左右旋（RotateLR）和右左旋（RotateRL）。

平衡因子的更新规则

1. 新增在左,parent->bf--;新增在右,parent->bf++
2. 更新后,parent->bf==1 or -1,说明parent插入前的平衡因子是0,说明左右子树高度相等,插入后有一边高,需要继续往上更新
3. 更新后,parent->bf==0,说明parent插入前的平衡因子是1 or -1,说明左右子树一边高一边低,插入后两边一样高,插入填上了矮的那边,parent所在子树高度不变,不需要继续往上更新
4. 更新后,parent->bf==2 or -2,说明parent插入前的平衡因子是1 or -1,已经平衡临界值,插入变成2 or -2,parent所在子树需要旋转处理
5. 更新后,parent->bf>2 or <-2,这个条件是不成立的,如果存在,则说明插入前就存在问题,需向前检查

3.AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种 ：

3.1 新节点插入较高右子树的右侧—右右:左单旋

void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if (subRL)
        subRL->_parent = parent;
    Node* ppNode = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    if (_root == parent)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if (ppNode->_left == parent)
        {
            ppNode->_left = subR;
        }
        else
        {
            ppNode->_right = subR;
        }
        subR->_parent = ppNode;
    }
    subR->_bf = parent->_bf = 0;
}

1. 首先，保存父节点 parent 的右子树 subR 和 subR 的左子树 subRL 的指针。
2. 将 parent 的右子树指针 _right 指向 subRL，即将 subRL 作为新的 parent 的右子树。
3. 如果 subRL 存在（不为 nullptr），则将 subRL 的父节点指针 _parent 指向 parent，以确保树的连接正确。
4. 获取 parent 的父节点指针 ppNode，以确定如何连接 subR。
5. 将 subR 的左子树指针 _left 指向 parent，同时将 parent 的父节点指针 _parent 指向 subR，完成左旋转。
6. 如果 parent 是根节点（_root == parent），则需要更新根节点 _root 为 subR，并将 subR 的父节点指针 _parent 设置为 nullptr，以确保树的根正确连接。
7. 否则，如果 parent 不是根节点，根据 parent 在其父节点 ppNode 中的位置，将 subR 连接到正确的位置，更新 subR 的父节点指针 _parent 为 ppNode。
8. 最后，将 parent 和 subR 的平衡因子 _bf 设置为0，因为在左旋转后，它们的高度没有变化。

3.2 新节点插入较高左子树的左侧—左左:右单旋

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

1. 首先，保存父节点 parent 的左子树 subL 和 subL 的右子树 subLR 的指针。
2. 将 parent 的左子树指针 _left 指向 subLR，即将 subLR 作为新的 parent 的左子树。
3. 如果 subLR 存在（不为 nullptr），则将 subLR 的父节点指针 _parent 指向 parent，以确保树的连接正确。
4. 获取 parent 的父节点指针 ppNode，以确定如何连接 subL。
5. 将 subL 的右子树指针 _right 指向 parent，同时将 parent 的父节点指针 _parent 指向 subL，完成右旋转。
6. 如果 parent 是根节点（_root == parent），则需要更新根节点 _root 为 subL，并将 subL 的父节点指针 _parent 设置为 nullptr，以确保树的根正确连接。
7. 否则，如果 parent 不是根节点，根据 parent 在其父节点 ppNode 中的位置，将 subL 连接到正确的位置，更新 subL 的父节点指针 _parent 为 ppNode。
8. 最后，将 parent 和 subL 的平衡因子 _bf 设置为0，因为在右旋转后，它们的高度没有变化。

原理同左单旋