Сбалансированные бинарные деревья. Включение вершины в сбалансированное дерево поиска, страница 3

Add (x:inf; var p:ptr; var Bh: Boolean)

                         нет

  Начало        P=NULL         p^.key > x          p^.key < x

                    да

Bh=TRUE       NEW(P)       add(x,p^.lp,Bh)       add(x,p^.rp,Bh)

 

  P^.key=x                                           ...       p^.inf=

нет

  P^.inf=1                          Bh=TRUE                    p^.inf+1

 

  P^.lp=NULL                             да

  P^.rp=NULL      Bh=FALSE    да

                                   p^.bal=1                    Конец

P^.bal=0        p^.bal=-1

                                         нет

                              да

   Конец          p^.bal=-1        p^.bal=0

 

                                         нет

                LR-поворот         lp.bal=-1

 

  Bh=FALSE       p^.bal=0         LL-поворот

Рисунок 6

В-деревья

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

Существует, однако, одна весьма практическая область применения сильно ветвящихся деревьев, представляющая общий интерес. Это формирование и ведение крупномасштабных деревьев поиска, для которых недостаточно оперативной памяти, либо требуется их долговременное хранение и обработка информации по частям.

Будем считать, что вершины дерева должны храниться на магнитном диске, а ссылки являются адресами на диске. Сильно ветвящиеся деревья представляют собой идеальное решение этой проблемы. Если происходит обращение к одному элементу, расположенному во вторичной памяти, то без больших дополнительных затрат можно обратиться к целой группе элементов. Это предполагает, что дерево разбито на поддеревья и эти поддеревья как раз те группы, которые одновременно доступны. Будем называть такие поддеревья страницами. На рис.4 приведено разбиение на страницы бинарного дерева. Так как каждое обращение к странице требует лишь одного обращения к диску, то экономия таких обращений может быть весьма существенной.

Для сильно ветвящихся деревьев можно отказаться от требования идеальной сбалансированности, очевидно, по аналогии с бинарными деревьями критерии сбалансированности могут быть смягчены. В 1970 году Бэйер Р. и Маккрейт Е. сформулировали следующий, как оказалось, плодотворный критерий сбалансированности: «Каждая страница дерева поиска, исключая первую, должна содержать при заданном постоянном n от n до 2n вершин». Таким образом, для дерева с N элементами и максимальным размером страницы в 2n вершин при выполнении этого требования в самом худшем случае получается логарифм от N по основанию n обращений к страницам. Кроме того, память, выделенная для хранения деревьев, используется не ниже, чем на 50%, поскольку страницы всегда заполнены минимум наполовину. На рис.5 приведен пример дерева поиска, построенного с использованием приведенного выше критерия.

Структуры данных, о которых идет речь, называются B-деревьями, а n – порядком В-дерева. Они обладают следующими свойствами:

-  каждая страница содержит не более 2n элементов,

-  каждая страница, кроме первой, содержит не менее n элементов,

-  каждая страница является либо листом, либо имеет m+1 потомков, где m число ключей на странице,

-  все страницы листья находятся на одном уровне.

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