Java二叉搜索树——插入实现

Question

我在执行二叉搜索树插入时遇到了这个问题。现在我已经尝试了递归方法和迭代方法。到目前为止，我得到的方法是“充其量”，因为对于树大小 = 31609 和树高度 = 35，插入大约需要 100 秒，并且应该 WAAAAAAY 低一秒左右.有人可以给我提示我可能做错了什么吗？

这是我到目前为止所做的代码(没有重复的插入):

void insert(int val){
    if(this.elem < val){
        if(this.right != null){
            this.right.insert(val);
        }
        else{
            nodes++;
            this.right = new Node(val);
        }
    }
    else if(this.elem > val){
        if(this.left != null){
            this.left.insert(val);
        }
        else{
            nodes++;
            this.left = new Node(val);

        }
    }
    else {
        return;
    }
}

Answer 1

如果使用第270行定义的函数进行插入，时间长其实是可以解释的。

看看这段代码:

public void insert(int val) {

        if (root == null) {
            nodes++;
            root = new Node(val);
        } else if (!root.exists(val)) {
            root.insert(val);
        }

    }

这调用了一个函数exists()，定义如下:

boolean exists(int val) {
            return val == this.elem
                    || (val < this.elem ? (this.left != null && this.left.exists(val))
                            : (this.right != null && this.right.exists(val)));
        }

当你看到这段代码时，你可以很容易地发现，也许每次调用这个函数时，你的代码都会递归地遍历整棵树!所以如果你插入 100K 次，你的代码在最坏的情况下运行 O(n^2*logn) 时间，所以 100 秒实际上是一个很好的运行时间!

我认为您要做的是修改您的 exists() 函数。