java - 常数时间内二叉搜索树的高度

Question

我需要用 O(1) 的时间来微调二叉搜索树的高度，我能想到的唯一方法是检查 add 和 remove 方法增加全局计数器是否有其他方法？

score 3 · Accepted Answer

O(1) 时间表明您在请求时应该已经具有高度。

最好的方法是在添加/删除新节点时保持/更新正确的值。您正在以正确的方式进行操作，但是它增加了添加和删除的复杂性。

您可以通过多种方式做到这一点，例如将深度值与树中的节点一起保留等。

class Node{
int depth;
Object value;
}

Node lowestNode;

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

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

树的高度是 ,lowestNode.depth

score 2 · Accepted Answer

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

如果保证树是平衡的（例如 AVL），您可以通过树中元素的数量来计算高度（您必须保持元素的数量：P）

2 回答 2