бинарное дерево поиска Java

Question

У меня есть вопрос о том, как я могу удалить ребенка из узла (корень)? Так как я не могу вызвать удаление, если я сделаю ребенка недействительным, будут ли дети этого ребенка двигаться вверх? Мол, я бы просто инициализировал его как ноль? Или я бы указал на ребенка ребенка?

Answer 1

В традиционном бинарном дереве поиска удаление узла может иметь различные последствия в зависимости от того, сколько дочерних узлов у узла:

• Узел без дочерних элементов может быть просто удален
• Узел с одним потомком может быть удален, а узел будет заменен его единственным потомком. Это применяется независимо от того, является ли ребенок левым или правым ребенком.
• У узла с двумя дочерними элементами есть немного более сложное правило: вы должны найти преемника порядка или порядка удаляемого узла, заменить текущий значение узла вместе со значением его предшественника или предшественника, затем удалите преемника или предшественника (согласно этим правилам).

Answer 2

Вы можете сделать что-то вроде этого (псевдокод):

С учетом корня дерева "root" и узла для удаления или некоторых данных "x" выполните следующее

 if x < root
      recurse to left child
 if x > root
      recurse to right child
 else //node found
      find the min item of the node right child //min item should be left most leaf node node
      replace the value of the node you want to delete with min nodes value
      now delete the min node
 return root;

Код:

delete(Node root, Object x){
    if(root == null){
        return null;
    }

    if(data < root.data){
        root = delete(root.left);
    }else if(root.data < data){
        root = delete(root.right);
    }else{
        if(root.left != null && root.right != null){
            Object tmp = findMin(root.right);
            root.data = tmp;
            root.right = delete(root.right, tmp);
        }else{
            return (root.left != null) ? root.left : root.right;    
        }
    }
return root;

}

Answer 3

Этот код должен помочь вам

public Node<T> getParentOf(Node<T> child){
    findParentOf(this.root, child);
    return temp;
}

private void findParentOf(Node<T> ROOT, Node<T> child){
    if(ROOT.hasLeft()){
        findParentOf(ROOT.left, child);
    }

    if(ROOT.left == child || root.right == child){
        temp = ROOT;
    }

    if(ROOT.hasRight()){
        findParentOf(ROOT.right, child);
    }
}


private void replaceNode(Node<T> original, Node<T> newNode){
    Node<T> tempParent = getParentOf(original);
    if(original == tempParent.left){
        tempParent.left = newNode;
    }else if(original == tempParent.right){
        tempParent.right = newNode;
    }
}

private void traverseChildrenAndAdd(Node<T> newParent, Node<T> oldParent){
    newParent.insert(oldParent.data);
    if(oldParent.hasLeft()){
        traverseChildrenAndAdd(newParent,oldParent.left);
    }



    if(oldParent.hasRight()){
        traverseChildrenAndAdd(newParent,oldParent.right);
    }
}
private void deleteNode(Node<T> ROOT, Node<T> d){
    if(d.data.compareTo(ROOT.data) < 0){
        deleteNode(ROOT.left, d);
    }else if(d.data.compareTo(ROOT.data) > 0){
        deleteNode(ROOT.right, d);
    }else if(d == this.root){
        if(this.root.hasLeft()){
            traverseChildrenAndAdd(root.left, root.right);
            root = root.left;
        }else if(root.hasRight()){
            root = root.right;
        }else{
            root = null;
        }
    }else{
        if(ROOT.hasLeft()&&ROOT.hasRight()){
            Node<T> successor = getMinNode(ROOT);
            replaceNode(successor, successor.right);
        }else if(ROOT.hasLeft() || ROOT.hasRight()){
            if(ROOT.hasLeft()){
                replaceNode(ROOT, ROOT.left);
            }else{
                replaceNode(ROOT, ROOT.right);
            }
        }else{
            replaceNode(ROOT, null);
        }
    }
}

public void remove(T data){
    deleteNode(this.root, new Node<T>(data));
}

Answer 4

Ответ Тима кажется лучшим.Но да, вы захотите сделать одну из трех вещей в зависимости от того, какого ребенка вы удаляете.Если вы сделаете ребенка недействительным, его дети не будут двигаться вверх, потому что вы потеряли ссылку на них.Вместо этого вы захотите определить, должны ли левые или правые дочерние элементы дочернего объекта, которого вы удаляете, установить указатель, указывающий на дочернего элемента, которого вы удаляете.После того, как вы установите предыдущий «указатель узлов (левый или правый) на дочерний элемент (левый или правый) узла, который вы удаляете, у вас больше не будет ссылки на этот узел, поэтому нет необходимости устанавливать его в нуль (вы можете»к нему больше нет доступа. Если вы не написали какой-то BST с двойной связью, в этом случае это не классический BST)

Answer 5

Стандартный класс дерева будет знать свои дочерние элементы, как правило, застрявшие в массиве или коллекции - в случае двоичного дерева у вас есть только два прямых дочерних элемента, поэтому будет работать массив фиксированного размера. По этой причине они обычно реализуют какой-то метод «removeMe», который вызывает дочерний элемент, чтобы удалить его из этого списка дочерних элементов.

Как упомянуто выше, это становится сложным, если у ребенка, которого вы удаляете, есть дети.

Answer 6

Это домашняя работа? В этом нет ничего плохого ... нам просто нравится помогать людям учиться, а не рассказывать им ответы.

Если вы просто установите дочерний узел на нуль, вы потеряете любую информацию о дочерних узлах.