Binary Sort Tree, 又称二叉搜索树，二叉查找树 Binary Search Tree。
出现时间可以追溯到计算机刚出现的年代，是几百年的遗产。属于幼儿园大班级别的数据结构知识。
思维结构极其简单，重在学习代码结构，与一些扩展算法应用。
幼儿园必知必会

任何数据结构最有价值的依然是思维模型。

序言

数据排序也是一种极其实用的数据组织方式，可以快速解决排名类的问题。因此在"算法"领域中，有一类专门研究针对无序数据的"排序"算法的大类，如冒泡、插入、归并、快排等等，都是对线性表结构的排序算法。
然而我们在解决问题时，不仅仅可以站在算法角度，还能够站在数据结构的角度，直接设计维护一个数据结构让我们在数据插入和删除等各种操作后，最后依然是有序的数据。
基于计算机幼儿园小班的知识储备，至少可以想得到两种数据结构方案：

  1. 维护一个有序的高级数组:

    • 数据插入时： 二分查找恰当的插入位置(O(logN)) + 插入新数据(O(N))。 总复杂度O(N)
    • 数据删除时： 二分查找待删除数据的位置(O(logN)) + 删除数据(O(N))。 总复杂度O(N)
    • 数据查询时： 按排名索引 O(1)

  2. 维护一个有序的高级链表:

    • 数据插入时： 从头节点依次找到恰当插入位置(O(N)) + 插入新数据(O(1))。 总复杂度O(N)
    • 数据删除时： 从头节点依次找到待删除数据位置(O(N)) + 删除数据(O(1))。 总复杂的O(N)
    • 数据查询时： 按排名索引 O(N)

可以看得出上述两种有序数据结构在性能方面，没有大区别。那么为什么我们从不会去学习上述两个数据结构呢？ 因为过于低级了，而且还有另一个更加优秀的解决方案：二叉排序树。它同时吸取结合了有序数组快速二分查找的优势，与链表的快速插入删除的优势。

BST结构性质

非常简单，仅3点：

  1. 左子树 < 根节点
  2. 右子树 > 根节点
  3. 中序遍历结果就是一个有序的序列

对树中的任何节点而言，左子树为空或所有数据都小于自己，右子树为空或所有数据都大于自己。

用途：解决一切与排名相关的检索需求。

插入操作

待插入的新数据从根节点出发，比根节点小就走左方向，比根节点大就走右方向。通过递归的方式，直至走到头。
因此新插入的数据一定就是叶节点（重复值不会插入）。

BST插入操作插图待制作

删除操作

删除操作稍复杂，需分情况讨论：

  1. 删除叶节点，直接删除。
  2. 删除度为1的节点。
    • 把它唯一的「孤儿子树」直接挂在它的父节点上，位置不变。
  3. 删除度为2的节点，替换成删除度为1或0的节点情况。
    • 该节点的前驱：左子树最大值
    • 该节点的后继：右子树最小值
    • 用前驱或后继来替换当前节点，然后再去删除用来替换的前驱或后继节点（也是通过递归的方式）。

度就是节点的孩子个数。
删除度2节点只需要找前驱或者后继其中一个点来替换就行，不需前驱点和后继点都找出来。
代码已找前驱点为例。

BST删除操作插图待制作

复杂度分析

假设当前BST的树高是H。

  1. 插入数据时：复杂度就是递归的次数，最多也就是H次。 总复杂度O(H)。
  2. 删除数据时：最坏情况需要先找前驱或后继(O(H))，递归删除最坏也是(O(H))。 总复杂度O(H)。
  3. 查询数据时：也是根据规则一步走一层向下搜索，最多搜索H次。 总复杂度O(H)。

因此复杂度与树高H息息相关。
对二叉排序树而言，极其依赖输入的数据特点。第一个输入的数据点就是一切的起源，根节点，且不会再改变了。

  • 假如后续的输入数据是完全有序的，最终BST会退化成一个链表，此时树高H就是数据规模N。
  • 假如后续的输入数据是完全无序的，假设最终BST形成一个完美的平衡状态，此时树高H就是log(N)

