Что я должен выбрать для простого в коде сбалансированного бинарного дерева поиска?

Question

Что я должен выбрать для простого в коде сбалансированного бинарного дерева поиска?

Я хотел бы знать, какой сбалансированный BST будет легко кодировать на C++, и при этом его сложность будет примерно равна O(logn).

Я уже пробовал деревья Red Black, но хотел бы найти альтернативу, которая менее сложна для кодирования. Я работал с Treaps в прошлом, но мне интересно изучить варианты, которые либо работают лучше, либо их легче реализовать.

Каковы ваши предложения?

1

c++ binary-search-tree red-black-tree treap

Источник

user2270136 27 июл '14 в 14:21

1 ответ

Решение

Другие вопросы по тегам c++ binary-search-tree red-black-tree treap

user3399526 29 июл '14 в 16:08 2014-07-29 16:08 · Accepted Answer · 2014-07-29 16:08

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

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

Вращения в дереве AVL

Treaps, с другой стороны, распределяются случайным образом, что для больших наборов данных близко к сбалансированному, но вы все равно не получите этот идеальный O(logn). Кроме того, вы можете случайно встретить набор данных, который вставляется очень несбалансированным образом, и ваше время доступа может приблизиться к O(n).

Посетите страницу Википедии для получения дополнительной информации: http://en.wikipedia.org/wiki/Avl_tree