Бинарные деревья

Бинарное дерево – это динамическая структура данных, в которой ка­ждый узел-родитель содержит, кроме данных, не более двух сыновей (левый и правый).

На рисунке приведен пример бинарного дерева (корень обычно изображается сверху, хотя изображение можно и перевернуть).

Такая структура данных организуется следующим образом (N – NULL):

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

Если дерево организовано таким образом, что для каждого узла все ключи его ле­вого поддерева меньше ключа этого узла, а все ключи его правого поддерева – больше, оно называется деревом поиска. Одинаковые ключи здесь не допускаются.

Представление динамических данных в виде древовидных структур оказывается довольно удобным и эффективным для решения задач быстрого поиска информации.

Сбалансированными, или AVL-деревьями, называются деревья, для каждого узла которых высóты его поддеревьев различаются не более чем на 1. Причем этот критерий обычно называют AVL-сбалансированностью в отличие от идеальной сбалансированности, когда для каждого узла дерева количество узлов в его левом и правом поддеревьях различаются не более чем на единицу [44].

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