我需要用 O(1) 的时间来调整二叉搜索树的高度,我能想到的唯一方法是检查增加全局计数器的添加和删除方法是否还有其他方法怎么办?
最佳答案
O(1) 时间表明你应该已经有要求的高度。
最好的方法是在添加/删除新节点时保持/更新正确的值。您正在以正确的方式进行操作,但是它增加了添加和删除的复杂性。
你可以通过多种方式做到这一点,比如将深度值与树中的节点一起保存等。
class Node{
int depth;
Object value;
}
Node lowestNode;
我可以考虑将最大深度节点引用存储在一个对象中并将其保留为 depth 。因此,无论何时添加新元素,都可以根据其父元素检查元素的深度,如果新元素具有更多深度,则替换最大深度节点。
如果要删除最大深度节点,则将其替换为父节点,否则沿树递归地更正所有元素的深度。
树的高度为 , lowestNode.depth
关于java - 常数时间内二叉搜索树的高度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15193306/