В этой статье блога мы углубимся в концепции предшественника и преемника в двоичном дереве поиска (BST). Мы будем использовать разговорный язык и приведем примеры кода, чтобы объяснить различные методы поиска предшественника и преемника в BST. Итак, начнём!

Понимание бинарных деревьев поиска:
Двоичное дерево поиска — это структура данных, которая организует свои элементы отсортированным образом, при этом каждый узел имеет значение, большее, чем все значения в его левом поддереве, и меньше, чем все значения в его левом поддереве. его правое поддерево. Это свойство делает его эффективным для поиска, вставки и удаления элементов.

Что такое предшественник и преемник?
В контексте BST предшественником узла является узел с наибольшим значением, меньшим, чем данный узел. И наоборот, преемником является узел с наименьшим значением, превышающим данный узел.

Метод 1: неупорядоченный обход
Одним из распространенных подходов к поиску предшественника и преемника является выполнение неупорядоченного обхода BST. При обходе по порядку мы посещаем узлы в порядке возрастания. Отслеживая ранее посещенный узел во время обхода, мы можем идентифицировать предшественника и преемника.

Вот реализация Python для обхода по порядку для поиска предшественника и преемника:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
def inorder(root, target):
    if root is None:
        return None

    stack = []
    current = root
    predecessor = successor = None

    while True:
        if current:
            stack.append(current)
            current = current.left
        elif stack:
            current = stack.pop()

            if current.value < target:
                predecessor = current
            elif current.value > target and successor is None:
                successor = current
                break

            current = current.right
        else:
            break

    return predecessor, successor

Метод 2: рекурсивный подход
Другой способ найти предшественника и преемника — использовать рекурсивный метод. Мы начинаем обход BST от корня и сравниваем целевое значение с каждым узлом. На основе сравнения мы соответствующим образом обновляем предшественника и преемника.

Вот реализация рекурсивного подхода на Python:

def find_predecessor_successor(root, target):
    if root is None:
        return None, None

    if root.value == target:
        if root.left:
            predecessor = find_max_node(root.left)
        if root.right:
            successor = find_min_node(root.right)
        return predecessor, successor

    if root.value > target:
        return find_predecessor_successor(root.left, target)

    predecessor, successor = find_predecessor_successor(root.right, target)
    if predecessor is None:
        predecessor = root
    if successor is None:
        successor = find_min_node(root.right)

    return predecessor, successor
def find_min_node(root):
    while root.left:
        root = root.left
    return root
def find_max_node(root):
    while root.right:
        root = root.right
    return root

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

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