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

Четверг, 27 ноября 2014
ФМЛ 239, Актовый зал

Описание

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