Идеально сбалансированные бинарные деревья

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

БД идеально сбалансировано, если для каждого его узла количество потомков в левом и правом поддеревьях различается не более чем на 1.

Рассмотрим алгоритм построения идеально сбалансированного БД. Если количество узлов дерева известно, и дана последовательность значений его вершин a[1], a[2],…a[n], то можно применить следующий рекурсивный алгоритм построения идеально сбалансированного БД.

1. Начиная с a[1], выбираем очередное a[i] в качестве значения корня дерева (поддерева).

2. Тем же способом строим левое поддерево с количеством узлов

3. Строим правое поддерево с количеством узлов

Таким образом, значение a[1] окажется в корне дерева, и именно на него будет ссылаться указатель дерева. Значения попадут в левое поддерево, а значения – в правое поддерево. Следовательно, распределение значений по узлам дерева полностью определяется исходной последовательностью данных. На рис. 30 показано идеально сбалансированное БД, построенное по следующему набору значений узлов: 9, 17, 20, 16, 12, 21, 6, 3, 11, 4, 19, 14, 13, 1, 5, 2, 8, 18, 7, 10, 15.

Рис. 30 – Идеально сбалансированное БД

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

рядка где n – количество узлов дерева.

Добавление и удаление узлов идеально сбалансированного дерева вызывают некоторые трудности. Чтобы поддерживать сбалансированность дерева при добавлении и удалении узлов, необходимо иметь информацию о сбалансированности каждого поддерева и поддерживать ее. Поэтому идеально сбалансированные деревья применяются для работы с данными, которые мало изменяются в процессе обработки.

Дата добавления: 2015-07-16