树形结构不同，导致性能也不同。所以 不同的树形结构之间 不同的本质其实在于：平均查找次数不同，即查找效率不同

平均查找次数：每个节点被找到所需次数的期望，基于的假设是每个节点都是等概率的被查找。

总次数节点数\frac{总次数}{节点数}

自然而然地，幼儿园的孩子们基本都会产生以下问题和新的学习方向：

  1. BST的根节点不会变，因此它的结构极其依赖数据输入的顺序。那么有没有一种数据结构: 它既可以保持BST的性质，又能自适应的调整根节点，始终保持一种平衡的树结构呢？ 有，是数据结构中研究的一个大类：平衡二叉排序树。包括AVL树，红黑树等等。（小学内容）

  2. 基于上面平均查找次数的假设，每个节点都是等概率被查找的。那假如真实情况里每个节点不是等概率被查找的呢？比如就存在有一些数据被用户频繁的搜索，一些数据自从存入就鲜有人问津。那么被频繁查询检索的数据节点是不是更应当靠近树根，使得查询次数少一些？ 是的，而且也已经有一种解决该问题的平衡二叉排序树结构：伸展树（小学内容）

二叉排序树最坏性能是O(N)，最优性能是O(logN)，碾压最初提出的 高级数组结构 和 高级链表结构。
高级数据结构多种多样。他们往往都是从基础数据结构出发，改善了一个应用场景的性能，就创造了一个我们又要去学习的高级数据结构。
很大部分高级数据结构其实都早已是古老的遗产了，由于他们解决的问题恰好应对了我们实际应用时的痛点，才能够历久弥新。然而他们提出的问题也并未有多巧妙、多难以想象。最珍贵的是学习前辈们为了解决这些问题的思维方式和解决方案，这就是高级数据结构的学习价值所在。
重视珍惜我们生活工作中遇到的种种奇怪问题是最简单的事情，但能否进一步下定决心、憋一口劲、坚持不懈的研究出可靠的解决方案、并持续优化这些问题呢？能否成功还是需要我们平时日复一日的海量经验观察与知识积累。

基础版二叉排序树代码演示

树形结构比较抽象，即使理解了思维模型，翻译成代码是有难度的。重点学习代码结构和技巧。

1. 头文件定义

#include <stdio.h>
#include <stdlib.h>
#define DATA(n) (n ? n->data : 0)
#define L(n) (n ? n->lchild : NULL)
#define R(n) (n ? n->rchild : NULL)

typedef struct Node {
    int data;
    struct Node *lchild, *rchild;
} Node;

// 结构操作
Node *getNewNode(int data);          // 创建新节点
Node *insert(Node *root, int data);  // 插入数据
Node *predecessor(Node *root);      // 寻找前驱节点（为删除操作服务）
Node *erase(Node *root, int data);   // 删除数据
void clear(Node *root);             // 析构树
int search(Node *root, int val);    // 查找数据
void printNode(Node *root);         // 打印单节点信息
void output(Node *root);            // 中序遍历打印整棵树
  • Node 结构是树中的任意节点，只有值、左子节点指针 与 右子节点指针 3个属性。
  • getNewNode 和 clear 是最最基础的创建节点与析构树操作。
  • insert, predecessor, erase 是维护BST结构性质的 数据插入 和 数据删除 操作。重点学习部分
  • search 功能较简单，仅仅是判断数据是否在树中。
  • printNode 和 output 一起协作打印整棵树BST的信息。

2. 源文件代码

Node *getNewNode(int data) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = data;
    p->lchild = p->rchild = NULL;
    return p;
}

Node *insert(Node *root, int data) {
    // 插入数据data：返回根节点指针
    if (root == NULL) return getNewNode(data); // 成功到达叶节点，生成新节点插入
    if (root->data == data) return root; // 出现重复值，开始回溯
    // 核心插入逻辑：
    if (root->data > data) root->lchild = insert(root->lchild, data);
    else root->rchild = insert(root->rchild, data);
    return root;
}

Node *predecessor(Node *root) {
    // 找前驱: 返回左子树的最大值节点
    Node *temp = root->lchild;
    while (temp->rchild) temp = temp->rchild;
    return temp;
}

