Удаление узлов из двоичного дерева поиска (BST) — обычная операция в древовидных структурах данных. При удалении узла из BST важно сохранить свойства дерева и гарантировать, что полученная структура останется допустимой BST. В этой статье мы рассмотрим несколько методов удаления узлов из BST, а также примеры кода для каждого подхода.

Метод 1: рекурсивное удаление

Один из самых простых способов удалить узел из BST — использовать рекурсивный алгоритм. Идея состоит в том, чтобы найти узел, который нужно удалить, и заменить его его преемником или предшественником, гарантируя, что полученное дерево останется действительным BST.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
def delete_node(root, key):
    if root is None:
        return root
    if key < root.key:
        root.left = delete_node(root.left, key)
    elif key > root.key:
        root.right = delete_node(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        successor = get_successor(root.right)
        root.key = successor.key
        root.right = delete_node(root.right, successor.key)

    return root
def get_successor(node):
    current = node
    while current.left:
        current = current.left
    return current

Метод 2: итеративное удаление

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

def delete_node_iterative(root, key):
    parent = None
    current = root
    while current and current.key != key:
        parent = current
        if key < current.key:
            current = current.left
        else:
            current = current.right
    if current is None:
        return root
    if current.left is None:
        child = current.right
    elif current.right is None:
        child = current.left
    else:
        successor = get_successor(current.right)
        current.key = successor.key
        current.right = delete_node_iterative(current.right, successor.key)
        return root
    if parent is None:
        return child
    if parent.left == current:
        parent.left = child
    else:
        parent.right = child
    return root

Метод 3. Удаление с продвижением узла

Другой подход к удалению узлов в BST предполагает продвижение либо самого левого дочернего элемента правого поддерева, либо самого правого дочернего элемента левого поддерева. Этот метод гарантирует, что полученное дерево сохранит свойство BST.

def delete_node_promotion(root, key):
    parent = None
    current = root
    while current and current.key != key:
        parent = current
        if key < current.key:
            current = current.left
        else:
            current = current.right
    if current is None:
        return root
    if current.left is None and current.right is None:
        child = None
    elif current.right is None:
        child = current.left
    elif current.left is None:
        child = current.right
    else:
        successor = current.right
        if successor.left is None:
            current.key = successor.key
            current.right = successor.right
        else:
            while successor.left:
                parent = successor
                successor = successor.left
            current.key = successor.key
            parent.left = successor.right
        return root
    if parent is None:
        return child
    if parent.left == current:
        parent.left = child
    else:
        parent.right = child
    return root

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

Реализуя эти методы, вы можете уверенно выполнять операции удаления узлов в BST, сохраняя целостность и функциональность ваших древовидных структур данных.