java – 删除方法二进制搜索树

发布时间：2020-12-15 04:15:12 所属栏目：Java 来源：网络整理

导读：我正在尝试为我一直在研究的BST结构实现一个remove方法.以下是包含find,insert和remove方法的代码： public class BST { BSTNode root = new BSTNode("root"); public void insert(BSTNode root,String title){ if(root.title!=null){ if(title==root.title)

我正在尝试为我一直在研究的BST结构实现一个remove方法.以下是包含find,insert和remove方法的代码：

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

解决方法

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()

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!