АиСД S02E06. Декартово дерево, дерево по неявному ключу

Алгоритмы и структуры данных. Семестр 2. Лекция 6.
На шестой лекции мы продолжили говорить про сбалансированные деревья поиска. Изучили, как работает декартово дерево, а так же познакомились с новой структурой данных - деревом поиска по неявному ключу.
Университет ИТМО, 2022 г.

[@innokentiyromanchenko1450]

спасибо за лекции

[@Relice]

декартово дерево работает быстро только тогда когда 'x' и 'y' рандомные??? например если 'x' и 'y' отсортированы он же будет долго работать??

[@s_alexander_n]

Да, но у этого очень маленькая вероятность: при рандоме средняя высота дерева не больше 4•log(n)