AVL树的详细实现(C++)

AVL树概念

前面已经介绍了二叉搜索树，但是二叉搜索树在某些情况下会出现极度不平衡，其树形结构便退化成了链表，查找效率也会下降。于是出现了 AVL 树，AVL 树保证了二叉搜索树的平衡，引入了平衡监督机制，也就是在插入结点时，树中某一部分不平衡度超过一个阈值后将出发平衡调整操作，这样便保证了树的平衡度在可接受的范围内，最大的好处就是提高了搜索的效率。

AVL 树是一种平衡二叉树，其名字来源于发明者的名字（Adelson-Velskii 以及 Landis）。AVL树的递归定义如下：

左右子树的高度差小于等于 1。
其每一个子树均为平衡二叉树。

通过这两个性质就可以判定一棵树是否为平衡二叉树了。

如下图就是一颗平衡二叉树，任何节点的两个子树的高度最大差别为 1：

而下图不是一颗平衡二叉树，因为结点 7 的两颗子树高度相差为 2。

AVL 树的查找、插入和删除在平均和最坏情况下均为 O(logn)。

如果在 AVL 树种插入或删除节点后，使得高度之差大于 1。此时，AVL 树的平衡状态就被破坏，不再是平衡二叉树，为了维持一个平衡状态，需要对其进行旋转处理。

平衡二叉树加入了“平衡因子”概念，定义为：

某个结点的左子树的高度减去右子树的高度得到的差值。AVL 树的所有结点的平衡因子的绝对值都不超过 1。

为了计算平衡因子，自然需要在节点种引入高度这一属性。高度一般定义为左右子树高度的最大值。下面将会详细介绍 AVL 树的详细实现。

AVL树的失衡调整失衡

在 AVL 树中进行插入或删除节点后，可能导致 AVL 树失去平衡。这种失衡可以概括为 4 中姿态：

（1）LL 失衡：LeftLeft，也称为“左左”。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致“根的左子树的高度”比“根的右子树的高度”大 2，导致 AVL 树失去了平衡。如下图：

（2)LR 失衡：LeftRight，也称为“左右”。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致“根的左子树的高度”比“根的右子树的高度”大 2，导致 AVL 树失去了平衡。如下图：

（3）RL 失衡：RightLeft，称为“右左”。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致“根的右子树的高度”比“根的左子树的高度”大 2，导致 AVL 树失去了平衡。

（4）RR 失衡：RightRight，称为“右右”。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致“根的右子树的高度”比“根的左子树的高度”大 2，导致 AVL 树失去了平衡。

旋转 LL 旋转

LL 失衡的情况，可以通过一次左旋转将 AVL 树恢复平衡，如下图：

可以发现，只通过一次旋转就可以恢复为 AVL 树。对于 LL 旋转，可以这样理解：

LL 旋转是围绕“失去平衡的 AVL 根节点”进行的，也就是节点 k2，由于是 LL 情况，即“左左情况”，用手抓着“左孩子，即 k1”使劲向左摇，将 k1 变成了根节点，而 k2 变成了 k1 的右子树，而“k1 的右子树”变成了“k2 的左子树”。

代码如下：

AVLTreeNode *leftLeftRotation(AVLTreeNode *&k2)
{
    AVLTreeNode *k1 = k2->m_leftChild;
    k2->m_leftChild = k1->m_rightNode;
    k1->m_rightNode = k2;
    k2->m_height = std::max(height(k2->m_leftChild), height(k2->m_rightNode)) + 1;
    k1->m_height = std::max(height(k1->m_leftChild), k2->m_height) + 1;
    return k1;
}

RR 旋转

理解了 LL 之后，RR 旋转就相当容易理解了。RR 就是与 LL 堆成的情况，RR 恢复平衡的旋转方法如下：

RR 旋转也只需要一次即可。对于 RR 旋转，可以这样理解：

