Деревья поиска, АВЛ-деревья

Двочиное дерево поиска как структура, поддерживающая операции \({\tt Search}\), \({\tt Insert}\), \({\tt Delete}\), \({\tt Min/Max}\), \({\tt Succ/Pred}\), \({\tt LowerBound/UpperBound}\), \({\tt Statistics}\) за время, пропорциональное высоте дерева. Сравнение с хеш-таблицей. АВЛ-дерево: доказательство логарифмической оценки на высоту, малые и большие вращения.