Предпочтение между деревом AVL и деревом 2-3

Question

Может кто-нибудь сказать мне, если использование AVL предпочтительнее, чем использование дерева 2-3 или наоборот, и почему так?

Спасибо

Answer 1

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

Я также обычно предпочитаю деревья AVL хеш-таблицам. Я знаю, что ожидаемая сложность хеш-таблиц превосходит гарантированную сложность деревьев AVL, но на практике постоянные факторы делают две структуры данных в целом конкурентоспособными, и нет никаких беспокойств по поводу некоторых неожиданных данных, вызывающих плохое поведение. Кроме того, я часто нахожу, что когда-то в течение срока службы программы, в ситуации, не предусмотренной, когда первоначальный выбор хеш-таблицы казался правильным, мне нужны данные в отсортированном порядке, поэтому я в итоге переписываю программу, чтобы использовать Дерево AVL вместо хеш-таблицы; делайте это достаточно много раз, и вы узнаете, что можете начать с деревьев AVL.

Если ваши ключи являются строками, попытки троичного поиска предлагают разумную альтернативу деревьям AVL.

Answer 2

AVL Tree

Дерево AVL - это самобалансирующееся бинарное дерево поиска, изобретенное Г.М. Адельсоном-Вельским и Е.М.Ландисиным в 1962 году. Дерево названо AVL в честь своих изобретателей. В дереве AVL высоты двух поддеревьев узла могут отличаться не более чем на единицу. Благодаря этому свойству дерево AVL также известно как дерево с сбалансированной высотой.

2–3 Дерево

В дереве 2-3 каждый внутренний узел имеет двух или трех дочерних узлов. Узлы с двумя потомками называются 2-узлами. 2-узлы имеют одно значение данных и два дочерних узла. Узлы с тремя дочерними узлами называются 3-узлами. 3-узлы имеют два значения данных и трех дочерних элементов (левый, средний и правый дочерние элементы)

Пример: 2-3 дерева

Это означает, что дерево 2-3 не является двоичным деревом. В этом дереве все узлы листьев находятся на одном уровне (нижний уровень).

Здесь вы можете найти разницу между почти всеми видами деревьев в структуре данных... https://knowshares.wordpress.com/2017/01/01/difference-binary-binarysearch-avl-2-3-b-trees/