左偏红黑树稽古 O 二叉查找树与（二叉）平衡树的简易开启方式

Author: sandyzikun

之前笔者简单谈过了二叉树的基础构造与遍历相关操作，这回我们稍微说一说二叉树的简易应用——二叉查找树，以及其进阶——（二叉）平衡树。

Intro

二叉查找树1 (Binary Search Tree，简称BST)，是一类对节点与其左右孩子关系具有约束的二叉树的统称。
其最明显的性质是如若该树不为空，则其 任何节点的值大于其左孩子的值、小于其右孩子的值 （反之即左孩子>本体>右孩子亦然，但一般很少反过来定义，因为效果其实没什么两样）。
基于这一性质，我们能明显地看出来这样一棵树的中序遍历是递增的，因此这也经常作为一种有序数据结构，用于对元素的排序。

（二叉）平衡树 (Balanced Tree，简称BT)，是一类对节点数量加以约束的二叉查找树的统称。
这一类查找树的特点在于会尽量避免查找树某个节点一侧的节点量过大、节点过多，从而在某些极端情况下也能避免查找时的时间复杂度过高。

BST

二叉查找树的简介。

二叉查找树是一种树形数据结构，满足以下特征：

  1. 空树是二叉查找树；
  2. 任何节点的值（如若左孩子存在）大于其左孩子的值、（如若右孩子存在）小于其右孩子的值；
  3. 正如二叉树是递归定义的一样，二叉查找树也是递归定义的一样——二叉查找树的左右子树也是二叉查找树，也满足相关性质。

因为二叉查找树本质上也是二叉树，没有需要特殊结构才能实现的功能，因此其节点的定义与二叉树是一样的：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Node {
    int val;
    struct Node *parent, *lchild, *rchild;
} *root;
struct Node * new_node(int _value) {
    // 类比高级语言中的对象构造函数并加以简单封装。
    // 除了指向母亲节点与左右孩子的指针外，目前的节点结构中没有除了`val`之外其他的成员，
    //  因此此处初始化中，仅需要对`val`进行赋值。
    struct Node * q = (struct Node *)malloc(sizeof(struct Node));
    q->val = _value;
    q->lchild = nullptr;
    q->rchild = nullptr;
    q->parent = nullptr;
    return q;
}

使用结构体数组模拟的静态实现、使用Python等高级语言的对象引用机制的实现当中的定义与上面的相似，于此不再赘述。
因此二叉查找树的遍历也与普通的二叉树相仿，在此列举出先序遍历与中序遍历的方法。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void __preorder(struct Node *rt) {
    if (rt != nullptr) {
        printf(" %d,", rt->val);
        __preorder(rt->lchild);
        __preorder(rt->rchild);
    }
}
void __inorder(struct Node *rt) {
    if (rt != nullptr) {
        __inorder(rt->lchild);
        printf(" %d,", rt->val);
        __inorder(rt->rchild);
    }
}
void printall() {
    __preorder(root);   putchar('\n');
    __inorder(root);    putchar('\n');
}

Searching

作为二叉查找树，其与应用最为直接相关的功能即为search。
根据性质3知道我们可以递归遍历二叉查找树以寻找所求值，性质2决定遍历时每一步的方向，性质1用于部分情况的判断。
大致的思路如下：

  • 如若这个节点==nullptr，则以其为根的树是空树，所以遍历到该节点后，便找不到所求的_target值，此时返回nullptr以表示在树上不存在带有所求值得节点；
  • 如若当前节点带有的值即为所求，即返回当前节点的位置；
  • 如若当前节点带有的值!=所求值，则
    • 所求值<当前节点带有的值->在左子树中继续寻找，
    • 所求值>当前节点带有的值->在右子树中继续寻找。
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Node * __search(struct Node *rt, int _target) {
    if (rt == nullptr)
        return nullptr;
    else if (_target == rt->val)
        return rt;
    else {
        if (_target < rt->val)
            return __search(rt->lchild, _target);
        else
            return __search(rt->rchild, _target);
    }
} inline bool search(int _target) {
    return __search(root, _target) != nullptr;
}

在这里我们容易看出，函数__search返回的是带有值_target的节点所在的位置，然后函数search通过审察该位置是否存在节点以判断树中是否存在所求的值_target。

Insertion

二叉查找树所模拟的是一个集合，因此其中所有的元素如若存在，则唯一。
为了保证这一点，我们再插入之前应当先判断行将插入的元素是否已经存在于该树当中，如若不存在，则再插入它。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Node * __insert(struct Node *rt, int _value) {
    if (rt == nullptr)
        return new_node(_value);
    else {
        if (rt->val != _value) {
            if (_value < rt->val) {
                rt->lchild = __insert(rt->lchild, _value);
                rt->lchild->parent = rt;
            } else {
                rt->rchild = __insert(rt->rchild, _value);
                rt->rchild->parent = rt;
            }
        }
        return rt;
    }
} inline void insert(int _value) {
    root = __insert(root, _value);
}

以上过程中，递归的每一步中，函数__insert返回的是节点rt本身的位置，这个返回过程像是在确认 我就是我，我的左孩子就是我左下方那位、有孩子就是我右下方那位 一样，这个过程会在后面涉及到旋转操作的平衡树中用到。

Rotation

