恒定时间内二叉搜索树的高度 [英] Height of binary search tree in constant time

问题描述

我需要使用O（1）的时间来精确二叉搜索树的高度我能想到的唯一方法就是检查添加和删除方法增加全局计数器是否还有其他方式？

I need to fine the height of a binary search tree with a time of O(1) the only way i could think to do this is to put a check in the add and remove methods incrementing a global counter is there any other way?

推荐答案

O（1）时间表明你应该在请求时已经有了高度。

O(1) time suggests that you should already have the height when it is requested.

最好的方法是在添加/删除新节点时保持/更新正确的值。你正在以正确的方式做到这一点，但它增加了添加和删除的复杂性。

The best way is it to keep/update the correct value whenever a new node is added/deleted . You are doing it in a right way , however it increases the complexity on addition and deletion.

你可以做多种方式，比如保持深度值和树等节点。

You can do it number of ways , like keep the depth value along with the node in tree etc.

class Node{
int depth;
Object value;
}

Node lowestNode;

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

I can think of storing the max depth node reference in an object and keep that as depth . So whenever you add a new element , you can check the depth of element based on its parent and replace the max depth node if the new element has more depth .

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

If you are deleting the max depth node then replace it with the parent otherwise correct the depth of all elments recursively along the tree.

树的高度是， lowestNode.depth

这篇关于恒定时间内二叉搜索树的高度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！