Node *erase(Node *root, int data) {
    // 删除数据data：返回根节点指针
    if (root == NULL) return NULL;
    // 先找到待删除数据的位置
    if (data < root->data) {
        root->lchild = erase(root->lchild, data);
    } else if (data > root->data) {
        root->rchild = erase(root->rchild, data);
    } else {
        // 当前节点root就是待删除的节点
        if (root->lchild == NULL || root->rchild == NULL) {
            // 情况1：度为 0 或 1
            Node *temp = root -> lchild ? root->lchild : root->rchild;
            free(root); // 释放当前节点空间
            return temp;
        } else {
            // 情况2：度为 2
            Node *temp = predecessor(root); // 找前驱节点
            root->data = temp->data;
            root->lchild = erase(root->lchild, temp->data); // 递归往左子树删除前驱节点。
            return root;
        }
    }
    return root;
}

int search(Node *root, int val) {
    // 查找值。0：失败； 1：成功
    if (root == NULL) return 0;
    if (root->data == val) return 1;
    if (root->data > val) return search(root->lchild, val);
    return search(root->rchild, val);
}

void clear(Node *root) {
    // 递归析构
    if (root == NULL) return;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return ;
}

void printNode(Node *root) {
    // 打印单个节点信息
    printf("(%d, %d, %d)\n", root->data, DATA(L(root)), DATA(R(root)));
}

void output(Node *root) {
    // 中序遍历
    if(root == NULL) return;
    output(root->lchild);
    printNode(root);
    output(root->rchild);
    return ;
}
  • insert 和 search 操作基本一致。
  • 重点关注 insert 和 erase 操作，严格维护BST的性质。erase 中的将度1和度0情况代码合并优化了，仅是代码长度优化，实际结构操作逻辑没有任何变化。
  • 需注意 insert 和 erase 函数的返回值都是 Node *。 因为根节点可能会变化，所以要返回新的根节点值。这里的根节点不是狭义的根节点（树根），而是可以把任何节点都当成根节点，叶子节点也是没有孩子的根节点。
  • predecessor 函数实际是不完整的，当前版本只适用于找度2节点的前驱。对于没有左子树的度1节点和度0节点找前驱都是有bug的。但在以上场景足够用了，对度1和度0节点，我们没有找前驱的需求。
  • 代码难点在于理解和熟悉递归操作。

3. 测试程序

int main() {
    int op, val;
    Node *root = NULL;
    while (~scanf("%d%d", &op, &val)) {
        switch(op) {
            case 0: printf("search %d, result : %d\n", val, search(root, val)); break;
            case 1: root = insert(root, val); break;
            case 2: root = erase(root, val); break;
        }
        if (op) {
            printf("look:\n");
            output(root);
            printf("-------------------------\n");
        }
    }
    return 0;
}

递归小提示

所有有关树形结构的操作几乎都离不开递归代码（虽然像以上版本的insert和search函数也可以用while循环解决，但是erase用循环就稍复杂）。递归的代码技巧是计算机幼儿园的孩子们毕业必须要掌握的

以上的BST中的递归逻辑比较简单，都是单线操作，单线到头了就开始单线回溯。不像深搜多条路径的问题，回溯到中途发现有岔路了又会往深处继续递归寻找新路径，更复杂一些（画递归树帮助理清过程）。但其实递归原理是一种非常标准的栈结构，熟悉后会觉得非常简单优雅 并且爱上它。

我第一次接触递归代码是求阶乘和斐波那契数列，当时的感觉是和循环差不多。于是形成了一种错觉：任何递归格式的代码理应都可以翻译成循环格式的代码，那么只用学好容易理解的循环就够了，并且所有场景都用循环解决。但其实是不太准确的。递归相较于循环其实还是要稍微高级一点点。递归是一个动态的栈结构。

