tree - 非自平衡的二叉搜索树有什么用吗？

Question

我能找到的所有类型的二叉搜索树都是自平衡的。有没有什么不是，实际上是有用的？

Answer 1

每个不主动执行平衡的二叉搜索树都可能变得不平衡。

特别是，将（反向）排序序列插入 BST 将导致退化树（本质上是链表）：

3 2 1

    3
   /
  2
 /
1

和

1 2 3

1
 \
  2
   \
    3

Answer 2

我想到的第一个例子是Rope，它是一种二叉树，用于高效地存储和编辑长字符串，例如在文本编辑器中。

它本身并不平衡，但连接和拆分要求树是平衡的。但是即使在不平衡的树中也可以访问每个角色O(log N)，所以也许这符合您的问题