Сравнение сбалансированных бинарных деревьев поиска - PullRequest
Новая
       86

Сравнение сбалансированных бинарных деревьев поиска

3 голосов
/ 27 августа 2011

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

Первый из них, который я узнал, это AVL, второй - Красно-Черное дерево.

Есть кое-что, что я не совсем понимаю: согласно некоторым книгам и статьям, AVL может выполнять поиск немного быстрее, чем красно-черное дерево, ну, это понятно.

  1. Тогда что такое край красно-черного дерева над AVL?

  2. В AVL, вероятно, после каждой вставки мы должны проверять баланс, но в красно-черном дереве нам не нужно часто что-то делать, верно?

PS: Я ищу что-то подобное, но я не получил удовлетворительного ответа. Надеюсь, что некоторые друзья могут дать мне подробное сравнение самобалансирующихся деревьев.

1 Ответ

2 голосов
/ 27 августа 2011

Дерево AVL имеет следующее свойство: для каждого узла разница в высоте левого и правого поддерева не превышает 2.

В красно-черном дереве, с другой стороны,высота левого или правого поддерева любого узла не более в два раза высоты другого дерева.То есть они отличаются не более чем в 2 раза.

Это интуитивно показывает, что поиск действительно быстрее в среднем в дереве AVL.

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

...