Java, метод удаления двоичного дерева

Question

Я пытаюсь написать remove(node cRoot, Object o) функцию для отсортированного двоичного дерева.

Вот что у меня есть:

private boolean remove(Node cRoot, Object o) {
  if (cRoot == null) {
    return false;
  }
  else if (cRoot.item.equals(o)) { 
    //erase node fix tree
    return true;
  }
  else if (((Comparable)item).compareTo(cRoot.item)<=0){
    return remove(cRoot.lChild, o);
  }
  else { 
     return remove(cRoot.rChild,o);
  }
}

Не работает правильно. Чтобы удалить узел, вы должны восстановить дерево, чтобы исправить дыру. Как это сделать?

Answer 1

Обычно существует два способа удаления дерева:

Первый метод:

Удалите узел, затем замените его любым дочерним узлом. Затем выполните восстановление дерева, выполнив замену «родитель-потомок», пока дерево не будет снова отсортировано.

Второй метод:

Пройдите по дереву, чтобы найти следующее (самое высокое или самое низкое) значение, которое принадлежит корню *, если это листовой узел, поменяйте его местами с корнем, а затем обрежьте значение, которое хотите удалить. Если это внутренний узел, вам придется рекурсивно вызывать remove на этом узле. Повторяйте, пока листовой узел не будет удален.

* Я имею в виду, что если вы конвертируете свой BST в отсортированный список, то вы захотите выбрать либо значение слева, либо справа от корня в качестве нового корня. То есть самый левый потомок правого поддерева или самый правый потомок левого поддерева.

Answer 2

Основной псевдокод для удаления узла из отсортированного дерева довольно прост:

1. стереть значение узла
2. найти дочерний узел с максимальным значением
3. сделать его корневым узлом
4. если бы у него были дети - перейти к 2 рекурсивно

По сути, вы делаете то, что пузырите узлы вверх по дереву, каждый раз по максимуму дочерних узлов в каждом узле, так что в итоге вы остаетесь с отсортированным деревом, и только один узел отсутствует в конце полного путь, по которому вы пошли.

Также - см. википедию по теме , у них также есть некоторый пример кода на языке Си.

Answer 3

В простом case3 вы можете использовать следующий алгоритм:

if(removed node had left child)
{
   place left child instead of removed node;
   most_right = most right leaf in the left subtree;
   move right child of removed node as right child of most_right;
}
else
{
   place right child instead of removed node
}

В более сложных случаях вам может потребоваться перебалансировать дерево (см. Деревья AVL, http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html для примера C ++)

Answer 4

Я нашел этот код на Хабрахабр . Я только что добавил комментарии.

public void remove (T1 k){
    Node<T1,T2> x = root, y = null;
    // from while to if(x == null) - searching for key
    while(x != null){
        int cmp = k.compareTo(x.key);
        if(cmp == 0){
            break;  // quit cycle if key element is found
        } else {
            y = x;
            if(cmp < 0){
                x = x.left;
            } else {
                x = x.right;
            }
        }
    }
    if(x == null) return;   // if key is not found or tree is empty
    if(x.right == null){    // if element found has not right child
        if(y == null){      // if element found is root & has not right child
            root = x.left; 
        } else {            // if element found is not root & has not right child           
            if(x == y.left) y.left = x.left;    
            else y.right = x.left;              
        }
    } else {            // element found has right child, so search for most left of rights
        Node<T1,T2> mostLeft = x.right;
        y = null;
        while(mostLeft.left != null) {
            y = mostLeft;
            mostLeft = mostLeft.left;
        }
        if(y == null){  // if right child of element found has not left child
            x.right = mostLeft.right;
        } else {        // if right child of element found has left child
            y.left = mostLeft.right;
        }
        x.key = mostLeft.key;       
        x.value = mostLeft.value;   
    }
}

Answer 5

1. лист-удаляемый узел
2. 1 ребенок Продвигать поддерево
3. 2-дочерний регистр замените узел либо
4. в порядке преемника или предшественника
5. оставил большую часть правого поддерева или
6. правая большая часть левого поддерева