tree - 随机二叉搜索树

Question

我有一个 BST，我从 1...n 随机插入密钥（每个排列都以 1/n！概率完成）。我的问题是为什么即使排列是统一的，结果树也不统一？

Answer 1

很大程度上取决于树的实现。是自我平衡吗？考虑简单的树 1 2 3 和 3 2 1

Very simple tree:
add 1

1

add 2


1
 \
  2

add 3

 1
  \
   2
    \
     3

然后 3 2 1

加 3

3

add 2


  3
 /
2

add 1

     3
    /
   2
  / 
 1

现在做 2 3 1

2

2
 \
  3


  2
 / \
1   3

Answer 2

二叉搜索树不仅仅是一棵统一的搜索树......一棵树是按照新值保存在其中的顺序构建的。正如glowcoder已经展示的那样，这并不能保证一致性......

具有均匀分布的随机数并不能保证构建二叉树的最优值顺序

为了通过二叉树进行最小的搜索，必须定期重建树。这通常发生在非工作时间，算法可能会将整棵树读入一个链表，然后从该链表中构建一个具有最佳一致性的新树