二叉查找树

二叉查找树 (Binary Search Tree)

二叉查找树，又称二叉搜索树，是为了实现快速查找而生的。

💡 树中任意一个节点，其左子树中每个节点值都要小于当前节点值，而右子树中每个节点值都要大于当前节点值。

如何在二叉查找树中查找一个节点？

首先取根节点：

二叉查找树的插入过程类似查找操作。新插入的数据一般都是在叶子节点上，所以只需要从根节点开始，依次比较要插入的数据与节点值的大小关系。

若要插入的数据大于当前节点值：

同理，若要插入的数据小于当前节点值也是类似的判断逻辑。

二叉查找树的删除操作比较复杂，针对要删除节点的子节点数的不同，需要分三种情况来处理。

被删除节点没有子节点，直接将其父节点的 next 指针置为 null 。
被删除节点只有一个子节点，更新其父节点的 next 指针，指向被删除节点的子节点。
被删除节点有两个子节点，需要找其右子树中的最小节点，把它替换到被删除节点上，然后再删除这个最小节点。（因为最小节点肯定没有左子节点，如果有左子节点，那就不是最小节点了）

实际上，关于二叉查找树的删除操作，还有个非常简单、取巧的方法，就是单纯将要删除的节点标记为“已删除”，并不是真正从树中将这个节点去掉。

这样原本删除的节点还需要存储在内存中，比较浪费内存空间，但删除操作就变得简单多了。而且，这种处理方法没有增加插入、查找操作代码实现的难度。

二叉查找树除了支持上面几个操作之外，还有一个重要的特性，中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 **O(n)**，非常高效。因此，二叉查找树又称为**二叉排序****树**。

很多时候，在实际的软件开发中，二叉查找树中存储的是一个包含很多字段的对象。

利用对象的某个字段作为键值 (key) 来构建二叉查找树，把对象中的其他字段称为卫星数据。

上面讲的二叉查找树的操作，针对的都是不存在键值相同的情况。如果存储的两个对象键值相同，这种情况该如何处理？

每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入的数据相同，就将这个要插入的数据放到节点的右子树，即把这个新插入的数据当作大于这个节点的值来处理。

当要查找数据的时候，遇到值相同的节点，并不停止查找操作，而是继续在其右子树中查找，直到遇到叶子节点才停止。

这样就可以把值等于要查找值的所有节点都找出来。

对于删除操作，也需要先查找每个要删除的节点，然后再按上面讲的删除操作的方法，依次删除。

二叉查找树的形态各式各样，对于同一组数据，构造出来的不同二叉查找树，它们的查找、插入、删除操作的执行效率是不一致的。

如下图中第一种二叉查找树，根节点的左右子树极度不平衡，已经退化成了链表，查找的时间复杂度就变成了 O(n)。

上述分析的其实是一种最糟糕的情况。在最理想的情况下，二叉查找树是一棵完全二叉树（或满二叉树）。

此时的插入、删除、查找的时间复杂度是多少？

从前面的例子、图、以及代码来看，不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，即 O(height)。

既然如此，问题就转变成另外一个，如何求一棵包含 n 个节点的完全二叉树的高度？

树的高度等于最大层数 - 1，为了计算方便，将其转换成层来表示。

从上图可以看出，包含 n 个节点的完全二叉树中，第一层包含 1 个节点，第二层包含 2 个节点，第三层包含 4 个节点，依此类推，下面一层节点个数是上一层的 2 倍，第 K 层包含的节点个数就是 2^(K -1)。

不过，对于完全二叉树来说，最底层的节点个数的范围是 1 个到 2^(L -1) 个之间（假设最大层数是 L）。

如果把每一层的节点个数加起来就是总的节点个数 n，即如果节点的个数是 n，那么 n 满足这样一个关系：

1 2	n >= 1 + 2 + 4 + ... + 2^(L - 2) + 1 n <= 1 + 2 + 4 + ... + 2^(L - 2) + 2^(L - 1)

借助等比数列的求和公式，可以计算出，L 的范围是 [log(n + 1), log(n) + 1]。完全二叉树的层数小于等于 log(n) + 1，即完全二叉树的高度小于等于 logn。

显然，极度不平衡的二叉查找树，它的查找性能无法满足工程需求。

需要构建的是一种无论如何删除、插入数据，在任何时候都能保持任意节点的左右子树都比较平衡的二叉查找树。

散列表的插入、删除、查找操作的时间复杂度可以做到常量级 O(1)，非常高效。

而二叉查找树在比较平衡的情况下，插入、删除、查找操作的时间复杂度才是 O(logn)，相对散列表，好像并没有什么优势，那为何还要使用二叉查找树？

有以下几个原因：

散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定。尽管二叉查找树的性能不稳定，但是在工程中，最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
笼统地说，尽管散列表的查找等操作是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决办法比较成熟、固定。
为了避免过多的散列冲突，散列装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。