АиСД S02E05. Дерево поиска, AVL-дерево
Алгоритмы и структуры данных. Семестр 2. Лекция 5.
На пятой лекции мы начали говорить про сбалансированные деревья поиска. Рассмотрели основные операции, которые можно с ним делать, и изучили способ балансировки, который используется в AVL-дереве.
Университет ИТМО, 2020 г.
Пікірлер: 11
Какой топовый препод. Не токсик, видно что шарит, нормально объясняет
Спасибо за вашу лекцию! Плюс еще одно знание в копилку молодого масленка.
спасибо за прекрасный разбор!
Превосходно
Спасибо за видеоурок
Годно
Доказать логарифмическую высоту AVL дерева можно чуть проще. Видно, что f(H)>= f(H-1)+f(H-2), а значит функция F растёт быстрее, чем числа Фибоначчи, которые растут экспоненциально.
Печально что нет кода добавления элемента в АВЛ дерево, включая все повороты.
Чтобы insert выглядел КРАСИВО, нужно возвращать из него корень результирующего поддерева, а в месте вызова писать `node = insert(node, x)` (в прод так писать, наверное, не стоит, потому что рекурсия таким образом перестаёт быть хвостовой, но для иллюстрации работы алгоритма вроде вполне норм) С erase аналогично
@pavelmavrin
3 жыл бұрын
Адам Смит норм план да, я так пишу декартово
16:03