Я не понимаю, как двигать части дерева - PullRequest
Новая
       6

Я не понимаю, как двигать части дерева

1 голос
/ 07 апреля 2020

Моя цель - создать BST, который: когда я вставляю узел, я вставляю его в root, если элемент для вставки уже существует, перемещаем существующий элемент в root. Если вы удаляете узел, переместите отца этого узла в root. 

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

Я еще не имел дело с Удалить. Я застрял в функции вставки.

Моя идея заключалась в следующем: заменить старый root новым и зацепить старый root слева от нового, если он меньше, или вправо, если оно больше. Также, если это старый root меньше нового, найдите первый по величине элемент нового root в правой ветви старого root и переместите его, зацепив его как правую ветвь новый root. И наоборот, если оно больше.

Но я не способен. Может кто-нибудь мне помочь? Может быть, прежде чем закрыть «вопрос», мне также понадобится несколько советов по операции удаления.

...