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

什么是二叉查找树？
二叉查找树（BST），又名二叉搜索树是一种基于节点的二叉树数据结构，具有以下属性：
节点的左子树仅包含值小于自身值的节点。节点的右子树只包含值大于自身值的节点。左右子树也必须是二叉搜索树。不能有重复的节点。
如下图
二叉查找树的上述属性提供了节点值之间的排序，以便可以快速完成搜索、最小值和最大值等操作。如果没有排序，那么我们可能必须比较每个节点值来搜索给定的数值。

文章插图
如何在给定的二叉查找树中搜索特定的节值？
为了搜索一个值，如果我们有一个排序数组，我们可以通过二分查找法来进行搜索。假设我们要在数组中搜索一个数字，在二分查找中，我们首先将数组定义为我们的搜索空间，该数字只能存在于该搜索空间内。现在我们将要搜索的数字或要搜索的元素与搜索空间的中间元素（中位数）进行比较，如果正在搜索的记录小于中间元素，我们就在左半边搜索，否则我们继续搜索在右半部分，在相等的情况下我们找到了元素。在二分查找中，我们从搜索空间中的“n”个元素开始，如果中间元素不是我们正在寻找的元素，我们将搜索空间减少到“n/2”，以此类推我们不断缩小搜索空间，直到我们找到想要寻找的值，或者我们将搜索空间缩小到一个元素并停止搜索。
二叉查找树中的搜索操作与上述操作非常相似。假设我们要搜索数字，我们从根开始，然后我们将要搜索的值与根的值进行比较，如果相等，我们完成搜索，如果它更小，我们知道我们需要转到左子树，因为在二叉查找树中，左子树中的所有元素都较小，而右子树中的所有元素都较大。在二叉查找树中搜索元素基本上就是这种遍历，在每一步我们要么向左要么向右，并且在每一步我们丢弃一个子树。如果树是平衡的（如果所有节点的左右子树的高度差不大于 1，我们称树平衡），我们从搜索空间“n”开始节点，当我们丢弃其中一个子树时，我们丢弃“n/2”节点，因此我们的搜索空间减少到“n/2” 。在下一步中，我们将搜索空间减少到“n/4”并重复直到找到元素或我们的搜索空间减少到只有一个节点。这里的搜索也是二分查找，因此得名；二叉查找树。
图例：
在下面的树中搜索 6

文章插图
从根开始。将搜索元素与根进行比较，如果小于根，则递归调用左子树，否则递归调用右子树。如果在任何地方找到要搜索的元素，则返回 true，否则返回 false 。
时间复杂度：搜索和插入操作的最坏情况时间复杂度为 O(h)，其中 h 是二叉搜索树的高度。在最坏的情况下，我们可能不得不从根到最深的叶节点。倾斜树的高度可能变为 n，搜索和插入操作的时间复杂度可能变为 O(n) 。
【BST二叉查找树｜搜索及插入操作】二叉查找树的一些特性：
二叉查找树的中序遍历总是产生升序的输出。我们可以构造一个只有前序或后序或层次遍历的二叉查找树。请注意，我们总是可以通过对特定的遍历进行排序来获得中序遍历。具有 n 个不同键的不同的二叉查找树的数量是加泰罗尼亚数完整示例代码下载链接：
（包含各种语言：C语言、、Java，C++等均有示例）
免费?资源下载：二叉搜索树实现