RR 旋转是围绕“失去平衡的 AVL 根节点”进行的，也就是节点 k1，由于是 RR 情况，即“右右情况”，用手抓着“右孩子，即 k2”使劲向右摇，将 k2 变成了根节点，而 k1 变成了 k2 的左子树，而“k1 的右子树”变成了“k2 的左子树”。

代码如下：

AVLTreeNode *rightRightRotation(AVLTreeNode *&k1)
{
    AVLTreeNode *k2 = k1->m_rightNode;
    k1->m_rightNode = k2->m_leftChild;
    k2->m_leftChild = k1;

    k1->m_height = std::max(height(k1->m_leftChild), height(k1->m_rightNode)) + 1;
    k2->m_height = std::max(height(k2->m_rightNode), k1->m_height) + 1;
    return k2;
}

LR 旋转

LR 失衡情况，需要经过两次旋转才能让 AVL 树恢复平衡。如下图：

第一次旋转是围绕 k1 进行的 RR 旋转，第二次旋转是围绕 k3 进行的 LL 旋转。

代码如下：

AVLTreeNode *leftRightRotation(AVLTreeNode *&k3)
{
    k3->m_leftChild = rightRightRotation(k3->m_leftChild);
    return leftLeftRotation(k3);
}

RL 旋转

RL 旋转是和 LR 对称的情况，RL 恢复平衡的旋转方法如下：

第一次旋转是围绕 k3 进行的 LL 旋转，第二次是围绕 k1 进行的 RR 旋转。

代码如下：

AVLTreeNode *rightLeftRotation(AVLTreeNode *&k1)
{
    k1->m_rightNode = leftLeftRotation(k1->m_rightNode);
    return rightRightRotation(k1);
}

AVL树的实现节点定义

template 
struct AVLTreeNode
{
    T m_key;                  // 关键字
    int m_height;             // 高度
    AVLTreeNode *m_leftChild; // 左孩子
    AVLTreeNode *m_rightNode; // 右孩子
    AVLTreeNode(T value, AVLTreeNode *l, AVLTreeNode *r) : m_key(value), m_height(0), m_leftChild(l), m_rightNode(r) {}
};

详细代码实现

注意：关于 AVL 树的各种二叉树的通用接口之前的二叉树篇幅中已经实现过，这里不再赘述，仅实现了 AVL 树中重要的接口。

#include 
using namespace std;

template 
struct AVLTreeNode
{
    T m_key;                  // 关键字
    int m_height;             // 高度
    AVLTreeNode *m_leftChild; // 左孩子
    AVLTreeNode *m_rightNode; // 右孩子
    AVLTreeNode(T value, AVLTreeNode *l, AVLTreeNode *r) : m_key(value), m_height(0), m_leftChild(l), m_rightNode(r) {}
};

template 
class AVLTree
{
public:
    AVLTree() : m_root(NULL) {}
    ~AVLTree() { destroy(m_root); }

public:
    // 中序遍历
    void inOrder() { inOrder(m_root); }

    // 先序遍历
    void preOrder() { preOrder(m_root); }

    // 树的高度
    int height() { return height(m_root); }

    // 查找AVL树种值为key的结点（递归）
    AVLTreeNode *search(T key) { return search(m_root, key); }

    // 查找AVL树种值为key的结点（非递归）
    AVLTreeNode *iterativeSearch(T key) { return iterativeSearch(m_root, key); }

    // 查找最小结点，返回最小结点的键值
    T minimum()
    {
        AVLTreeNode *p = minimum(m_root);
        if (p != NULL)
            return p->m_key;
        return (T)NULL;
    }

    // 查找最大结点，返回最大结点的键值
    T maximum()
    {
        AVLTreeNode *p = maximum(m_root);
        if (p != NULL)
            return p->m_key;
        return (T)NULL;
    }

    // 将键值为key的结点插入到AVL中
    void insert(T key) { insert(m_root, key); }

