二叉树在 这篇文章 中讲到过了，其中讲述了二叉树的各种性质，特点

(资料图)

二叉查找树

今天我们就要学习一棵特别的二叉树 —— 二叉查找树 ( Binary Search Tree , 即 BST )

怎么样的一棵树才能称作二叉查找树呢，当然是要能够查找，所以在这棵二叉树上，每一个结点都储存着一个能够比较大小的值，让我们可以按照顺序排序以及查找它们，例如下面的两个都是二叉查找树 ( 顺序为左子树 < 根结点 < 右子树 )

在二叉查找树中，其任意一棵子树都是二叉查找树

所以，二叉查找树的中序遍历是一个有序的序列，例如上面两棵二叉树的中序遍历为

当我们要在二叉查找树上查找一个数时，需要从根结点开始，一步一步向根深处走去，例如在二叉查找树.1中，我们要查找 12，根据这棵二叉树的性质 ( 即左子树的值 < 右子树 )，我们知道在第一步中 ( 根结点中 )，因为 ，所以我们需要在右子树中寻找 12，而不是去左子树中寻找，因为左子树上所有结点的值均小于根结点

于是我们寻找到了 19，虽然这次我们只能向左子树走，但是当存在右子树时，我们也知道应该向左子树走，因为 ，右子树中的值绝对大于 12，所以 12 绝对在其左子树

相比数组查询某个特定的值的位置需要 次，二叉查找树仅查找了 ，要快上很多，原因是每次向下查找时，都排除了一半的结点，但是所有的二叉查找树都会更快吗

这不一定，如果二叉查找树长成 二叉查找树.2的样子，查找一个数的时间复杂度与使用数组就没有区别了，因为在查找时，每次向下查找都只排除了 1 个结点，导致效率低下，这时我们称这棵二叉查找树退化成为了链，是退化的

而像 二叉查找树.1这样，根结点到任意一个结点的距离小于等于  的二叉查找树则称为平衡的二叉查找树

想都不用想，我们自然希望查找某个数时花费的时间最少，因此我们就希望一棵树要在插入和删除结点时要一直维持它的平衡状态，让查找效率保持一个较高的水平

为了维持二叉查找树的平衡，我们就需要用到平衡树

当然这篇文章不讲

好了那么关于二叉查找树的内容就讲到这里了，如果你觉得本篇文章对你有所帮助的话，请不要忘记三连支持！

标签：