递归代码很妙的一个地方在于：不同于单次循环，递归多了一个回溯的过程。简单来说，递归程序跑到了单次循环的终点后，还很聪明地自己再原路回到起点。比如教会狗狗出去扔垃圾，回来再顺便取封信回来。
通过灵活地写代码 可以安排递归程序在去的路上执行一些特定事务，回的路上再顺便执行一些事务。一般情况而言：

  • 递归调用代码之前的部分 都是在往终点去的路上要做的事情。
  • 递归调用代码之后的部分 就是回到起点路上要做的事情。
    像那些在一去一回路上要办的事情又多又杂的情况下，用循环下指令 恐怕很难把逻辑理清并把代码写得很干净。

递归可分为 "头递归" 和 "尾递归" 两种。关键在与想象栈结构，先push到终点再pop回起点，递归过程就很容易明白。
因此递归的缺点就是会占用很多内存资源，递归太深，内存恐怕装不下栈造成段错误。而且一去一回的过程时间开销也不小。除此之外，我觉得递归调用剩下的全是优点了，代码简洁优雅，好好整理一下也易读。
当然递归有许多奇怪的写法，有时需要考虑过程中返回值如何传递等等。

应用扩展

目前基础版的BST代码只实现了对结构性质的维护。真正对用户有价值的功能，只有search和output，未免过于鸡肋。既然是为了解决「排名」需求，那么至少还需要提供两个用户查询功能：

  • 排名第k位的元素值是多少？
  • 排名前k为的元素有哪些？ Top-k 问题

  1. 如何解决排名K的检索问题？

    • 假如当前节点的左子树大小为k-1，当前节点就一定是第k位元素。
    • 解决方案：节点增加size属性，代表当前节点为根的树大小。
      • LS 为root左子树的size
      • LS == k - 1 则root为第k位元素
      • LS > k - 1 则第k位元素在左子树中，递归查找左子树的第k为元素
      • LS < k - 1 则第k位元素在右子树中，递归查找右子树的第(k - LS - 1) 位元素。
      • 特别注意：LS == k 并不能代表左子节点就是第k位元素！

  2. 如何解决Top-k问题？（小于排名第k位的所有元素）

    • 基于问题1的解决方案，Top-k问题也非常简单。
    • 情况1：LS == k - 1 则输出左子树 和 root值。
    • 情况2：LS > k - 1 则再去左子树找所有小于第k位的值。
    • 情况3：LS < k - 1 则输出左子树 和 root值，再去找右子树中所有小于 第(k - LS - 1) 位的值。

二叉排序树 与 快排算法

熟悉幼儿园大班快排算法的原理后，很容易发现Top-k解法和快排太像了。

快排核心操作就是：选取一个基准值，然后做partition操作。基准值就是根节点X，partition就是分成左右子树，左part都小于X，右part都大于X。

所以"快排算法"在思维逻辑上借鉴的就是二叉排序树的核心思想，即使它并没有真的构造出一个二叉排序树。

// 基础快排代码（无任何优化版本）
void quick_sort(int *num, int l, int r) {
    // 边界条件
    if (l > r) return;
    // 构造左右partition
    int base = num[l], a = l, b = r;
    while(a < b) {
        while (a < b && num[b] >= base) --b;
        if(a < b) num[a++] = num[b];
        while (a < b && num[a] < base) ++a;
        if(a < b) num[b--] = num[a];
    }
    num[a] = base;
    // 递归快排两部分
    quick_sort(num, l, a-1);
    quick_sort(num, a+1, r);
    return;
}

思考1：快排的时间复杂度 和 二叉排序树 之间的关系？
思考2：快排衍生出来的 快速选择算法(Top K 问题) 和 二叉排序树 之间的关系 ？

一旦深刻理解了数据结构的思维模型，数据结构和算法就是相辅相成的。算法的思维模型和数据结构的思维模型就是可以互相借鉴的。

优化：升级版BST代码

1. 头文件定义变化

#define SIZE(n) (n ? n->size : 0)

// 新增size属性
typedef struct Node {
    int data, size;
    Node *lchild, *rchild;
} Node;

// 修改方法
Node *getNewNode(int data);          // 创建新节点
Node *insert(Node *root, int data);  // 插入数据
Node *erase(Node *root, int data);   // 删除数据