    // 删除键值为key的结点
    void remove(T key)
    {
        AVLTreeNode *z = search(m_root, key);
        if (z != NULL)
            m_root = remove(m_root, z);
    }

    // 销毁AVL树
    void destroy() { destroy(m_root); }

private:
    void inOrder(AVLTreeNode *node)
    {
        if (node == NULL)
            return;
        inOrder(node->m_leftChild);
        cout << node->m_key << " ";
        inOrder(node->m_rightNode);
    }

    void preOrder(AVLTreeNode *node)
    {
        if (node == NULL)
            return;
        cout << node->m_key << " ";
        preOrder(node->m_leftChild);
        preOrder(node->m_rightNode);
    }

    int height(AVLTreeNode *node)
    {
        return node != NULL ? node->m_height : 0;
    }

    void destroy(AVLTreeNode *&tree)
    {
        if (tree == NULL)
            return;
        if (tree->m_leftChild != NULL)
            destroy(tree->m_leftChild);
        if (tree->m_rightNode != NULL)
            destroy(tree->m_rightNode);
        delete tree;
    }

    AVLTreeNode *search(AVLTreeNode *node, T key)
    {
        if (node == NULL || node->m_key == key)
            return node;
        if (key < node->m_key)
            return search(node->m_leftChild, key);
        else
            return search(node->m_rightNode, key);
    }

    AVLTreeNode *iterativeSearch(AVLTreeNode *node, T key)
    {
        while ((node != NULL) && (node->m_key != key))
        {
            if (key < node->m_key)
                node = node->m_leftChild;
            else
                node = node->m_rightNode;
        }
        return node;
    }

    AVLTreeNode *minimum(AVLTreeNode *node)
    {
        if (node == NULL)
            return NULL;
        while (node->m_leftChild != NULL)
        {
            node = node->m_leftChild;
        }
        return node;
    }

    AVLTreeNode *maximum(AVLTreeNode *node)
    {
        if (node == NULL)
            return NULL;
        while (node->m_rightNode != NULL)
        {
            node = node->m_rightNode;
        }
        return node;
    }

    AVLTreeNode *insert(AVLTreeNode *&node, T key)
    {
        if (node == NULL)
        {
            node = new AVLTreeNode(key, NULL, NULL);
        }
        else if (key < node->m_key) // key插入node的左子树的情况
        {
            node->m_leftChild = insert(node->m_leftChild, key);
            // 插入节点后，如果AVL树失衡，需要进行相应调节
            if (height(node->m_leftChild) - height(node->m_rightNode) == 2)
            {
                if (key < node->m_leftChild->m_key)
                    node = leftLeftRotation(node);
                else
                    node = leftRightRotation(node);
            }
        }
        else if (key > node->m_key) // key插入node的右子树的情况
        {
            node->m_rightNode = insert(node->m_rightNode, key);
            // 插入节点后，如果AVL树失衡，需要进行相应调节
            if (height(node->m_rightNode) - height(node->m_leftChild) == 2)
            {
                if (key > node->m_rightNode->m_key)
                    node = rightRightRotation(node);
                else
                    node = rightLeftRotation(node);
            }
        }
        else
        {
            cout << "添加失败，不能添加相同的结点" << endl;
        }
        node->m_height = max(height(node->m_leftChild), height(node->m_rightNode)) + 1;
        return node;
    }

