Операции с двоичным деревом поиска: удаление

При удалении узла из бинарного дерева поиска обязательно поддерживать последовательность узлов в порядке. Есть много возможностей сделать это. Однако следующий метод, который был предложен Т. Хиббардом в 1962 г., гарантирует, что высота поддеревьев субъекта изменяется не более чем на единицу. Есть три возможных случая для рассмотрения:

• Удаление узла без дочерних элементов: просто удалите узел из дерева.
• Удаление узла с одним дочерним узлом: удалите узел и замените его дочерним.
• Удаление узла с двумя дочерними элементами: вызов узла, подлежащего удалению D. Не удаляйте D. Вместо этого выберите либо его предшествующий узел по порядку, либо его последующий узел по порядку в качестве заменяющего узла E. Скопируйте пользовательские значения E в D. Если E не имеет дочернего элемента, просто удалите E из своего предыдущего родителя G. Если E имеет дочерний элемент, скажем F, это правильный дочерний элемент. Замените E на F у родителя E.

Во всех случаях, когда D оказывается корневым, снова сделайте узел замены корневым.

Узлы с двумя детьми сложнее удалить. Преемник по порядку узла - это самый левый дочерний узел его правого поддерева, а предшественник по порядку узла - самый правый дочерний элемент поддерева. В любом случае, этот узел будет иметь только одного или ни одного дочернего элемента вообще. Удалите его в соответствии с одним из двух простых случаев выше.

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

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

# -*- coding: utf-8 -*-

def find_min(self):
    """Получает минимальный узел в дереве."""
    current_node = self
    while current_node.left_child:
        current_node = current_node.left_child
    return current_node

def replace_node_in_parent(self, new_value=None) -> None:
    if self.parent:
        if self == self.parent.left_child:
            self.parent.left_child = new_value
        else:
            self.parent.right_child = new_value
    if new_value:
        new_value.parent = self.parent

def binary_tree_delete(self, key) -> None:
    if key < self.key:
        self.left_child.binary_tree_delete(key)
        return
    if key > self.key:
        self.right_child.binary_tree_delete(key)
        return
    # Удаляем ключ
    if self.left_child and self.right_child:  
        # Если присуствуют оба дочерних узла
        successor = self.right_child.find_min()
        self.key = successor.key
        successor.binary_tree_delete(successor.key)
    elif self.left_child:  
        # Если узел имеет только левый дочерний
        self.replace_node_in_parent(self.left_child)
    elif self.right_child:  
        # Если узел имеет только правый дочерний
        self.replace_node_in_parent(self.right_child)
    else:
        # Этот узел не имеет дочерних
        self.replace_node_in_parent(None)  

---

Читайте также:

• Структуры данных: двоичное дерево поиска
• Операции с двоичным деревом поиска: поиск
• Операции с двоичным деревом поиска: вставка