这是有效的 BST 插入吗？

Question

我只是根据逻辑自己实现了二叉搜索树插入方法。那么，任何人都可以验证代码在插入和搜索时是否正常工作（使用您自己的搜索方法，如中序、前序、后序）？

同时求代码的时间复杂度。

public void insert(int data) {
    Node node = new Node(data);
    if (root == null) {
        root = node;
        size++;
    } else {
        Node n = root;
        if (data > n.data) {
            while (n.right != null) {
                n = n.right;
            }
            if (data < n.data) {
                while (n.left != null) {
                    n = n.left;
                }
                if (data != n.data) {
                    n.left = node;
                    size++;
                }
            } else {
                if (data != n.data) {
                    n.right = node;
                    size++;
                }
            }
        } else if (data < n.data) {
            while (n.left != null) {
                n = n.left;
            }
            if (data > n.data) {
                while (n.right != null) {
                    n = n.right;
                }
                if (data != n.data) {
                    n.right = node;
                    size++;
                }
            } else {
                if (data != n.data) {
                    n.left = node;
                    size++;
                }
            }
        }

    }
}

编辑：- 我在插入这些数字时发现了一个问题：-

    bst.insert(10);
    bst.insert(11);
    bst.insert(90);
    bst.insert(13);
    bst.insert(12);
    bst.insert(70);
    bst.insert(80);

它打印成这样（顺序）：- 10 11 80 70 12 13 90

Answer 1

您的代码似乎存在一些问题：

if (data > n.data) {
    while (n.right != null) {
                n = n.right;
                .
                .
                }
           }

意味着给定一棵树：

并要求插入例如 21，给定的算法将尝试将其插入 26 的左子节点。但是这个节点已经被占用，因此您的算法存在缺陷。我建议您递归地从每个节点调用插入，例如：

// in class tree
public void insert(int data) {
    if (root == null) {
        root = new Node(data);
    } 
    else {
        root.insert(data);
    }
    size++;
}
//in class Node
public void insert(int data) {
    if(data>=this.data){
         if(right==null) right=new Node(data)
         else right.insert(data);
    }
    else{
         if(left==null) left=new Node(data)
         else left.insert(data);
    }
}

由于每个节点都负责在插入之前检查其子节点是否为空，所以此问题不会重复。

在复杂性方面：你可以得到一棵像

这样的树

其中插入一个大于n的值会导致传递n个节点，因此时间复杂度为O(n)。

这是有效的 BST 插入吗？

Is this the efficient BST Insertion?

java

binary-search-tree

data-structures