java - メソッドの二分探索木を削除

Question

私が取り組んできた 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);
        }
    }
}

挿入メソッドを使用して削除メソッドを支援できると言われましたが、最小/最大の要素を取得して、削除する要素をその値に置き換え、再帰的に削除する方法がわかりません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

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 2

これは非常に古い質問ですが、とにかく...受け入れられた回答の実装はc ++から取得されているため、Javaにはポインターがないため、変更する必要があるポインターのアイデアがまだ存在します。

したがって、ノードを null などに変更するたびに、そのノードのインスタンスは変更されますが、元のインスタンスは変更されません。

この実装は、アルゴリズムに関する coursera コースの 1 つから取られています。

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

ノード間のすべてのリンクは、再帰からの戻り値を使用して関連付けられます。

Answer 3

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