java - 我不明白如何移动树的一部分

Question

我的目标是创建一个 BST：当我插入一个节点时，我将它插入根，如果要插入的元素已经存在，则将现有元素移动到根。如果删除一个节点，则将该节点的父节点移动到根节点。

class BSTNode {

BSTNode left = null;
BSTNode rigth = null;
int data = 0;

public BSTNode() {
    super();
}

public BSTNode(int data) {
    this.left = null;
    this.rigth = null;
    this.data = data;
}

@Override
public String toString() {
    return "BSTNode [left=" + left + ", rigth=" + rigth + ", data=" + data + "]";
}

}


class BinarySearchTree {

BSTNode root = null;

public BinarySearchTree() {

}

public void insert(int data) {
    BSTNode node = new BSTNode(data);
    if (root == null) {
        root = node;
        return;
    }else{

        BSTNode currentNode = root;
        BSTNode parentNode = null;



            if (currentNode.data == data)
                return;

            if (currentNode.data > data) {
                parentNode = node;

                BSTNode existing = searchNode(data);

                if (existing != null){
                    parentNode = existing;
                    parentNode.rigth = currentNode;
                }else{
                    parentNode.rigth = currentNode;
                }        
            } else {
                parentNode = node;

                BSTNode existing = searchNode(data);

                if (existing != null){

                    parentNode = existing;
                    parentNode.left = currentNode;
                }else{
                    parentNode.left = currentNode;
                }
            }
            root = parentNode;
        }
    }


public BSTNode searchNode(int data) {
    if (empty())
        return null;
    return searchNode(data, root);
}

public BSTNode searchNode(int data, BSTNode node) {
    if ((node.left != null && node.left.data == data) || (node.rigth != null && node.rigth.data == data)) {
        if (node.left.data == data){
            BSTNode existing = node.left;
            node.left = null;
            return existing;
        }
        if(node.rigth.data == data){
            BSTNode existing = node.rigth;
            node.rigth = null;
            return existing;
        }
        else if (node.data > data)
            return searchNode(data, node.left);
        else if (node.data < data)
            return searchNode(data, node.rigth);  
    }
    return null;
}

我还没有处理删除。我被困在插入功能上。

我的想法是：用新根替换旧根，如果它更小，则将旧根挂在新根的左侧，或者如果它更大，则挂在右侧。另外，如果是旧根小于新根，则在旧根的右分支上寻找新根的第一个最大元素，并将其作为新根的右分支钩住来移动。如果它更大，则相反。

但我没有能力。谁能帮我？也许在关闭“问题”之前，我还需要一些关于删除操作的建议。

标签： javabinary-search-tree