删除方法二叉搜索树

Question

我正在尝试为我一直在研究的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);
        }
    }
}

我被告知可以使用insert方法来帮助我使用remove方法，但我只是不知道如何获取最小/最大的元素，然后用该值替换我正在删除的元素，然后递归地删除我获取替换值的节点，同时仍然保持O（logn）的复杂性。有人有什么想法或明显的漏洞我错过了，或任何其他有帮助的，因为我撞我的头在这个问题上？

编辑：我用答案的想法得出了这个结论，我相信这会奏效，但我得到了一个错误，我的方法（不仅仅是删除）必须返回字符串，下面是代码的样子，我认为这是返回语句？？

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

Answer 1

要在java中比较对象，请使用。方法而不是“==”运算符

  if(title==root.title)
          ^______see here

你需要像这样使用

 if(title.equals(root.title)) 

或者，如果您有兴趣忽略该案例，请遵循以下代码

 if(title.equalsIgnoreCase(root.title))

Answer 2

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

Answer 3

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

这是对不平衡树的删除。我有C语言的代码，所以我很快就翻译出来了。不过可能有一些小错误。您正在编码的树是否必须平衡？如果需要的话，我也有平衡移除。根据你问题的措辞，我不太确定。还要确保为findMax（）添加了一个私人助手函数