Мое предпочтение среди различных разновидностей сбалансированных бинарных деревьев - это деревья AVL. Они проще в программировании, чем любая из альтернатив (см. Мою реализацию здесь и здесь , и обратите внимание, что даже удаление не особенно сложно), потому что есть меньше случаев, чтобы рассмотреть, они обеспечить очень-чуть более быстрый поиск (потому что они более строго сбалансированы, чем альтернативы), и нет никаких скрытых наихудших случаев или амортизированных временных границ.
Я также обычно предпочитаю деревья AVL хеш-таблицам. Я знаю, что ожидаемая сложность хеш-таблиц превосходит гарантированную сложность деревьев AVL, но на практике постоянные факторы делают две структуры данных в целом конкурентоспособными, и нет никаких беспокойств по поводу некоторых неожиданных данных, вызывающих плохое поведение. Кроме того, я часто нахожу, что когда-то в течение срока службы программы, в ситуации, не предусмотренной, когда первоначальный выбор хеш-таблицы казался правильным, мне нужны данные в отсортированном порядке, поэтому я в итоге переписываю программу, чтобы использовать Дерево AVL вместо хеш-таблицы; проделайте это достаточно раз, и вы узнаете, что можете начать с деревьев AVL.
Если ваши ключи являются строками, троичный поиск предлагает разумную альтернативу деревьям AVL.