Сбалансированные сильно ветвящиеся деревья
Деревья бинарного поиска естественным образом обобщаются до
-арных деревьев поиска, в которых каждый узел имеет
сыновей и содержит
имен. Имена в узле делят множество имен на
подмножеств, каждое подмножество соответствует одному из
поддеревьев узла. На рис. 13.2 показано полностью заполненное 5-арное дерево с двумя уровнями. Заметим, что мы не можем требовать, чтобы каждый узел
-арного дерева имел ровно
сыновей и включал равно
имен; если мы захотим включить
в дерево на рисунке 13.2, то должны будем создать узлы с меньше чем
сыновьями и меньше чем
именами. Таким образом, определение
-арного дерева утверждает только, что каждый узел имеет не более
сыновей и содержит не более
имен. Ясно, что на
-арных деревьях можно осуществлять поиск так же, как и на бинарных деревьях.
Как и в деревьях бинарного поиска, полезно различать внутренние узлы и листья. Внутренний узел содержит
имен, записанных в естественном порядке, и имеет
сыновей, каждый из которых может быть либо внутренним узлом, либо листом. Лист не содержит имен (разве что временно в процессе включения), и, как раньше, в листьях - завершаются безуспешные поиски. Обычно за очевидностью мы на рисунке их опускаем.
Рис. 13.2. Абсолютно сбалансированное, полностью заполненное 5-арное дерево поиска
Сбалансированное сильно ветвящееся дерево порядка
есть
-арное дерево в котором:
- Все листья расположены на одном уровне.
- Корень имеет сыновей, .
- Другие внутренние узлы имеют сыновей, .
| |
Содержание раздела
| 
.
