Почему avl-дерево быстрее для поиска, чем красное черное дерево?

Я прочитал его в нескольких местах, что поиск дерева avl быстрее, но не способен понять. Насколько я понимаю: максимальная высота красно-черного дерева = 2 * log (N + 1) высота дерева AVL = 1.44 * логотип (N + 1)

Это потому, что AVL короче?

Ответ 1

Да.

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

Поскольку дерево AVL упаковано более плотно (т.е. имеет меньшую максимальную высоту), это означает, что больше предметов ближе к корню, чем в случае с красным-черным.

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

Ответ 2

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

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

В целом, это зависит от входной последовательности, которая будет определять, как наклонно наше дерево, и выполняемая операция. Для использования вставки с использованием Red-Black Tree и для поиска с использованием AVL.

Ответ 3

Дерево AVL и RBTree имеют соответствующие преимущества, а также недостатки. Вы поймете, что лучше, если вы уже узнали, как они работают.

AVL немного быстрее, чем RBTree в операции вставки, потому что в вставке должно быть не более одного вращения, тогда как для RBTree может быть два.

RBTree требуется всего три вращения при удалении, но это не гарантируется в AVL. Таким образом, он может удалять узлы быстрее, чем AVL.

Однако, прежде всего, они имеют строгую логарифмическую высоту дерева.

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

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

Вот некоторые факты, которые могут быть более точными:

Высота дерева AVL строго меньше: 1.44log (n + 2) -0.328 (Приблизительно)

Высота красно-чёрного дерева не более 2log (n + 1)

Подробнее см. https://en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structures.