АиСД S02E05. Дерево поиска. АВЛ-дерево
HTML-код
- Опубликовано: 30 сен 2024
- Алгоритмы и структуры данных. Семестр 2. Лекция 5.
На пятой лекции мы начали говорить про сбалансированные деревья поиска. Рассмотрели основные операции, которые можно с ним делать, и изучили способ балансировки, который используется в АВЛ-дереве.
Университет ИТМО, 2022 г.
28:19 Не понял, почему у АВЛ дерева высоты один, одна вершина. Почему одной вершины достаточно а не двух?
Ну если в вершинах мерить длину пути. Если в ребрах, все на один больше будет
2-3-дерево какое-то мутное. Как ни крути, с "тройным" узлом возиться в два раза дольше. И получается, что в худшем случае, например, правое поддерево может фактически быть в два раза выше левого, если брать количество действий. Да, это всё логарифм, но в этом плане АВЛ всё-таки более сбалансированное.
о чем вы: правое поддерево такой же высоты, как и левое. да, в одной вершинке хранятся 2 ключа, в этом и прелесть. и как вы ввели отношение сравнения на деревьях посика относительно сбалансированности -- для меня все еще загадка