二叉树搜索树(程序员都知道)

如果您是一个开发人员，不熟悉此数据结构，那么现在是该了解该数据结构的时候了。继续阅读基本知识。

二叉搜索树

在上一篇文章中，我们介绍了一个二叉树，它是关于存储数据的形状的。二叉搜索树(BST)是对该结构的进一步增强。

第一个重要的变化是，我们存储的数据需要一个键;如果我们有一个基本类型，比如字符串或数字，那么值本身可以是键，如果我们有一个更复杂的类，那么我们需要在这个结构中定义一个键，或者我们需要为每个条目构建一个唯一的键。

第二个更改是比较这些键的方法，这些键对于数据结构的性能至关重要。数字是最简单的，因为我们可以很容易地比较哪个更大，哪个更小。

第三个也是最后一个改变是我们储存的方式;左节点的键总是小于父节点的键，右节点的键总是大于父节点的键。

举个例子，这里有一个只使用数字作为键的BST:

请注意，左边的所有节点都比它们的父节点和上面的所有父节点小。

为什么?

那么，我们为什么要关心BST呢?我们应该关注搜索，因为搜索在里面表现得很好，因为每次你向下移动一个深度，你就会消除大约50%的潜在节点。

例如，如果我们想要在我们的例子中找到关键的66，我们可以从根(50)开始，然后往右移动。在这一点上，我们立即消除了8个可能的节点。下一个节点位于节点左边，包含70个节点(总共可能删除12个节点)。下一个是节点的右边，值为65，然后是66的左边，67的左边。我们找到了5步的节点。

用大O符号表示，这意味着我们的性能接近O(log n)，当树不是最优或不平衡的时候，O(n)可能是最坏的情况。

平衡与不平衡

在上面的例子中，我们有一个二叉搜索树，它是最优的，也就是说它的深度是最低的。下面我们可以看到一个完全有效的BST;每个子节点都在父节点的右边，因为它比父节点大。

然而，这将导致O(n)搜索性能不理想。解决方案是重新平衡BST，在上面的例子中，我们可以得到多个结束状态（我将在下面展示两个）。关键是我们从5到3的深度。

实现

. net有一个带有SortedDictionary的内置实现。不幸的是，在JavaScript或Java中没有现成的方法。