Почему Двоичные деревья Важны?

Двоичные деревья - это простейшая форма многосторонних деревьев, поэтому их легче изучать в этом смысле.

Многосторонние деревья имеют узлы, состоящие из N ] ключей и N + 1 указателей в строках:

               |
   +-----+-----+-----+-----+
   | k00 | k01 | k02 | k03 |
   +-----+-----+-----+-----+
  /      |     |     |      \
p00     p01   p02   p03     p04

Чтобы узнать, по какому указателю следует следовать при поиске, вы сравниваете ключ, который ищете, с ключами в узле. Этот пример выше представляет собой многоходовое дерево порядка 2 (я определяю порядок n как имеющий 2n ключей и 2n + 1 указателей).

Когда вы «вырождаете» эту структуру, чтобы получить наименьший возможный узел, вы получаете один ключ и два указателя, ваше классическое двоичное дерево:

      |
   +-----+
   | k00 |
   +-----+
  /       \
p00       p01

Когда я учился в университете (и я открыто признаю, что это было некоторое время назад), мы сначала изучили бинарные деревья , просто потому, что алгоритмы были элегантными. Поиск был простым сравнением узла и выбором одного из двух поддеревьев. Вставка и удаление также были относительно простыми.

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

Затем последовали несбалансированные многосторонние деревья, чтобы получить концепцию поиска внутри узла, как только вы нашли правильный узел, а затем, наконец, сбалансировать многосторонние деревья, которые были в основном такими же, как двоичные деревья, но с той же дополнительной сложностью последовательного поиска, а также вставки или удаления внутри узла и объединения и разделения самих узлов.

На каждом из этих шагов вы просто немного усложняли алгоритмы. Я не припоминаю, чтобы у слишком многих людей возникали проблемы с этой прогрессией, так что, возможно, все учебники, которые вы упоминаете, находятся только на начальном уровне.

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

Мы разработали реализацию многостороннего дерева под OS / 2 (здесь показан мой возраст) которые вопили, гарантируя, что узлы идентичны по размеру лежащим в основе дисковым блокам. Несмотря на то, что это могло привести к потере некоторого места, улучшение скорости того стоило.

Для содержимого в памяти: бинарные деревья обладают всеми преимуществами многосторонности без каких-либо дополнительных сложностей (необходимость сочетать последовательный поиск узла с выбором поддерева).

Бинарные деревья сводятся к следующему: «Должны ли мы двигаться влево или вправо?», Множественные способы - «Где в этом узле ключ, чтобы мы могли выбрать поддерево?».