英文:
Is this the efficient BST Insertion?
问题
我根据逻辑自己实现了二叉搜索树插入方法。
所以，有人可以验证一下代码在插入和搜索时是否正常工作（可以使用自己的搜索方法，如中序遍历、前序遍历、后序遍历）？
还请计算出代码的时间复杂度。
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
英文:
I implemented the Binary Search Tree Insertion method on my own just based on logic.
So, can anyone verify that the code is working fine while inserting and searching( use your own searching methods like inorder, preorder, postorder)?
And also find the time complexity of the code.
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++;
}
}
}
}
}
Edit :- I found a problem when i insert these numbers:-
bst.insert(10);
bst.insert(11);
bst.insert(90);
bst.insert(13);
bst.insert(12);
bst.insert(70);
bst.insert(80);
it prints like this(inorder):-
10 11 80 70 12 13 90
答案1
得分: 0
在你的代码中似乎存在一些问题：
if (data > n.data) {
while (n.right != null) {
n = n.right;
.
.
}
}
这意味着对于像下面这样的树：
10
/ \
8 15
/ \
12 23
\
26
/
20
如果尝试插入例如 21，给定的算法将会尝试将其插入到节点 26 的左子节点。然而，该节点已经被占据，因此你的算法存在缺陷。
我建议你从每个节点递归地调用插入，就像这样：
// 在树的类中
public void insert(int data) {
if (root == null) {
root = new Node(data);
}
else {
root.insert(data);
}
size++;
}
// 在节点的类中
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);
}
}
由于每个节点在插入之前负责检查其子节点是否为空，这个问题将不会重复出现。
关于复杂性：
你可以得到一棵像下面这样的树：
1
\
2
\
3
\
...
\
n
在这种情况下，插入一个大于 n 的值将导致经过 n 个节点，因此时间复杂度为 O(n)。
英文:
There seem to be a few issues with your code:
if (data > n.data) {
while (n.right != null) {
n = n.right;
.
.
}
}
means that given a tree like:
10
/ \
8 15
/ \
12 23
\
26
/
20
And asking to insert for example 21, the given algorithem would attempt to insert it in the left child of 26. However this node is already taken, hence your algorithem is flawed.
I would suggest that you call insertion from each node recursively like:
// 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);
}
}
Since each node is responsible for checking if its children are empty before insertion this problem wont repeat.
In terms of complexity:
you can get a tree like
1
\
2
\
3
\
...
\
n
Where inserting a value bigger than n would result in passing over n nodes, therefore time complexity is O(n).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论