3
對於一個平衡搜索樹，對於所有情況都是O（log（N））。對於不平衡搜索樹，最壞的情況是O（N），例如，插入1,2,3,4 ...，並且最佳情況下的複雜度是平衡時的情況，例如插入6,4,8,3,5,7 。我們如何定義不平衡搜索樹的平均個案複雜度？簡單不平衡搜索樹的平均漸近深度是多少？
A
回答
4
二叉樹的平均高度是Theta（sqrt（n））。已在以下論文中顯示（或引用，不太確定）：http://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf。
但是也許你對隨機節點的平均深度更感興趣，這是Theta（log n），可以在這裏看到：http://www.toves.org/books/data/ch05-trees/index.html（第5.2.4節）。
相關問題
- 1. 平衡二叉搜索樹
- 2. 平衡二叉搜索樹子樹
- 3. 平衡搜索樹查詢，漸進的分析
- 4. 多鍵平衡樹
- 5. CLLocationManager中水平精度的平均精度是多少？
- 6. 平衡二元搜索樹問題
- 7. 完美平衡二叉搜索樹
- 8. 二進制搜索樹平衡
- 9. 函數來平衡搜索樹
- 10. 二叉搜索樹（前平衡）
- 11. 差異重量平衡樹和高度平衡樹
- 12. 平衡二叉搜索樹的分期複雜度
- 13. 將不平衡轉換爲均衡的bsp樹？
- 14. 給定數字n，那裏有多少個平衡二叉樹（不是二叉搜索樹）？
- 15. 平衡KD樹
- 16. AVL樹平衡
- 17. 平衡AVL樹
- 18. （）的不平衡度（）
- 19. 一個平衡的二叉搜索樹，這也是堆
- 20. 平衡如何平衡B-樹
- 21. 計算二叉搜索樹的最大不平衡
- 22. 將常規的二叉搜索樹變成平衡的二叉搜索樹
- 23. 均衡的二叉搜索樹實現
- 24. 二元搜索樹通過旋轉平衡（在AVL樹上）
- 25. 樹或平衡二叉搜索樹來存儲字典？
- 26. 不平衡二叉樹
- 27. 序言 - 平衡樹或不
- 28. Grafana中的$ interval平均值是多少？
- 29. 恆星的平均顏色是多少？
- 30. 平均速度，btree或散列表的速度是多少？
由於與隨機遊走的相似性，我會期待'O（n^.5）'，但我沒有發佈答案，因爲我無法證明這一點。 順便說一句，如果這是家庭作業，你能標記它嗎？ – pavpanchekha
這不是功課。這是出於好奇心，因爲C++，Java中的標準庫中的大多數搜索樹都實現爲不平衡。 – user236215
這太難以做作業了。 – 2010-02-25 05:26:38