31. Реализация множеств посредством сбалансированных деревьев

Подробно рассмотрим одну из таких реализаций, которая называется 2-3 дерево и имеет следующие свойства.

1. Каждый внутренний узел имеет или два, или три сына.

2. Все пути от корня до любого листа имеют одинаковую длину.

Будем считать, что пустое дерево и дерево с одним узлом также являются 2-3 деревьями.

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

Предполагаем, что упорядочивание элементов по используемому отношению линейного порядка основывается только на значениях одного поля (среди других полей записи, содержащей информацию об элементе), которое формирует тип элементов. Это поле назовем ключом. Например, если элементы множества - работники некоторого предприятия, то ключевым полем может быть поле, содержащее табельный номер или номер карточки социального страхования. В каждый внутренний узел записываются ключ наименьшего элемента, являющегося потомком второго сына, и ключ наименьшего элемента – потомка третьего сына, если, конечно, есть третий сын. Отметим, что 2-3 дерево с k уровнями имеет от 2^k-1 до З^k-1 листьев.

Другими словами, 2-3 дерево, представляющее множество из n элементов, будет иметь не менее 1+log₃n и не более 1+log₂n уровней. Таким образом, длины всех путей будут иметь порядок O(logn). Можно найти запись с ключом х в множестве, представленном 2-3 деревом, за время O(logn) путем простого перемещения по дереву, руководствуясь при этом значениями элементов, записанных во внутренних узлах.

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

• Если х<у, то перемещаемся к первому сыну узла node.

• Если х³у и узел node имеет только двух сыновей, то переходим ко второму сыну узла node.

• Если узел node имеет трех сыновей и х³у, то сравниваем х со значением z - вторым значением, записанным в узле node, т.е. со значением наименьшего элемента, являющегося потомком третьего сына узла node:

  • если х<z, то переходим ко второму сыну,

  • если х³z, переходим к третьему сыну узла node.

• Таким способом в конце концов мы придем к листу, и элемент х будет принадлежать исходному множеству тогда и только тогда, когда он совпадает с элементом, записанным в листе.

Очевидно, что если в процессе поиска получим х=у или х=z, поиск можно остановить. Но, конечно, алгоритм поиска должен предусмотреть спуск до самого листа.

Процесс вставки нового элемента х в 2-3 дерево начинается так же, как и процесс поиска элемента х.

• Пусть мы уже находимся на уровне, предшествующем листьям, в узле node, чьи сыновья (уже проверено) не содержат элемента х.

• Е сли узел node имеет двух сыновей, то мы просто делаем элемент х третьим сыном, помещая его в правильном порядке среди других сыновей. Осталось переписать два числа в узле node в соответствии с новой ситуацией.

• Ограничимся представлением посредством 2-3 деревьев множеств элементов, чьи ключи являются действительными числами. Общий тип записи обозначим как elementtype.

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

• Родители этих узлов являются записями, состоящими из двух полей действительных чисел и трех полей указателей на родителей листьев.

• Таким образом, разные уровни 2-3 дерева имеют разные типы данных (указатели на элементы или указатели на узлы).

• Эта ситуация вызывает затруднения при программировании на языке Pascal операторов, выполняемых над 2-3 деревьями. Но язык Pascal имеет механизм, вариант структуры record (запись), который позволяет обращаться с узлами 2-3 дерева, имеющими разный тип данных. В данном случае все равно каждый узел будет занимать пространство, равное пространству, занимаемому самым "большим" типом данных. Поэтому язык Pascal - не лучший язык для практической реализации 2-3 деревьев.