使用二叉搜索树来解决什么类问题？

Question

我已经看到这个数据结构谈了很多,但我不清楚什么样的问题需要这样的数据结构(通过替代表示).我从来不需要一个,但也许那是因为我不太喜欢它.你能开导我吗？

Answer 1

使用二进制搜索树的一个示例是要快速添加元素的值的排序列表。

考虑为此使用数组。您可以非常快速地读取随机值，但是如果要添加新值，则必须在数组中找到它所属的位置，将所有内容移开，然后插入新值。

使用二叉搜索树，您只需遍历树以查找值（如果该值已在树中）将在何处，然后将其添加到那里。

另外，考虑是否要查找排序后的数组是否包含特定值。您必须从数组的一端开始，然后将要查找的值与每个单独的值进行比较，直到您在数组中找到该值或将其传递到原点为止。使用二叉搜索树，您可以大大减少可能需要进行的比较次数。但是，只需要快速警告一下，绝对有可能构想二进制搜索树需要更多比较的情况，但这只是例外，而不是规则。

Answer 2

我过去用过的一件事是霍夫曼解码(或任何可变比特长度方案).

如果使用叶子上的字符维护二进制树,则每个传入位决定是移动到左侧还是右侧节点.

到达叶节点时,您将获得解码后的角色,然后可以从下一个节点开始.

例如,请考虑以下树:

    .
   / \
  .   C
 / \
A   B

这将是一个主要字母为文件的树C(通过使用较少的位用于公共字母,文件比固定位长方案的文件短).各个字母的代码是:

A: 00 (left, left).
B: 01 (left, right).
C: 1  (right).

该级,那么你使用的问题,就是您希望能够既插入和访问元素合理有效.除了不平衡树(例如上面的Huffman示例),您还可以使用平衡树,这使得插入成本更高(因为您可能必须在运行中重新平衡),但是因为您是更高效的查找遍历最小可能的节点数.