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

Ответ 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, чтобы мы могли выбрать поддерево?".

Ответ 2

Двоичные деревья - это простая концепция, их легко понять, легко реализовать и работать хорошо и быстро - я полагаю, этого достаточно для обучения и/или использования их.

Ответ 3

Преимущество двоичных деревьев над деревьями "n-ary" заключается в том, что их перемещение часто сводится к простой проблеме решения "да/нет", как в двоичный разделение пространства.

Ответ 4

Поскольку структуры дерева данных часто используются для упорядочения упорядоченных элементов, например: a > b > c. Если ваши элементы, вставленные в деревья, упорядочены, все, что вам нужно, - это две ветки на каждом node, чтобы разделить элементы, которые больше в левом поддереве, и элементы, которые меньше в правом поддереве.

Вот почему бинарные деревья гораздо более распространены, чем m-арные деревья. Это не имеет никакого отношения к простоте принятия решения "да/нет" по сравнению с м-арным решением!

Ответ 5

Добавляя к всем приведенным выше ответам, дерево любой арности может быть представлено двоичным деревом (где левая ссылка переходит к первому дочернему элементу node, а правильная ссылка переходит к следующему "брату" ).

Ответ 6

Я не собираюсь быть слишком много techi здесь.. потому что вопрос в том, почему Binary Tree уделяет столь большое значение в DataStructure. Двоичное дерево, означает дерево, основанное на T/F, да/нет и т.д. Предположим, что сочетание Duo. Практически мы сталкиваемся с ситуацией, когда нам нужно решить "да" или "нет". Верно или неверно. Такое двоичное дерево. Программные средства, над которыми мы работаем, - это решения, которые собираются использовать структуры данных, используемые внутри, чтобы решить сценарии реальной жизни. Именно поэтому бинарное дерево входит в картину и обычно используется и даже важно. Остальные деревья являются дополнительными усовершенствованиями или добавленными сложностями, соответствующими их типичным ситуациям. Для запуска двоичного дерева всегда важно.

Ответ 7

Например, бинарные деревья используются для сортировки кучи (двоичная куча). Это способ для очень быстрой сортировки данных, так что самый большой (или самый низкий) элемент всегда находится спереди. Это используется, например, в алгоритме AI (A *).