Построение бинарного дерева
В программировании наибольшее распространение получили упорядоченные двоичные деревья поиска. Правило построения такого дерева следующее: элементы, у которых значение некоторого признака (ключа) меньше, чем у корня, всегда включаются слева от некоторого поддерева, а элементы со значениями, большими, чем у корня - справа. Этот принцип используется как при формировании двоичного дерева, так и при поиске в нем элементов.
Таким образом, при поиске элемента с некоторым значением ключа происходит спуск по дереву, начиная от корня. Выбор направления следующего шага – направо или налево (по значению искомого ключа) - происходит в каждом очередном узле на пути. При поиске элемента результатом будет либо узел с заданным ключом, либо лист с «нулевой» ссылкой (искомый элемент отсутствует на проделанном пути). Последняя ситуация может возникнуть, например, если целью поиска было включение очередного узла в дерево. При этом справа или слева (в зависимости от значения признака) к листу будет присоединен новый узел.
Рассмотрим пример формирования двоичного дерева. Предположим, что нужно сформировать двоичное дерево, узлы (элементы) которого имеют следующие значения признака: 20, 10, 35, 15, 17, 27, 24, 8, 30. В этом же порядке они и будут поступать для включения в двоичное дерево.
Первым узлом в дереве (корнем) станет узел со значением 20. В общем случае, поиск места подключения очередного элемента всегда начинается с корня. К корню слева подключается элемент 10, а справа - 35. Далее элемент 15 подключается справа к 10, проходя путь: корень 20 - налево - элемент 10 - направо - подключение, так как дальше пути нет. Процесс продолжается до тех пор, пока не будут включены в дерево все элементы. Результат представлен на рис. 5.6.
Отметим, что при создании двоичного дерева обычно считается, что ключи элементов не повторяются.
Узлы, у которых заполнены два адреса связи считаются полными, а с одним адресом – неполными. Элементы с двумя незаполненными адресами называются концевыми (листьями).
В упорядоченном бинарном дереве значение ключевого атрибута каждого узла должно быть больше, чем значение ключа у любого элемента на его левой ветви, и не меньше, чем ключ на его правой ветви.
Рис. 5.6. Построение бинарного дерева.
Значения элементов дерева: 20, 10, 35, 15, 17, 27, 24, 8, 30
Алгоритм построения упорядоченного бинарного дерева может быть сформулирован так.
1.Первый элемент с ключом р[1] становится корнем дерева.
2.Значение ключа второго узла р[2] сравнивается с р[1] (корня дерева). Если р[2] < p[1], то второй элемент помещается на левой от корня ветви, в противном случае – на правой. В результате будет получено упорядоченное дерево из первых двух узлов.
3. Далее на каждом шаге создается упорядоченное дерево из первых i элементов. Выбор i-го узла производится следующим образом. Ключ р[i] сравнивается с корневым значением и выполняется переход по левому адресу (если р[1]>р[i]), в противном случае (при р[1] <= р [i]) – по правому адресу. Далее ключ достигнутого узла также сравнивается с р[i], и снова организуется переход по левому и правому адресу и т.д. При нахождении незаполненного адреса связи ему присваивается ключ р[i].
Пункт 3 повторяется до тех пор, пока не будут включены в дерево все элементы исходного массива.
Из рассмотренного алгоритма следует, что основным методом, используемым при построении двоичного дерева и решении других задач, является поиск. В процессе поиска в упорядоченном бинарном дереве просматривается некоторый путь, начинающийся всегда в его корне. Искомое значение ключа q сравнивается со значением корня р[1]. Если р[1]>q, просмотр дерева продолжается по левой от корня ветви, иначе (если р[1] <= q) – по правой. Для произвольного узла с ключом р[i] могут быть получены следующие результаты сравнения:
р[i] = q – элемент, удовлетворяющий условию поиска найден, и поиск заканчивается по правой ветви.
р[i] >q – производится переход к элементу, расположенному на левой ветви р(i).
р[i] < q – производится переход к элементу, расположенному на правой ветви р[i].
Поиск заканчивается, когда у какого-либо узла отсутствует адрес связи, необходимый для дальнейшего продолжения поиска.
Построение В+ дерева
При выполнении этой операции руководствуются основным правилом: изначально все узлы кроме последнего содержат один дополнительный элемент (то есть m+1 потомков в сумме), который будет использован для построения внутренних узлов.
Рассмотрим алгоритм на примере. Пусть количество потомков для каждого листового узла не более 4, то есть степень дерева m = 5. На вход подана последовательность чисел от 1 до 24. Разобьём их на блоки по приведенному правилу:
1|2|3|4|5 6|7|8|9|10 11|12|13|14|15 16|17|18|19|20 21|22|23|24
Из слоя листовых узлов строим следующий уровень путём вынесения туда лишних (в данном случае пятых) элементов на уровень выше. У четырех из пяти блоков такие элементы есть. Это – 5, 10, 15 и 20. Полученный новый уровень разбиваем в соответствии с тем же правилом.
Пусть для внутренних (нелистовых) узлов будет задано ограничение на количество потомков, равное 2 (по свойствам 2 и 3 узлов В-дерева). Результат вынесения элементов на верхний уровень приведен ниже.
5|10|15 20
1|2|3|4 6|7|8|9 11|12|13|14 16|17|18|19 21|22|23|24
Продолжаем процесс, пока не получим корень.
15
5|10 20
1|2|3|4 6|7|8|9 11|12|13|14 16|17|18|19 21|22|23|24
Осталось добавить ссылки и получится готовое В-дерево.