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

Двоичные деревья поиска поддерживают три основных операции: вставка элементов, удаление элементов и поиск (проверка наличия ключа).

Поиск

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

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

def search_recursively(key, node):
    if node is None or node.key == key:
        return node
    if key < node.key:
        return search_recursively(key, node.left)
    # key > node.key
    return search_recursively(key, node.right)

Тот же алгоритм может быть реализован итеративно:

def search_iteratively(key, node):
    current_node = node
    while current_node is not None:
        if key == current_node.key:
            return current_node
        if key < current_node.key:
            current_node = current_node.left
        else:  # key > current_node.key:
            current_node = current_node.right
    return current_node

Эти два примера основаны на том, что отношение порядка является полным порядком.

Если отношение порядка является только полным предварительным порядком, разумное расширение функциональности заключается в следующем: также в случае поиска равенства выполняется поиск в направлении, указанном пользователем. Сортировка двоичного дерева, снабженная такой функцией сравнения, становится устойчивой.

Поскольку в худшем случае этот алгоритм должен осуществлять поиск от корня дерева до самого дальнего от корня листа, операция поиска занимает время, пропорциональное высоте дерева. В среднем, двоичные деревья поиска с n узлами имеют высоту O(log n). Однако в худшем случае деревья двоичного поиска могут иметь высоту O(n), когда несбалансированное дерево напоминает связанный список (вырожденное дерево).

---

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

• Структуры данных: двоичное дерево поиска
• Структуры данных: B-дерево (B-tree)
• Структуры данных: хэш-таблица