[26.12.24] Scapegoat Tree

[Ruslan Savchenko]

В ближайший четверг в 16:30 состоится доклад Максима Бабенко Scapegoat Tree

Аннотация

На занятии мы рассмотрим scapegoat tree -- крайне простой и естественный способ балансировки бинарных деревьев поиска.

В отличие от альтернатив, требующих поддержания сложных и местами искусственных инвариантов и разбора множества случаев в процессе балансировки, scapegoat tree основано на простой идее: если какое-то из поддеревьев стало достаточно сильно несбалансированным, то нужно его полностью перестроить заново, превратив в сбалансированное.

Помимо этого мы посмотрим на некоторые естественные приложения scapegoat tree, в частности, на задачу двумерного поиска.

[Ruslan Savchenko]

Скоро начинаем https://yandex.zoom.us/j/91482099342

--

Best regards,
Ruslan Savchenko

[Ruslan Savchenko]

Запись https://disk.yandex.ru/d/QVC4UnqOMkhdgg