我需要罰款的時間爲O(1)的二叉搜索樹的高度我唯一能想到的方法是在添加和刪除方法中進行檢查增加一個全球計數器是否有其他方法?二進制搜索樹的高度在不變的時間
1
A
回答
2
存儲一個屬性的高度,並在添加/刪除時更新它應該是最合理的解決方案。
如果樹是保證平衡(如AVL),就可以計算出在樹中元素的個數高度(你必須保持元素的數量雖然:P)
3
O(1)時間表明你應該已經在要求的時候擁有高度。
無論何時添加/刪除新節點,最好的方法是保持/更新正確的值。你正在做的是正確的方式,但它增加了添加和刪除的複雜性。
你可以做到這一點的方法數,如保持深度值與樹的節點沿等
class Node{
int depth;
Object value;
}
Node lowestNode;
我能想到的存儲對象的最大深度節點參考,並保持該深度。因此,無論何時添加新元素,都可以根據元素的父元素檢查元素的深度,並在新元素具有更多深度時替換最大深度節點。
如果您要刪除最大深度節點,請將其替換爲父級,否則請沿着樹狀圖遞歸地更正所有元素的深度。
樹的高度是,lowestNode.depth
相關問題
- 1. 二進制搜索樹,高度
- 2. 二進制搜索樹的高度,而不構建它
- 3. 二進制搜索樹內的二進制搜索樹
- 4. 二進制搜索樹中的高度函數
- 5. 獲取二叉搜索樹的高度
- 6. 二進制搜索樹C++
- 7. 二進制搜索樹Instantiaition
- 8. 二進制搜索樹toString
- 9. 二進制搜索樹
- 10. Haskell - 二進制搜索樹
- 11. 二進制搜索樹C++
- 12. 二進制搜索樹C++
- 13. 二進制搜索樹 - 搜索範圍
- 14. Swift二進制搜索樹搜索
- 15. 二進制搜索的運行時間
- 16. 線性搜索或二進制搜索或二叉搜索樹
- 17. 如何將二進制搜索樹添加到二進制搜索樹?
- 18. 唯一的二進制搜索樹
- 19. 在二進制搜索樹中查找數據點的深度
- 20. 在非二進制樹中搜索
- 21. 雙刪除(?)在二進制搜索樹
- 22. 計算二進制搜索樹的高度的函數無法正常工作
- 23. Java二進制搜索樹在運行時不打印
- 24. 二進制搜索未排序數組的時間複雜度
- 25. 深度優先搜索二進制樹/圖中的Java
- 26. Java二進制搜索詞樹
- 27. 如何打印二進制搜索樹?
- 28. C二進制搜索樹插入
- 29. 二進制搜索樹陣列Imp。 C++
- 30. 二進制搜索樹打印
你需要多準確?如果它是平衡的,它應該是log n。並且log n可以通過值n中的有效位的數量來近似。 – 2013-03-04 02:12:08