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