固定时间内二分查找树的高度

Question

我需要确定二进制搜索树的高度，时间为O(1)我能想到的唯一方法是在add和remove方法中添加一个检查，使全局计数器递增，还有其他方法吗？

Answer 1

O(1)时间表明，当请求高度时，您应该已经拥有它。

最好的方法是在添加/删除新节点时保留/更新正确的值。您这样做是正确的，但是它增加了添加和删除的复杂性。

你可以通过多种方式来实现，比如在树中保留节点的深度值等。

class Node{
int depth;
Object value;
}

Node lowestNode;

我可以考虑将最大深度节点引用存储在一个对象中，并将其作为深度。因此，无论何时添加新元素，都可以基于其父元素检查元素的深度，如果新元素具有更多深度，则替换最大深度节点。

如果您要删除最大深度节点，则将其替换为父节点，否则将沿着树递归地更正所有元素的深度。

树的高度是，lowestNode.depth

Answer 2

存储高度的属性并在执行添加/删除操作时更新它应该是最合理的解决方案。

如果树被保证是平衡的(例如AVL)，你可以通过树中元素的数量来计算高度(你必须保留元素的数量:P )