Java 移除方法二叉搜索树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19870680/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Remove method binary search tree
提问by dawich77
I am trying to implement a remove method for the BST structure that I have been working on. Here is the code with find, insert, and remove methods:
我正在尝试为我一直在研究的 BST 结构实现一个删除方法。这是带有查找、插入和删除方法的代码：
public class BST {
BSTNode root = new BSTNode("root");
public void insert(BSTNode root, String title){
if(root.title!=null){
if(title==root.title){
//return already in the catalog
}
else if(title.compareTo(root.title)<0){
if(root.leftChild==null){
root.leftChild = new BSTNode(title);
}
else{
insert(root.leftChild,title);
}
}
else if(title.compareTo(root.title)>0){
if(root.rightChild==null){
root.rightChild = new BSTNode(title);
}
else{
insert(root.rightChild,title);
}
}
}
}
public void find(BSTNode root, String title){
if(root!= null){
if(title==root.title){
//return(true);
}
else if(title.compareTo(root.title)<0){
find(root.leftChild, title);
}
else{
find(root.rightChild, title);
}
}
else{
//return false;
}
}
public void remove(BSTNode root, String title){
if(root==null){
return false;
}
if(title==root.title){
if(root.leftChild==null){
root = root.rightChild;
}
else if(root.rightChild==null){
root = root.leftChild;
}
else{
//code if 2 chlidren remove
}
}
else if(title.compareTo(root.title)<0){
remove(root.leftChild, title);
}
else{
remove(root.rightChild, title);
}
}
}
I was told that I could use the insert method to help me with the remove method, but I am just not seeing how I can grab the smallest/largest element, and then replace the one I am deleting with that value, then recursively delete the node that I took the replacement value, while still maintaining O(logn) complexity. Anyone have any ideas or blatant holes I missed, or anything else helpful as I bang my head about this issue?
有人告诉我，我可以使用 insert 方法来帮助我使用 remove 方法，但我只是没有看到如何获取最小/最大元素，然后用该值替换我要删除的元素，然后递归删除我采用替换值的节点，同时仍然保持 O(logn) 复杂度。任何人都有任何我遗漏的想法或明显的漏洞，或者在我对这个问题感到震惊时还有其他任何有用的东西？
EDIT: I used the answers ideas to come up with this, which I believe will work but I'm getting an error that my methods (not just the remove) must return Strings, here is what the code looks like, I thought that's the return statements??
编辑：我使用了答案的想法来提出这个，我相信这会起作用，但我收到一个错误，我的方法（不仅仅是删除）必须返回字符串，这是代码的样子，我认为这是返回语句？？
public String remove(BSTNode root, String title){
if(root==null){
return("empty root");
}
if(title==root.title){
if(root.leftChild==null){
if(root.rightChild==null){
root.title = null;
return(title+ "was removed");
}
else{
root = root.rightChild;
return(title+ "was removed");
}
}
else if(root.rightChild==null){
root = root.leftChild;
return(title+ "was removed");
}
else{
String minTitle = minTitle(root);
root.title = minTitle;
remove(root.leftChild,minTitle);
return(title+ "was removed");
}
}
else if(title.compareTo(root.title)<0){
remove(root.leftChild, title);
}
else{
remove(root.rightChild, title);
}
}
采纳答案by Josh Engelsma
public void remove (String key, BSTNode pos)
{
if (pos == null) return;
if (key.compareTo(pos.key)<0)
remove (key, pos.leftChild);
else if (key.compareTo(pos.key)>0)
remove (key, pos.rightChild);
else {
if (pos.leftChild != null && pos.rightChild != null)
{
/* pos has two children */
BSTNode maxFromLeft = findMax (pos.leftChild); //need to make a findMax helper
//"Replacing " pos.key " with " maxFromLeft.key
pos.key = maxFromLeft.key;
remove (maxFromLeft.key, pos.leftChild);
}
else if(pos.leftChild != null) {
/* node pointed by pos has at most one child */
BSTNode trash = pos;
//"Promoting " pos.leftChild.key " to replace " pos.key
pos = pos.leftChild;
trash = null;
}
else if(pos.rightChild != null) {
/* node pointed by pos has at most one child */
BSTNode trash = pos;
/* "Promoting " pos.rightChild.key" to replace " pos.key */
pos = pos.rightChild;
trash = null;
}
else {
pos = null;
}
}
}
This is the remove for an unbalanced tree. I had the code in C++ so I have quickly translated. There may be some minor mistakes though. Does the tree you are coding have to be balanced? I also have the balanced remove if need be. I wasn't quite sure based on the wording of your question. Also make sure you add a private helper function for findMax()
这是对不平衡树的删除。我有 C++ 代码，所以我很快就翻译了。不过可能有一些小错误。您正在编码的树是否必须平衡？如果需要，我也有平衡移除。根据您问题的措辞，我不太确定。还要确保为 findMax() 添加私有帮助函数
回答by Prabhakaran Ramaswamy
To compare objects in java use .equals() method instead of "==" operator
要比较 Java 中的对象，请使用 .equals() 方法而不是“==”运算符
if(title==root.title)
^______see here
you need to use like this
你需要像这样使用
if(title.equals(root.title))
or if you are interesed to ignore the case follow below code
或者如果您有兴趣忽略该案例，请遵循以下代码
if(title.equalsIgnoreCase(root.title))
回答by Shawn
private void deleteNode(Node temp, int n) {
if (temp == null)
return;
if (temp.number == n) {
if (temp.left == null || temp.right == null) {
Node current = temp.left == null ? temp.right : temp.left;
if (getParent(temp.number, root).left == temp)
getParent(temp.number, root).left = current;
else
getParent(temp.number, root).right = current;
} else {
Node successor = findMax(temp.left);
int data = successor.number;
deleteNode(temp.left, data);
temp.number = data;
}
} else if (temp.number > n) {
deleteNode(temp.left, n);
} else {
deleteNode(temp.right, n);
}
}
回答by psykid
I know this is a very old question but anyways... The accepted answer's implementation is taken from c++, so the idea of pointers still exists which should be changed as there are no pointers in Java.
我知道这是一个非常古老的问题，但无论如何......接受的答案的实现取自c++，所以指针的想法仍然存在，应该改变，因为Java中没有指针。
So every time when you change the node to null or something else, that instance of the node is changed but not the original one
因此，每次当您将节点更改为 null 或其他内容时，该节点的实例都会更改，但不会更改原始实例
This implementation is taken from one of the coursera course on algorithms.
此实现取自有关算法的课程之一。
public TreeNode deleteBSTNode(int value,TreeNode node)
{
if(node==null)
{
System.out.println("the value " + value + " is not found");
return null;
}
//delete
if(node.data>value) node.left = deleteBSTNode(value,node.left);
else if(node.data<value) node.right = deleteBSTNode(value,node.right);
else{
if(node.isLeaf())
return null;
if(node.right==null)
return node.left;
if(node.left==null)
return node.right;
TreeNode successor = findMax(node.left);
int data = successor.data;
deleteBSTNode(data, node.left);
node.data = data;
}
return node;
}
All the links between the nodes are pertained using the return value from the recursion.
节点之间的所有链接都使用递归的返回值进行关联。
回答by sanjay
void deleteTreeNode(int data){
root = deleteTreeNode(root ,data);
}
private TreeNode deleteTreeNode(TreeNode root, int data) {
TreeNode cur = root;
if(cur == null){
return cur;
}
if(cur.data > data){
cur.left = deleteTreeNode(cur.left, data);
}else if(cur.data < data){
cur.right = deleteTreeNode(cur.right, data);
}else{
if(cur.left == null && cur.right == null){
cur = null;
}else if(cur.right == null){
cur = cur.left;
}else if(cur.left == null){
cur = cur.right;
}else{
TreeNode temp = findMinFromRight(cur.right);
cur.data = temp.data;
cur.right = deleteTreeNode(cur.right, temp.data);
}
}
return cur;
}
private TreeNode findMinFromRight(TreeNode node) {
while(node.left != null){
node = node.left;
}
return node;
}
