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