二進制搜索樹的高度在不變的時間

我需要罰款的時間爲O（1）的二叉搜索樹的高度我唯一能想到的方法是在添加和刪除方法中進行檢查增加一個全球計數器是否有其他方法？二進制搜索樹的高度在不變的時間

你需要多準確？如果它是平衡的，它應該是log n。並且log n可以通過值n中的有效位的數量來近似。 – 2013-03-04 02:12:08

存儲一個屬性的高度，並在添加/刪除時更新它應該是最合理的解決方案。

如果樹是保證平衡（如AVL），就可以計算出在樹中元素的個數高度（你必須保持元素的數量雖然：P）

2013-03-04 01:50:58

O（1）時間表明你應該已經在要求的時候擁有高度。

無論何時添加/刪除新節點，最好的方法是保持/更新正確的值。你正在做的是正確的方式，但它增加了添加和刪除的複雜性。

你可以做到這一點的方法數，如保持深度值與樹的節點沿等

class Node{ 
int depth; 
Object value; 
} 

Node lowestNode;

我能想到的存儲對象的最大深度節點參考，並保持該深度。因此，無論何時添加新元素，都可以根據元素的父元素檢查元素的深度，並在新元素具有更多深度時替換最大深度節點。

如果您要刪除最大深度節點，請將其替換爲父級，否則請沿着樹狀圖遞歸地更正所有元素的深度。

樹的高度是，lowestNode.depth

2013-03-04 01:51:22

回答