Java 二叉搜索树 - 插入实现

Question

我遇到了二叉搜索树插入的问题。我已经尝试过递归和迭代方法，但是目前的实现方式最好只能说"勉强能用"。对于一个大小为31609且高度为35的树，插入需要约100秒，而应该要快很多，只需要约1秒钟。请问有人可以给我一些提示，我可能做错了什么吗？

以下是我目前为止所做的代码（不包含重复项的插入）：

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;
    }
}

- drBet

---

我怀疑问题并不在于插入本身。你能提供有关构造函数的信息吗？ - Willem Van Onsem

构造函数非常基本：私有节点（int elem）{ this.elem=elem; }。 - drBet

单次插入调用需要100秒，还是构建整个树需要100秒？ - Dathan

@drBet：问题可能出在别处，因为仅使用 此 ideone 处理100k插入只需大约40毫秒（是的，我知道这只是个测试，但100秒和40毫秒之间有很大的差异）。我唯一能想到的问题是数据已排序，因此您创建了一个链表。这棵树没有自我平衡，因此如果数据有序，这将导致问题。 - Willem Van Onsem

@CommuSoft 哦，非常感谢你的帮助！！！我已经因为缺觉而眼睛发抖了！http://pastebin.com/zKJws4Yk - drBet

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()函数。

- Ashkan Kazemi