Go 数据结构和算法篇（十七）：二叉排序树

前面已经介绍了二叉树的存储和遍历，今天这篇教程我们以二叉排序树为例，来演示如何对二叉树的节点进行「增删改查」。开始之前，我们先来介绍什么是二叉排序树，以及为什么要引入这种二叉树。

什么是二叉排序树

我们前面已经介绍了很多数据结构，比如数组、链表、哈希表等，数组查找性能高，但是插入、删除性能差，链表插入、删除性能高，但查找性能差，哈希表的插入、删除、查找性能都很高，但前提是没有哈希冲突，此外，哈希表存储的数据是无序的，哈希表的扩容非常麻烦，涉及到哈希冲突时，性能不稳定，另外，哈希表用起来爽，构造起来可不简单，要考虑哈希函数的设计、哈希冲突的解决、扩容缩容等一系列问题。

有没有一种插入、删除、查找性能都不错，构建起来也不是很复杂，性能还很稳定的数据结构呢？这就是我们今天要介绍的数据结构 —— 二叉排序树。

二叉排序树也叫二叉搜索树、二叉查找树，它是一种特殊的二叉树，我们重点关注「排序」二字，二叉排序树要求在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值，所以这么看来，二叉排序树是天然有序的。如果按照上篇教程讲的中序遍历，得到的结果将是一个从小到大的有序数据集：

但是构造二叉排序树的目的，并不是为了排序，而是为了提高查找、插入和删除的速度。不管怎么说，在一个有序数据集上查找数据肯定比无序数据集要快，同时二叉排序树这种非线性结构，也非常有利于插入和删除的实现。

下面我们就来看看如何实现二叉排序树的插入、查找和删除以及它们对应的时间复杂度。

定义二叉排序树

首先，我们需要定义好表示二叉树节点的数据结构，还是通过二叉链表来存储二叉排序树，为了提高代码的复用性，我们将上篇教程定义的 Node 结构体抽取出来放到独立的 node.go 文件：

这里我们通过结构体组合的方式声明二叉排序树的根节点是一个 Node 类型的指针，并为其定义了一个构造函数。

二叉排序树的插入

接下来，我们按照二叉排序树的定义，实现二叉排序树节点的插入方法：

如果是空树，则将其作为根节点，否则判断插入节点数据与当前节点数据值的大小，如果小于当前节点数据值，则递归遍历左子树，找到对应的位置插入，如果大于当前节点数据值，则递归遍历右子树找到对应的位置插入。

我们可以写一段简单的测试代码测试节点插入方法：

这里我们使用了上一篇编写的中序遍历方法 midOrderTraverse，对应的打印结果如下：

二叉排序树的查找

二叉排序树的删除比较复杂，我们先来看查找逻辑的实现，查找实现非常简单，和插入逻辑类似，依次递归比较就好了，直到目标节点数据值和待查找的数据值一致，则返回该节点的指针，或者返回空，表示没有找到：

在上一步编写的测试代码基础上，我们可以通过编写如下代码打印找到节点的对象信息。

执行代码，打印结果如下：

二叉排序树的删除

二叉排序树的删除相对而言要复杂一些，需要分三种情况来处理：

• 第一种情况：如果要删除的节点没有子节点，我们只需要直接将父节点中指向要删除节点的指针置为 nil。比如下图中的删除节点 55。
• 第二种情况：如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如下图中的删除节点 13。
• 第三种情况：如果要删除的节点有两个子节点，这就比较复杂了。我们需要先找到这个节点的右子树中节点值最小的节点，把它替换到要删除的节点上，然后再删除掉这个最小节点。因为最小节点肯定没有左子节点（如果有左子节点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如下图中的删除节点 18。（同理，也可以通过待删除节点的左子树中的最大节点思路来实现）

二叉排序树的删除

根据上面的思路，我们给出二叉排序树节点删除逻辑的实现代码：

执行 search.go，打印结果如下：

二叉排序树的时间复杂度

不论是插入、删除、还是查找，二叉排序树的时间复杂度都等于二叉树的高度，最好的情况当然是满二叉树或完全二叉树，此时根据完全二叉树的特性，时间复杂度是 O(logn)，性能相当好，最差的情况是二叉排序树退化为线性表（斜树），此时的时间复杂度是 O(n)，所以二叉排序树的形状也很重要，不同的形状会影响最终的操作性能，这也就引入了学院君接下来要继续深入介绍的二叉树内容 —— 平衡二叉树和红黑树。

（本文完）