Комбинаторные алгоритмы для программистов

          

Сбалансированные сильно ветвящиеся деревья


Деревья бинарного поиска естественным образом обобщаются до

Сбалансированные сильно ветвящиеся деревья
-арных деревьев поиска, в которых каждый узел имеет
Сбалансированные сильно ветвящиеся деревья

сыновей и содержит

Сбалансированные сильно ветвящиеся деревья
имен. Имена в узле делят множество имен на
Сбалансированные сильно ветвящиеся деревья
подмножеств, каждое подмножество соответствует одному из
Сбалансированные сильно ветвящиеся деревья

поддеревьев узла. На рис. 13.2 показано полностью заполненное 5-арное дерево с двумя уровнями. Заметим, что мы не можем требовать, чтобы каждый узел

Сбалансированные сильно ветвящиеся деревья
-арного дерева имел ровно
Сбалансированные сильно ветвящиеся деревья
сыновей и включал равно
Сбалансированные сильно ветвящиеся деревья
имен; если мы захотим включить
Сбалансированные сильно ветвящиеся деревья
в дерево на рисунке 13.2, то должны будем создать узлы с меньше чем
Сбалансированные сильно ветвящиеся деревья
сыновьями и меньше чем
Сбалансированные сильно ветвящиеся деревья
именами. Таким образом, определение
Сбалансированные сильно ветвящиеся деревья
-арного дерева утверждает только, что каждый узел имеет не более
Сбалансированные сильно ветвящиеся деревья
сыновей и содержит не более
Сбалансированные сильно ветвящиеся деревья
имен. Ясно, что на
Сбалансированные сильно ветвящиеся деревья
-арных деревьях можно осуществлять поиск так же, как и на бинарных деревьях.

Как и в деревьях бинарного поиска, полезно различать внутренние узлы и листья. Внутренний узел содержит

Сбалансированные сильно ветвящиеся деревья
имен, записанных в естественном порядке, и имеет
Сбалансированные сильно ветвящиеся деревья
сыновей, каждый из которых может быть либо внутренним узлом, либо листом. Лист не содержит имен (разве что временно в процессе включения), и, как раньше, в листьях - завершаются безуспешные поиски. Обычно за очевидностью мы на рисунке их опускаем.

Сбалансированные сильно ветвящиеся деревья

Рис. 13.2.  Абсолютно сбалансированное, полностью заполненное 5-арное дерево поиска

Сбалансированное сильно ветвящееся дерево порядка

Сбалансированные сильно ветвящиеся деревья
есть
Сбалансированные сильно ветвящиеся деревья
-арное дерево в котором:

  1. Все листья расположены на одном уровне.
  2. Корень имеет
    Сбалансированные сильно ветвящиеся деревья
    сыновей,
    Сбалансированные сильно ветвящиеся деревья
    .
  3. Другие внутренние узлы имеют
    Сбалансированные сильно ветвящиеся деревья
    сыновей,
    Сбалансированные сильно ветвящиеся деревья
    .

Сбалансированные сильно ветвящиеся деревья


Содержание раздела