在 O(log n) 中获取二叉树的大小

Question

完全披露：这是家庭作业。

我被要求 return 在二叉树中排名，经过一些编码后我让它工作了。但是由于我的代码没有被接受，我注意到代码应该运行 in O(log n)

导致速度变慢的罪魁祸首是我的尺寸方法：

public int size(Node node){
    if (node != null) return (size(node.left) + 1 + size(node.right));
    return 0;
}

我调用它是为了获得比我需要查找的元素小的所有元素的等级。

现在，我用谷歌搜索了所有内容，但显然不可能在 log n 时间内获得 BT 的大小？

那我需要怎么做？

Answer 1

对于仅存储 children 的简单二叉树，不可能在 O(log(n)) 时间内获得大小，因为有 n 个节点，您必须计算每个节点他们。但是，为什么要限制自己只有 children？像许多数据结构一样，您可以用节点存储大小：

class Node {
    public Node left;
    public Node right;
    public int value;
    private int size; // initialize this to 1
}

然后，当插入节点时，增加你遇到的每个节点的大小：

public void insert(int value) {
    // increment the size
    this.size++;
    if (value < this.value) {
        // obviously check for null as well and insert as appropriate
        this.left.insert(value);
    } else {
        this.right.insert(value);
    }
}

现在，您可以在 O(1) 时间内获得大小，因为每个节点都有它。

在 O(log n) 中获取二叉树的大小

Get size of a binary tree in O(log n)

java

big-o

binary-tree

time-complexity

data-structures