二叉查找树（BST）｜搜索及插入操作

什么是二叉查找树？

二叉查找树（BST），又名二叉搜索树是一种基于节点的二叉树数据结构，具有以下属性：  

1. 节点的左子树仅包含值小于自身值的节点。
2. 节点的右子树只包含值大于自身值的节点。
3. 左右子树也必须是二叉搜索树。
4. 不能有重复的节点。

如下图

二叉查找树的上述属性提供了节点值之间的排序，以便可以快速完成搜索、最小值和最大值等操作。如果没有排序，那么我们可能必须比较每个节点值来搜索给定的数值。 

如何在给定的二叉查找树中搜索特定的节值？

为了搜索一个值，如果我们有一个排序数组，我们可以通过二分查找法来进行搜索。假设我们要在数组中搜索一个数字，在二分查找中，我们首先将数组定义为我们的搜索空间，该数字只能存在于该搜索空间内。现在我们将要搜索的数字或要搜索的元素与搜索空间的中间元素（中位数）进行比较，如果正在搜索的记录小于中间元素，我们就在左半边搜索，否则我们继续搜索在右半部分，在相等的情况下我们找到了元素。在二分查找中，我们从搜索空间中的“n”个元素开始，如果中间元素不是我们正在寻找的元素，我们将搜索空间减少到“n/2”，以此类推我们不断缩小搜索空间，直到我们找到想要寻找的值，或者我们将搜索空间缩小到一个元素并停止搜索。

二叉查找树中的搜索操作与上述操作非常相似。假设我们要搜索数字，我们从根开始，然后我们将要搜索的值与根的值进行比较，如果相等，我们完成搜索，如果它更小，我们知道我们需要转到左子树，因为在二叉查找树中，左子树中的所有元素都较小，而右子树中的所有元素都较大。在二叉查找树中搜索元素基本上就是这种遍历，在每一步我们要么向左要么向右，并且在每一步我们丢弃一个子树。如果树是平衡的（如果所有节点的左右子树的高度差不大于 1，我们称树平衡），我们从搜索空间“n”开始节点，当我们丢弃其中一个子树时，我们丢弃“n/2”节点，因此我们的搜索空间减少到“n/2”。在下一步中，我们将搜索空间减少到“n/4”并重复直到找到元素或我们的搜索空间减少到只有一个节点。这里的搜索也是二分查找，因此得名；二叉查找树。

图例：

在下面的树中搜索 6 

1. 从根开始。 
2. 将搜索元素与根进行比较，如果小于根，则递归调用左子树，否则递归调用右子树。 
3. 如果在任何地方找到要搜索的元素，则返回 true，否则返回 false。  

时间复杂度：搜索和插入操作的最坏情况时间复杂度为 O(h)，其中 h 是二叉搜索树的高度。在最坏的情况下，我们可能不得不从根到最深的叶节点。倾斜树的高度可能变为 n，搜索和插入操作的时间复杂度可能变为 O(n)。  

二叉查找树的一些特性：  

1. 二叉查找树的中序遍历总是产生升序的输出。
2. 我们可以构造一个只有 前序 或 后序 或层次遍历的二叉查找树。请注意，我们总是可以通过对特定的遍历进行排序来获得中序遍历。
3. 具有 n 个不同键的不同的二叉查找树的数量是加泰罗尼亚数

  完整示例代码下载链接：

（包含各种语言：C语言、Python、Java，C++等均有示例）

免费​资源下载：二叉搜索树实现