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

Дерево $—$ связный ациклический граф. Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.

Двоичное дерево (бинарное дерево) $-$ это структура данных, в которой каждый узел может иметь не более двух потомков. Их обычно называют левым и правым.

Корень $-$ это самый верхний узел, с которого всё начинается.

Листья $-$ узлы, у которых нет потомков. Всё, что между ними, называется внутренними узлами. Узел может иметь одного потомка, или не иметь ни одного. Главное $-$ не больше двух. Двоичное дерево может быть пустым. Во многих алгоритмах пустое дерево служит базовым случаем рекурсии.

Корневое двоичное дерево $-$ это двоичное дерево, у которого явно выделен корень. Корневое двоичное дерево определяется рекурсивно либо как пустое, либо как состоящее из узла, называющегося корнем, из которого выходят до двух корневых двоичных деревьев: они называются левым и правым поддеревом.

Двоичное дерево поиска (BST, Binary Search Tree) $-$ это корневое двоичное дерево с дополнительным правилом: для любого узла все ключи (значения) в левом поддереве меньше значения этого узла, а все ключи в правом поддереве $-$ больше. Причина эффективности таких деревьев в том, что благодаря упорядоченности поиск превращается в последовательность сравнений: зашли в узел $-$ сравнили искомый ключ с текущим $-$ если меньше, идём налево, если больше $-$ направо. На каждом шаге мы отбрасываем примерно половину дерева.

Разница между двоичным деревом и коревым двоичным деревом видна на примере:

$$ A - B - C $$

Если корнем считать B, то B имеет двух потомков - A и C. Если же корнем принять, например, A, то A имеет одного потомка B, который, в свою очередь, одного потомка C.

Здесь каждый узел имеет либо 0 потомков (в случае листьев), либо два потомка и для каждого узла все элементы левого поддерева меньше значения данного узла, а все элементы правого поддерева $-$ больше значения данного узла.

Здесь четверка находится в левом поддереве относительно двойки и единицы, хотя, очевидно, больше каждого; шестерка $-$ в левом поддереве для единицы, а семерка $-$ для тройки, что тоже нарушает основное правило двоичных деревьев поиска.

Кроме поля ключа, каждый узел двоичного дерева имеет поля left, right И parent, которые содержат указатели на левый и правый дочерние узлы и на родительский узел соответственно (единственным узлом, указатель parent которого равен NULL, является корневой узел всего дерева).

Листинг 3.6. Объявление типа структуры дерева:

struct tree {
    item_type item;    // Элемент данных 
    tree *parent;      // Указатель на родительский узел 
    tree *left;        // Указатель на левый дочерний узел 
    tree *right;       // Указатель на правый дочерний узел 
};

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

Поиск начинается с корня. Сравниваем искомое значение со значением в текущем узле. Если равны — нашли. Если меньше — идём в левое поддерево. Если больше — в правое. Повторяем, пока не найдём или не упрёмся в пустой узел.

Листинг 3.7. Алгоритм рекурсивного поиска произвольного элемента в дереве:

tree *search_tree(tree *l, item_type x) {              //Функция принимает указатель на корень дерева (поддерева) 
    if (l == nullptr) return nullptr;                  //И возвращает указатель на требуемый узел
    if (l->item == x) return l;
    if (x < l->item) return search_tree(l->left, x);
    else return search_tree(l->right, x);
}

Листинг 3.8. Поиск наименьшего элемента в двоичном дереве:

tree *find_minimum(tree *t) {
    tree *min; // Указатель на наименьший элемент 

    if (t == nullptr) return (nullptr);

    min = t;
    while (min->left != nullptr) {
    min = min->left;

    return(min);

    }
}

Минимальный элемент находится в самом левом листе дерева - поэтому, чтобы его отыскать, достаточно двигаться влево, пока не дойдем до нулевого указателя.

В соответствии с определением двоичного дерева все ключи со значением меньшим, чем значение ключа корневого узла, должны находиться в левом поддереве корневого узла, а все ключи с большим значением - в правом. Таким образом, результатом рекурсивного посещения узлов является симметричный обход (in-order traversal) двоичного дерева. Реализация соответствующего алгоритма:

Листинг 3.9. Рекурсивный алгоритм симметричного обхода двоичного дерева:

void traverse_tree(tree *l) {
    if (l != nullptr) {
    traverse_tree(l->left);
    process_item(l->item) ;    //Что мы хотим сделать с элементом при обходе
    traverse_tree(l->right);
    }
}

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

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

Листинг 3.10. Вставка узла в двоичное дерево поиска:

void insert_tree(tree **l, item_type x, tree *parent) {
    tree *p;  // временный указатель

    if (*l == nullptr) {
        p = new tree;
        p->item = x;
        p->left = p->right = nullptr;
        p->parent = parent;
        *l = p;
        return;
    }

    if (x < (*l)->item) {
        insert_tree(&((*l)->left), x, *l);
    } else {
        insert_tree(&((*l)->right), x, *l);
    }
}

Процедура insert_tree принимает три аргумента:

• указатель l на указатель, связывающий поддерево с остальной частью дерева;

• вставляемый ключ x;

• указатель parent на родительский узел, содержащий l.

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

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

• Удаление листовых узлов: так как листовые узлы не имеют потомков, то их можно удалить, просто обнулив указатель на такой узел.

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

• Удаление узла с двумя потомками: нужно присвоить этому узлу ключ его непосредственного потомка в отсортированном порядке (найти минимальный элемент больше данного). Этот дочерний узел должен иметь наименьшее значение ключа в правом поддереве, т. е. быть самым левым узлом в правом поддереве родительского дерева. Перемещение этого потомка на место удаляемого узла дает в результате двоичное дерево с должным расположением ключей, а также сводит нашу задачу к физическому удалению узла с, самое большее, одним потомком, а это задача уже была решена ранее.

Для каждого удаления требуется самое большее две операции поиска, каждая из которых выполняется за время $O(h)$, где h $-$ высота дерева, плюс постоянные затраты времени на манипуляцию указателями.

Все три словарные операции (вставка, удаление, запрос), реализованные посредством двоичных деревьев поиска, исполняются за время $O(h)$, где h $-$ высота дерева, которая может быть заключена между значениями $lg\ n$ в наилучшем случае дерева и $n$ в наихудшем (n $-$ количество элементов в дереве). Наилучший случай достигается, когда дерево идеально сбалансированно. Наихудший - если, например, при построении дерева методом вставок элементы передавались в порядке возрастания. Тогда в итоговом дереве будут использоваться только правые узлы. Если предположить равновероятными каждое из $n!$ возможных упорядочиваний вставки, то с высокой вероятностью высота дерева окажется равной $\Theta(log\ n)$.

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

[ Скиена 2022 с. 108 - 114]

[ Бинарное дерево: как устроено и какие задачи дают на собеседованиях ]

[ Дерево (теория графов)]