devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

AVL树的详细实现(C++)_不使用stl实现avl树

作者：盐析白兔 | 2024-03-16 01:11:16

赞

踩

不使用stl实现avl树

AVL树概念

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

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

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

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

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

AVL树的详细实现-图1

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

AVL树的详细实现-图2

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

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

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

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

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

AVL树的失衡调整

失衡

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

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

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

AVL树的详细实现-图4

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

AVL树的详细实现-图5

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

AVL树的详细实现-图6

旋转

LL 旋转

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

AVL树的详细实现-图7

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

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

代码如下：

AVLTreeNode<T> *leftLeftRotation(AVLTreeNode<T> *&k2)
{
    AVLTreeNode<T> *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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
RR 旋转

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

AVL树的详细实现-图8

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

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

代码如下：

AVLTreeNode<T> *rightRightRotation(AVLTreeNode<T> *&k1)
{
    AVLTreeNode<T> *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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
LR 旋转

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

AVL树的详细实现-图9

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

代码如下：

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

  • 1
  • 2
  • 3
  • 4
  • 5
RL 旋转

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

AVL树的详细实现-图10

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

代码如下：

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

  • 1
  • 2
  • 3
  • 4
  • 5

AVL树的实现

节点定义

template <typename T>
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) {}
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

详细代码实现

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

#include <iostream>
using namespace std;

template <typename T>
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 <typename T>
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<T> *search(T key) { return search(m_root, key); }

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

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

    // 查找最大结点，返回最大结点的键值
    T maximum()
    {
        AVLTreeNode<T> *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<T> *z = search(m_root, key);
        if (z != NULL)
            m_root = remove(m_root, z);
    }

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

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

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

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

    void destroy(AVLTreeNode<T> *&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<T> *search(AVLTreeNode<T> *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<T> *iterativeSearch(AVLTreeNode<T> *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<T> *minimum(AVLTreeNode<T> *node)
    {
        if (node == NULL)
            return NULL;
        while (node->m_leftChild != NULL)
        {
            node = node->m_leftChild;
        }
        return node;
    }

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

    AVLTreeNode<T> *insert(AVLTreeNode<T> *&node, T key)
    {
        if (node == NULL)
        {
            node = new AVLTreeNode<T>(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<T> *remove(AVLTreeNode<T> *&node, AVLTreeNode<T> *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<T> *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<T> *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))
                    {
                        /* 如果node节点的左子树比右子树高，则:
                         * (01)找出node的左子树中最大节点
                         * (02)将该最大节点的值赋值给node
                         * (03)删除该最大节点
                         * 相当于用node的左子树中最大节点作为node的替身
                         * 这种方式删除node左子树中最大节点之后，AVL树任然是平衡的
                         */
                        AVLTreeNode<T> *max = maximum(node->m_leftChild);
                        node->m_key = max->m_key;
                        node->m_leftChild = remove(node->m_leftChild, max);
                    }
                    else
                    {
                        /* 如果node节点的右子树比左子树高，则:
                         * (01)找出node的右子树中最小节点
                         * (02)将该最小节点的值赋值给node
                         * (03)删除该最小节点
                         * 相当于用node的右子树中最小节点作为node的替身
                         * 这种方式删除node右子树中最小节点之后，AVL树任然是平衡的
                         */
                        AVLTreeNode<T> *min = minimum(node->m_rightNode);
                        node->m_key = min->m_key;
                        node->m_rightNode = remove(node->m_rightNode, min);
                    }
                }
            }
            else
            {
                // 被删除的节点等于node，并且node有一个孩子
                // 将当前节点指向该孩子节点并删除当前节点
                AVLTreeNode<T> *tmp = node;
                node = node->m_leftChild != NULL ? node->m_leftChild : node->m_rightNode;
                delete tmp;
            }
        }
        return node;
    }

private:
    /* LL：左子树的左边失去平衡(左单旋转)
     *       k2              k1     
     *      /  \            /  \
     *     k1   z   ===>   x    k2
     *    /  \                 /  \
     *   x    y               y    z
     */

    AVLTreeNode<T> *leftLeftRotation(AVLTreeNode<T> *&k2)
    {
        AVLTreeNode<T> *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：右子树的右边失去平衡(右单旋转)
     *       k1              k2     
     *      /  \            /  \
     *     x   k2   ===>   k1   z
     *        /  \        /  \   
     *       y    z      x    y  
     */
    AVLTreeNode<T> *rightRightRotation(AVLTreeNode<T> *&k1)
    {
        AVLTreeNode<T> *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：左子树的右边失去平衡(左双旋转)
     *       k3               k3               k2
     *      /  \     RR      /  \     LL      /  \
     *     k1   D   ===>   k2    D   ===>   k1    k3
     *    /  \            /  \             /  \  /  \
     *   A    K2         k1   C           A    B C   D
     *       /  \       /  \
     *      B    C     A    B
     */
    AVLTreeNode<T> *leftRightRotation(AVLTreeNode<T> *&k3)
    {
        k3->m_leftChild = rightRightRotation(k3->m_leftChild);
        return leftLeftRotation(k3);
    }

    /* RL：右子树的左边失去平衡(右双旋转)
     *     k1               k1                K2
     *    /  \      LL     /  \      RR      /  \
     *   A    k3   ===>   A    k2   ===>   k1    K3
     *       /  \             /  \        /  \  /  \
     *      k2   D           B    k3     A    B C   D
     *     /  \                  /   \
     *    B    D                C     D
     */
    AVLTreeNode<T> *rightLeftRotation(AVLTreeNode<T> *&k1)
    {
        k1->m_rightNode = leftLeftRotation(k1->m_rightNode);
        return rightRightRotation(k1);
    }

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

int main()
{
    AVLTree<int> 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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
  • 328
  • 329
  • 330
  • 331
  • 332
  • 333
  • 334
  • 335
  • 336
  • 337
  • 338
  • 339
  • 340
  • 341
  • 342
  • 343
  • 344
  • 345
  • 346
  • 347
  • 348
  • 349
  • 350
  • 351
  • 352
  • 353
  • 354
  • 355
  • 356
  • 357
  • 358
  • 359
  • 360
  • 361
  • 362
  • 363
  • 364
  • 365
  • 366
  • 367

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/245949
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号