二叉平衡树（又称 AVL 树）#

AVL 树是一种基于二叉搜索树的树，有自平衡的特点

何为平衡#

在这之前，我们先引入平衡因子的概念：

平衡因子#

对于二叉树的任意一个节点，平衡因子（此处记为 $b$ ）为：

b = Height(T_{left}) - Height(T_{right})

其中， $Height$ 代表取一个节点在这个树中的高度， $T$ 代表当前节点，下标 $_{left}$ 代表是当前节点的左节点， $_{right}$ 同理

介绍完平衡因子后，也就能够知道这里的“平衡”指的是什么了：

对于 AVL 树中的任何一个节点，平衡因子最大为 1

实现#

高度代码处理#

由于平衡因子是自行计算出来得到，而这个计算依赖与节点的高度属性，因此我们先处理关于高度的代码：

1
void updateHeight() {
2
    int lh = getHeight(left);
3
    int rh = getHeight(right);
4
    height = 1 + (lh > rh ? lh : rh);
5
}

在进行过插入等操作后，不可避免地会更改高度，因此我们需要上面的这个方法来实时更新当前节点的高度属性

同时，也就需要一个接口供我们访问这个属性

1
static int getHeight(AVLNode* node) {
2
    return node ? node->height : -1;
3
}

平衡因子计算#

之后，我们需要有一个方法来计算当前节点的平衡因子以便后续处理：

1
static int getBF(AVLNode* node) {
2
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
3
}

接下来，我们便要进行传统的增删查改环节了

但是在这之前，我们需要思考：当我们对 AVL 树进行插入和删除操作的时候，必定会对树的高度有所影响

正常的 AVL 树

但是，由于 AVL 树遵循二叉搜索树的性质，所以我们的这个 AVL 树不可避免的会有不平衡的情况出现

插入元素 7 后的的 AVL 树（不合法）

这个时候我们就需要通过一些操作将树进行平衡。这个操作便是树的旋转

树的旋转#

何为旋转#

树的旋转便是为了解决上述平衡问题而存在的操作

旋转，分为左旋转和右旋转

每种旋转的本质便是将当前节点作为轴，向左（逆时针）或者向右（顺时针）进行旋转

左旋

加以观察，你会发现旋转前和旋转后的树的中序遍历其实是一样的，换言之，旋转并没有使树改变

如果遇到了旋转部分存在一个子节点的情况时，就让旋转节点的左（右）节点等于这个冲突的节点，举个例子：

冲突解决的例子

注意到紫色的节点 2 为冲突节点，那么在节点 4 旋转的时候就将这个冲突的节点接在了旋转节点 4 的左节点上

LL,LR,RR,RL 四种类型#

所谓上述的四种类型，便是四种常见的使 VAL 树不平衡的情况

其中，对于 LL 情况我们已经见过了，便是刚刚的那个例子：

事实上，这四种类型的称呼来源于根节点和最大高度子节点的平衡因子情况

1 LL：根结点的平衡因子 +2，左子树根结点平衡因子 +1；
2 RR：根结点的平衡因子 -2，右子树根结点平衡因子 -1；
3 LR：根结点的平衡因子 +2，左子树根结点平衡因子 -1；
4 RL：根结点的平衡因子 -2，右子树根结点平衡因子 +1；

因此，我们可以写出下面的函数来实现左旋转和右旋转：

1
static AVLNode* RRotate(AVLNode* y) {
2
    if (!y || !y->left) return y;
3
    AVLNode* x = y->left;
4
    AVLNode* T2 = x->right;
5

6
    x->right = y;
7
    y->left = T2;
8

9
    y->updateHeight();
10
    x->updateHeight();
11

12
    return x;
13
}
14

15
static AVLNode* LRotate(AVLNode* x) {
16
    if (!x || !x->right) return x;
17
    AVLNode* y = x->right;
18
    AVLNode* T2 = y->left;
19

20
    y->left = x;
21
    x->right = T2;
22

23
    x->updateHeight();
24
    y->updateHeight();
25

26
    return y;
27
}

同时，需要一个 balance 函数来进行自动的平衡：

1
static AVLNode* balance(AVLNode* node) {
2
    if (!node) return nullptr;
3

4
    node->updateHeight();
5
    int bf = getBF(node);
6

7
    if (bf > 1) {
8
        if (getBF(node->left) < 0) {
9
            node->left = LRotate(node->left);
10
        }
11
        return RRotate(node);
12
    }
13

14
    if (bf < -1) {
15
        if (getBF(node->right) > 0) {
16
            node->right = RRotate(node->right);
17
        }
18
        return LRotate(node);
19
    }
20
    return node;
21
}

完成平衡相关的代码后，我们便可以开始写增删查改的代码了

插入#

1
static AVLNode* insert(AVLNode* node, int d) {
2
    if (!node) return new AVLNode(d);
3

4
    if (d < node->data) {
5
        node->left = insert(node->left, d);
6
    }
7
    else if (d > node->data) {
8
        node->right = insert(node->right, d);
9
    }
10
    else {
11
        return node;
12
    }
13

14
    return balance(node);
15
}

删除#

1
static AVLNode* del(AVLNode* node, int d) {
2
    if (!node) return nullptr;
3

4
    if (d < node->data) {
5
        node->left = del(node->left, d);
6
    }
7
    else if (d > node->data) {
8
        node->right = del(node->right, d);
9
    }
10
    else {
11
        if (!node->left || !node->right) {
12
            AVLNode* temp = node->left ? node->left : node->right;
13
            if (!temp) {
14
                delete node;
15
                return nullptr;
16
            } else {
17
                AVLNode* toReturn = temp;
18
                delete node;
19
                return balance(toReturn);
20
            }
21
        } else {
22
            AVLNode* temp = findMin(node->right);
23
            node->data = temp->data;
24
            node->right = del(node->right, temp->data);
25
        }
26
    }
27

28
    return balance(node);
29
}

WARNING
上述操作都需要注意，由于插入和删除操作都对树进行了节点的增删，所以平衡有可能会被打破，这个时候需要调用 balance 方法来维持平衡

查找#

1
bool has(int d) {
2
    if (d == data) return true;
3
    if (d < data) return left ? left->has(d) : false;
4
    return right ? right->has(d) : false;
5
}

修改#

逻辑与查找类似，需要增加赋值的逻辑，不多赘述