Что я должен выбрать для простого в коде сбалансированного бинарного дерева поиска?
Я хотел бы знать, какой сбалансированный BST будет легко кодировать на C ++, и при этом его сложность будет примерно равна O (logn).
Я уже пробовал деревья Red Black, но хотел бы найти альтернативу, которая менее сложна для написания кода. Я работал с Treaps в прошлом, но мне интересно изучить варианты, которые либо работают лучше, либо их легче реализовать.
Каковы ваши предложения?
Решение
AVL деревья в общем, лучше, чем Treaps, по моему опыту, и их не сложнее реализовать.
Они работают, вращая ветви дерева, которые становятся несбалансированными после любой вставки или удаления. Это гарантирует, что у них будет идеальный баланс, чтобы они не могли быть обмануты странными данными.
Treaps, с другой стороны, распределяются случайным образом, что для больших наборов данных близко к сбалансированному, но вы все равно не получите этот идеальный O (logn). Более того, вы можете случайно встретить набор данных, который вставляется очень несбалансированным образом, и ваше время доступа может приблизиться к O (n).
Проверьте страницу википедии для получения дополнительной информации: en.wikipedia.org/wiki/Avl_tree
Другие решения