АиСД S02E05. Дерево поиска. АВЛ-дерево

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

[@Vlad-sh5kj]

28:19 Не понял, почему у АВЛ дерева высоты один, одна вершина. Почему одной вершины достаточно а не двух?

[@pavelmavrin]

Ну если в вершинах мерить длину пути. Если в ребрах, все на один больше будет

[@alexandroppolus]

2-3-дерево какое-то мутное. Как ни крути, с "тройным" узлом возиться в два раза дольше. И получается, что в худшем случае, например, правое поддерево может фактически быть в два раза выше левого, если брать количество действий. Да, это всё логарифм, но в этом плане АВЛ всё-таки более сбалансированное.

[@inf_math6862]

о чем вы: правое поддерево такой же высоты, как и левое. да, в одной вершинке хранятся 2 ключа, в этом и прелесть. и как вы ввели отношение сравнения на деревьях посика относительно сбалансированности -- для меня все еще загадка