    AVLTreeNode *remove(AVLTreeNode *&node, AVLTreeNode *z)
    {
        if (node == NULL || z == NULL)
            return NULL;

        if (z->m_key < node->m_key) // 待删除的节点在tree的左子树中
        {
            node->m_leftChild = remove(node->m_leftChild, z);
            // 删除节点后，如果AVL树失衡，需要进行相应调节
            if (height(node->m_rightNode) - height(node->m_leftChild) == 2)
            {
                AVLTreeNode *r = node->m_rightNode;
                if (height(r->m_leftChild) > height(r->m_rightNode))
                    node = rightLeftRotation(node);
                else
                    node = rightRightRotation(node);
            }
        }
        else if (z->m_key > node->m_key) //待删除的节点在node的右子树中
        {
            // 删除节点后，如果AVL树失衡，需要进行相应调节
            node->m_rightNode = remove(node->m_rightNode, z);
            if (height(node->m_leftChild) - height(node->m_rightNode) == 2)
            {
                AVLTreeNode *l = node->m_leftChild;
                if (height(l->m_rightNode) > height(l->m_leftChild))
                    node = leftRightRotation(node);
                else
                    node = leftLeftRotation(node);
            }
        }
        else //当前node就是要删除的节点
        {
            if ((node->m_leftChild != NULL) && (node->m_rightNode != NULL))
            {
                if (height(node->m_leftChild) > height(node->m_rightNode))
                {
                    if (height(node->m_leftChild) > height(node->m_rightNode))
                    {
                        
                        AVLTreeNode *max = maximum(node->m_leftChild);
                        node->m_key = max->m_key;
                        node->m_leftChild = remove(node->m_leftChild, max);
                    }
                    else
                    {
                        
                        AVLTreeNode *min = minimum(node->m_rightNode);
                        node->m_key = min->m_key;
                        node->m_rightNode = remove(node->m_rightNode, min);
                    }
                }
            }
            else
            {
                // 被删除的节点等于node，并且node有一个孩子
                // 将当前节点指向该孩子节点并删除当前节点
                AVLTreeNode *tmp = node;
                node = node->m_leftChild != NULL ? node->m_leftChild : node->m_rightNode;
                delete tmp;
            }
        }
        return node;
    }

private:
    

    AVLTreeNode *leftLeftRotation(AVLTreeNode *&k2)
    {
        AVLTreeNode *k1 = k2->m_leftChild;
        k2->m_leftChild = k1->m_rightNode;
        k1->m_rightNode = k2;
        k2->m_height = std::max(height(k2->m_leftChild), height(k2->m_rightNode)) + 1;
        k1->m_height = std::max(height(k1->m_leftChild), k2->m_height) + 1;
        return k1;
    }

    
    AVLTreeNode *rightRightRotation(AVLTreeNode *&k1)
    {
        AVLTreeNode *k2 = k1->m_rightNode;
        k1->m_rightNode = k2->m_leftChild;
        k2->m_leftChild = k1;

        k1->m_height = std::max(height(k1->m_leftChild), height(k1->m_rightNode)) + 1;
        k2->m_height = std::max(height(k2->m_rightNode), k1->m_height) + 1;
        return k2;
    }

    
    AVLTreeNode *leftRightRotation(AVLTreeNode *&k3)
    {
        k3->m_leftChild = rightRightRotation(k3->m_leftChild);
        return leftLeftRotation(k3);
    }

    
    AVLTreeNode *rightLeftRotation(AVLTreeNode *&k1)
    {
        k1->m_rightNode = leftLeftRotation(k1->m_rightNode);
        return rightRightRotation(k1);
    }

private:
    AVLTreeNode *m_root; // AVL树的根节点
};

int main()
{
    AVLTree tree;
    tree.insert(3);
    tree.insert(2);
    tree.insert(1);
    tree.insert(4);
    tree.insert(5);
    tree.insert(6);
    tree.insert(7);

    tree.insert(16);
    tree.insert(15);
    tree.insert(14);
    tree.insert(13);
    tree.insert(12);
    tree.insert(11);
    tree.insert(10);
    tree.insert(8);
    tree.insert(9);

    tree.preOrder();
    cout << endl;
    tree.inOrder();
    cout << endl;

    tree.remove(8);
    tree.preOrder();
    cout << endl;
    tree.preOrder();
    cout << endl;

    return 0;
}

参考：
https://wangkuiwu.github.io/2013/02/02/avltree-cpp

AVL树的详细实现(C++)

C/C++/C#相关栏目本月热门文章