- АВЛ-деревья (Adelson-Velsky and Landis trees): Поддерживают баланс, контролируя разницу высот левого и правого поддеревьев для каждого узла (коэффициент баланca не более 1). Балансировка осуществляется с помощью поворотов.
- Красно-черные деревья (Red-Black trees): Используют дополнительный бит цвета для каждого узла (красный или черный) и набор правил для поддержания баланса. Сложнее для понимания и реализации, чем АВЛ-деревья, но часто имеют лучшую среднюю производительность вставок и удалений.
- Деревья 2-3 (2-3 trees): Каждый узел имеет 2-3 потомка и хранит 1-2 ключа. Все листья находятся на одном уровне. Балансировка осуществляется за счет слияния и расщепления узлов.
- B-деревья (B-trees): Обобщение деревьев 2-3, используемое в файловых системах и базах данных. Каждый узел имеет
M/2 \le K \le M ключей, где M — порядок дерева. Поддерживают баланс за счет аналогичных операций слияния и расщепления.
- Splay-деревья: Самооптимизирующиеся деревья, которые перемещают недавно accessed-элементы к корню с помощью операции splay. Не являются строго сбалансированными, но обеспечивают хорошую производительность для sequence-of-operations.
- Treap (Tree + Heap): Каждому узлу assigned a random priority. Узлы arranged так, чтобы they form a correct binary search tree with respect to keys и a min-heap (или max-heap) с respect to priorities. Баланс maintained via rotations to satisfy the heap property.
Из них наиболее commonly используемые в стандартных библиотеках и widely known are АВЛ-деревья and красно-черные деревья. B-деревья typically used in scenarios where data stored externally (on disk).