// 新增方法
void update_size(Node *root);       // 更新节点树大小size
int search_k(Node *root, int k);    // 查找排名第k的数据
void output_k(Node *root, int k);   // 打印 Top-k 的数据
  • getNewNode, insert, erase 内部都新增更新size的操作。更新size的步骤完全封装在update_size函数中。
  • search_k 与 output_k 函数都是基于 size 属性实现排名检索的需求。

2. 源文件代码变化

Node *getNewNode(int data) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = data;
    p->size = 0;
    p->lchild = p->rchild = NULL;
    return p;
}

void update_size(Node *root) {
    // 更新size 即左子树size + 右子树size + 1（root自己）
    root->size = SIZE(root->lchild) + SIZE(root->rchild) + 1;
    return;
}

Node *insert(Node *root, int data) {
    if (root == NULL) return getNewNode(data);
    if (root->data == data) return root;
    if (root->data > data) root->lchild = insert(root->lchild, data);
    else root->rchild = insert(root->rchild, data);
    update_size(root); // 回溯更新size
    return root;
}

Node *erase(Node *root, int data) {
    if (root == NULL) return NULL;
    if (data < root->data) {
        root->lchild = erase(root->lchild, data);
    } else if (data > root->data) {
        root->rchild = erase(root->rchild, data);
    } else {
        if (root->lchild == NULL || root->rchild == NULL) {
            Node *temp = root->lchild ? root->lchild : root->rchild;
            free(root); 
            return temp; // 这里不用更新size，因为度1节点root的子节点向下都不需要更新size
        } else {
            Node *temp = predecessor(root);
            root->data = temp->data;
            root->lchild = erase(root->lchild, temp->data);
        }
    }
    update_size(root); // 回溯更新size
    return root;
}


int search_k(Node *root, int k) {
    // 返回排名第k位的元素值
    if (root == NULL) return -1; // 失败，比如k超过整棵树的size了
    if (SIZE(root->lchild) == k - 1) return root->data;
    if (SIZE(root->lchild) > k - 1) return search_k(root->lchild, k);
    return search_k(root->rchild, k - SIZE(root->lchild) - 1);
}

void output_k(Node *root, int k) {
    // 打印前k位元素
    if (k == 0 || root == NULL) return ;
    if (SIZE(root->lchild) > k - 1) {
        // 递归左子树
        output_k(root->lchild, k);
    } else {
        // 打印左子树和根节点，然后递归右子树
        output(root->lchild);
        printNode(root);
        output_k(root->rchild, k - SIZE(root->lchild) - 1);
    }
}
  • 重点关注 search_k, output_k 两个函数。逻辑都很简单。

3. 测试程序

int main() {
    int op, val;
    Node *root = NULL;
    while (~scanf("%d%d", &op, &val)) {
        // 每次输入两个值：操作 + 值
        //getchar();
        switch (op) {
            case 0: printf("search %d, result : %d\n", val, search(root, val)); break;
            case 1: root = insert(root, val); break;
            case 2: root = erase(root, val); break;
            case 3: printf("search k = %d, result = %d\n",
                           val, search_k(root, val)); break;
            case 4: output_k(root, val); break;
        }
        if (op) {
            printf("\n");
            output(root);
            printf("----------------------\n");
        }
    }
    return 0;
}

总结

相比于一开始假想的 "高级有序数组结构" 和 "高级有序链表结构"，明显有序的 "二叉排序树结构" 更加高级。
最优情况时，BST的任何操作复杂度都是O(logN)，唯一输给了高级有序数组排名检索的O(1)复杂度。
但是BST的取舍明显非常地值得，完美的平衡BST结构，面对21亿的数据量时，每一次的数据插入、删除、检索都能在31次之内完成。
这就是设计和创造模型的魅力。

二叉排序树的性质非常简单，重点还是学习代码编写的技巧。
当然任何数据结构最具价值的依然是思维模型
为加深对二叉排序树的理解，可加练一些非常基础的二叉树题目：

由于二叉排序树的性能极其依赖树形结构，下一章学习能够自适应调整的平衡二叉树结构：AVL树。