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

Question

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

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

Answer 1

Да.

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

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

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

Answer 2

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

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

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

Answer 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.