Бинарные деревья - это самая простая форма многоцелевых деревьев, поэтому их легче изучать в этом смысле.
У деревьев с несколькими путями есть узлы, которые состоят из N ключей и N+1 указателей вдоль строк:
|
+-----+-----+-----+-----+
| k00 | k01 | k02 | k03 |
+-----+-----+-----+-----+
/ | | | \
p00 p01 p02 p03 p04
Чтобы узнать, по какому указателю следовать в поиске, вы сравниваете ключ, который ищете, с ключами в узле. В приведенном выше примере показано многоуровневое дерево порядка 2 (я определяю порядок n как имеющий 2n ключей и 2n+1 указателей).
Когда вы «выродите» эту структуру, чтобы получить наименьший возможный узел, вы получите один ключ и два указателя, ваше классическое двоичное дерево:
|
+-----+
| k00 |
+-----+
/ \
p00 p01
Когда я поступил в университет (и я свободно признаю, что это было некоторое время назад), мы изучали двоичные деревья сначала , просто потому, что алгоритмы были элегантными. Поиск был простым узлом сравнения и выбрал одно из двух поддеревьев. Вставка и удаление также были относительно простыми.
Затем мы перешли к сбалансированным двоичным деревьям, где поиск был точно таким же, но вставка и удаление были немного более сложными, включая вращение поддеревьев через корень поддерева при необходимости. чтобы сохранить равновесие.
Затем следовали несбалансированные многоходовые деревья, чтобы получить концепцию поиска в узле, как только вы нашли правильный узел, и, наконец, сбалансированные многоходовые деревья, которые были в основном такими же, как двоичные деревья, но с той же добавленной сложностью последовательного поиска, а также вставки или удаления внутри узла и объединения и разбрызгивания самих узлов.
На каждом из этих шагов вы просто добавляли немного больше сложности к алгоритмам. Я не помню, чтобы у многих людей были проблемы с этим прогрессом, поэтому, возможно, все учебники, о которых вы говорите, находятся только на начальном уровне.
Я никогда не считал, что многоходовые деревья более полезны, чем бинарные, за исключением одной очень специфической ситуации. Вот когда вы читаете узлы дерева с медленного носителя, такого как диск, и вы оптимизировали его для секторов / кластеров / блоков.
Мы разработали многопользовательскую реализацию дерева в OS / 2 (показывающую мой возраст здесь), которая выкрикивалась вперед, гарантируя, что узлы были идентичны по размеру базовым дисковым блокам. Несмотря на то, что это может привести к потере пространства, улучшение скорости того стоило.
Для вещей в памяти двоичные деревья обладают всеми преимуществами многоканальности без каких-либо дополнительных сложностей (необходимость сочетать последовательный поиск узла с выбором поддерева).
Двоичные деревья сводятся к «Должны ли мы двигаться влево или вправо?», Многозначными являются «Где ключ в этом узле, чтобы мы могли выбрать поддерево?».