一般而言只有在部分平衡树中会用到的操作，旋边。
~~但笔者对二叉查找树的删除操作进行了优化，其中可能会用到，故于此进行简单讲解。 ~~
由于笔者在构思时出了一点错误，所以关于该方法，在此暂不进行讲述。

二叉树的旋边是针对边(edge)进行的操作，分为左旋和右旋两种。

旋边有一条非常重要而且好用的性质，那就是：旋边不改变中序遍历顺序！
这一点很容易看出来，其相关证明笔者不在此赘述。

Left Rotate

如上图，左旋是对某一个节点及其右孩子进行的操作。
左旋时，连接节点与其右孩子的边逆时针旋转，使节点成为原本右孩子的左孩子，而后接管其左孩子，使之成为自己的右孩子。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Node * rotate(struct Node *rt) {
    /**
     * Left Rotate an Edge...
     *        [1]               [2]
     *        / \               / \
     *       *  [2]    ==>    [1]  *
     *          / \           / \
     *         O   *         *   O
     */
    Node * newroot = rt->rchild;
    if (newroot != nullptr) {
        // 处理被旋边所连接的两个节点指向母亲与孩子的指针。
        rt->rchild = newroot->lchild;
        newroot->lchild = rt;
        newroot->parent = rt->parent;
        rt->parent = newroot;
        // 如若需要接管的孩子不为空，则更新其指向母亲节点的指针。
        if (rt->rchild != nullptr)
            rt->rchild->parent = rt;
        return newroot;
    }
}

于是，当我们需要左旋连接节点node及其右孩子的边的时候，如下形式调用函数rotate即可完成旋边操作：

C++
1
node = rotate(node);

Right Rotate

右旋操作与上方左旋操作类似。

C++
1
2
3
4
5
6
7
8
9
10
11
12
struct Node * rotrev(struct Node *rt) {
    Node * newroot = rt->lchild;
    if (newroot != nullptr) {
        rt->lchild = newroot->rchild;
        newroot->rchild = rt;
        newroot->parent = rt->parent;
        rt->parent = newroot;
        if (rt->lchild != nullptr)
            rt->lchild->parent = rt;
        return newroot;
    }
}
C++
1
2
// For Instance ...
node = rotrev(node);

Removing

二叉查找树的删除操作需要在进行的时候维持相关的性质。
对于部分二叉查找树，删除过程会被特化为两种，一种是如同对优先队列进行pop操作的删除最小值remove_min，另一种是删除指定值，即remove。

对于待删除节点，由于二叉树、二叉查找树都是递归定义的数据结构，所以往往需要维护其左右子树在该节点被删除后不破坏二叉查找树的性质。
对于朴素二叉树，此时要考虑左子树是否存在、右子树是否存在两个相互独立的问题所组成的四种情形：

  1. 左右子树皆不存在：待删除节点为一片叶子：此时的解决方案便是直接删除该节点，无需考虑左右子树的维护问题；
  2. 右子树不存在，待删除节点有且仅有左子树：此时的解决方案便是使左孩子取代待删除节点，若待删除的并非根节点，便由母亲节点接管其左子树；
  3. 仅左子树不存在的情况，可以类比如上方法；
  4. 左右子树皆存在，此种情况的处理较为复杂。传统的处理便是保留其左子树，使其右孩子取代待删除的节点，即把右孩子的值复制到待删除节点上，然后递归删除右孩子（保留右子树并以左孩子进行取代亦可）。但笔者在此想到一种方案，便是把同时具有左右子树的节点通过旋边变成仅仅具有左子树的节点，实现其的操作便是左旋连接待删除节点与其右孩子的边。旋边后待删除节点会携左子树移动到原本左孩子的位置上，而原本的右孩子成为待删除节点的母亲节点。如若原本的右孩子的左子树不为空，则会由待删除节点接管并成为其右子树，此时则继续旋边，直到待删除节点不具有右子树为止。然后如2.中所言，以其左孩子取代待删除节点即可。

具体程式笔者在此不再赘述。

BT

何为平衡？为何平衡？在考虑这些问题之前请让我们先审察一种情形：

当我们从某时起，向二叉查找树加入的元素总是加入在上一个加入的元素下方，从某一个节点开始便会只具有左孩子或右孩子，从而形成一条“长链”。
此时的二叉查找树中以某一个节点为根的子树便会退化为一条线性表（链表），极端不理想情况下，沿着那一条“长链”遍历的时间复杂度便会升至O(m)。
如若能够控制从根节点出发的每一条路径长度都大致相等，则不理想情况下，遍历的时间复杂度也能控制在O(log m)左右。
由此便引入二叉查找树中的一个重要概念，那便是，平衡。

我们可以先感性地理解一下：所谓平衡树便是每个节点左右子树大致相当的二叉查找树。
但对于不同种类的平衡树，其所定义的平衡也不一样，以下将简单介绍两种常见的二叉查找树的平衡：

  1. 弱平衡（期望平衡）：多见于Treap2或Splay3；
  2. 高度平衡：多见于AVL4平衡树，其核心在于任意节点的左右子树高度差不超过一。

References

笔者引用的一些参考文献，以及希望给出的一些相关资料与题目，供大家辅助参考理解二叉查找树与平衡树的相关概念。