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

Question

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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 6

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

Учитывая корень дерева "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;

}