2.8 — Дерево двоичного поиска

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

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

Первое свойство: у каждого узла есть «левое поддерево», где все числа меньше, чем значение самого узла. Например, узел с числом 9 больше, чем любые числа в его левом поддереве.

Узел 15 всегда больше всех значений в его левом поддереве. Каждый узел также меньше всех значений в его правом поддереве. Например, узел 15 меньше всех чисел в его правом поддереве. Из этих двух свойств следует, что самый маленький узел в дереве находится в конце левого поддерева корневого узла. В нашем случае это 3. Наибольший узел дерева расположен в конце правого поддерева, если двигаться от верхнего узла. В этом примере максимальное значение равно 28.

Дерево двоичного поиска наглядно демонстрирует принцип бинарного поиска. Благодаря двум ключевым свойствам, при поиске нужного узла или выборе места для вставки нового элемента достаточно сравнить его значение с текущим узлом. Это помогает определить, куда двигаться — направо или налево.

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

Существуют структуры данных, которые расширяют возможности двоичного дерева поиска. Например, они помогают поддерживать баланс его ветвей. Это называется равновесным b-деревом поиска. Использование такой структуры сохраняет эффективность алгоритма. В данном дереве поиска у узла могло быть максимум два дочерних элемента. Однако количество дочерних узлов можно увеличить до m, где m — константа.

OrderedDict

OrderedDict — это класс из модуля collections, который реализует словарь, сохраняющий порядок добавления элементов.

До Python 3.7 порядок ключей в обычных dict не был гарантирован. Поэтому для задач, где важна последовательность элементов, использовали OrderedDict.

Начиная с Python 3.7 стандартные dict тоже запоминают порядок, но OrderedDict всё ещё полезен, так как имеет дополнительные методы.

from collections import OrderedDict

def printMaxActivities(actions: dict) -> None:

    acn = sorted(actions, key=actions.get(1))
    ord_actions = OrderedDict()
    for k in acn:
        ord_actions[k] = actions[k]

    i = acn[0]
    print(i, end=' ')
    for j in ord_actions:
        if ord_actions[j][0] >= ord_actions[i][1]:
            print(j, end=' ')
            i = j

if __name__ == '__main__':
    actions: dict = {
        'action2': [3, 4],
        'action3': [0, 6],
        'action5': [8, 9],
        'action6': [5, 9],
        'action1': [1, 2],
        'action4': [5, 7],
    }
    printMaxActivities(actions)

Когда использовать OrderedDict?

Если важен точный порядок добавления элементов.
Если нужно перемещать ключи (например, реализация LRU-кэша).
Для задач, где порядок влияет на результат сравнения словарей.

Дерево двоичного поиска

Материал урока

OrderedDict

Когда использовать OrderedDict?