随机二进制搜索树

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已经表明，这并不保证一致性...

具有随机数的均匀分布不保证值的次序，即通过为最佳建立二叉树

有一个最小的努力搜索二叉树，树必须定期重建。这通常发生在非营业时间，其中算法可以将整棵树读入链表中，然后从该列表中构建具有最佳一致性的新树