C++ AVL树

上面我们知道二叉搜索树在特殊情况下查找的时间复杂度为O(N),
所以为了解决二叉搜索树不稳定的问题，我们引入了AVL树，也称为平衡二叉树。

二叉搜索树相关知识点

AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右
子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
  
  我们如果发现平衡因子大于等于2的话，我们就会通过旋转操作使整颗树的平衡因子回到-1,0,1

AVL树基本框架

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; // balance factor

    AVLTreeNode(const pair<K, V>& kv)
            :_left(nullptr)
            , _right(nullptr)
            , _parent(nullptr)
            , _kv(kv)
            , _bf(0) 
    {}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

AVL树的基本结构

template<class K, class V>
struct AVLTree
{
	typedef AVLTreeNode<K, V> Node;
private:
	Node* _root;//定义一个根节点
};
1
2
3
4
5
6
7

AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

如何更新平衡因子
新增在右,父亲的bf加一
新增在左,父亲的bf减一

1. 更新完成后,父亲的bf==1/-1,说明父亲插入前的bf一定是0,插入后一边高一边低,需要继续向上更新
2. 更新完成后,父亲的bf==0,说明父亲在插入前的bf是1/-1,插入后两边高度一致,则不需要继续往上更新了
3. 更新完成后,父亲的bf==2/-2,打破了平衡,父亲所在的子树要旋转处理
   

AVL树的插入（无旋转）

// 一:按照二叉搜索树的方式插入值;
// 二:调整平衡因子后旋转

bool Insert(const pair<K, V> &kv) 
{
    if (_root == nullptr) // 插入第一个节点
    {
        _root = new Node(kv);
        return true;
    }

    Node *cur = _root;
    Node *parent = nullptr;
    
    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 (parent->_bf == 1 || parent->_bf == -1) // 高度出现变化,往上更新
        {
            parent = parent->_parent;
            cur = cur->_parent;
        }
        else if (abs(parent->_bf) == 2) // parent所在的子树不平衡了,旋转处理
        {
            // 后面旋转
        }
    }
}

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

AVL树的插入（旋转操作）

单旋

基础旋转

左单旋

右单旋

---

双旋

先左旋再右旋

先右旋再左旋

旋转代码

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

    parent->_right = subRL;
    subR->_left = parent;

    Node *parentParent = parent->_parent;

    parent->_parent = subR;
    if (subRL)
        subRL->_parent = parent;

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

        subR->_parent = parentParent;
    }

    parent->_bf = subR->_bf = 0;
}

void RotateR(Node *parent) // 右旋
{
    Node *subL = parent->_left;
    Node *subLR = subL->_right;

    parent->_left = subLR;
    if (subLR)
        subLR->_parent = parent;

    Node *parentParent = parent->_parent;

    subL->_right = parent;
    parent->_parent = subL;

    if (_root == parent)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if (parentParent->_left == parent)
        {
            parentParent->_left = subL;
        }
        else
        {
            parentParent->_right = subL;
        }

        subL->_parent = parentParent;
    }

    subL->_bf = parent->_bf = 0;
}

void RotateRL(Node *parent) // 先右再左
{
    Node *subR = parent->_right;
    Node *subRL = subR->_left;
    int bf = subRL->_bf;

    RotateR(parent->_right);
    RotateL(parent);

    if (bf == 0)
    {
        // subRL自己就是新增
        parent->_bf = subR->_bf = subRL->_bf = 0;
    }
    else if (bf == -1)
    {
        // subRL的左子树新增
        parent->_bf = 0;
        subRL->_bf = 0;
        subR->_bf = 1;
    }
    else if (bf == 1)
    {
        // subRL的右子树新增
        parent->_bf = -1;
        subRL->_bf = 0;
        subR->_bf = 0;
    }
    else
    {
        assert(false);
    }
}

void RotateLR(Node *parent) // 先做再右 复用
{
    RotateL(parent->_left);
    RotateR(parent);
}
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