Деревья поиска

Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте. АВЛ-дерево: верхняя оценка $O(logn)$ на высоту, сохранение свойства при помощи малых и больших вращений.