8. Деревья поиска: продолжение

Суббота, 04 ноября 2017
НГУ, ауд. 2128, НГУ, новый корпус

Слайды с лекции

algorithms_1_lecture_041117.pdf

Описание

Декартовы деревья (дучи). Единственность декартова дерева для заданного набора различных ключей и приоритетов. Логарифмическая оценка матожидания высоты дучи. Операции слияния и разделения для дуч. Операции вставки и удаления элементов для дуч. Построение декартового дерева за линейное время при условии предварительной сортировки ключей. B+ деревья: определения и основные свойства. Операции поиска, вставки и удаления для B+ деревьев.