Идеально сбалансированное дерево (никто не знает точного определения?)

oleg1966

субж.

Togar

Для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1.
(cs.mipt.ru/stolyarov/ComputerScienceI/lec5.DOC и
http://www.pascaler.ru/dynamics/derevo/dynamics_4.php)

oleg1966

Это ж вроде просто сбалансированные. Нет, не так?
а что тогда "сбалансированные деревья", если это определение для идеальных?

spider44

Н. Вирт, "Алгоритмы и структуры данных":
Одно из определений сбалансированного дерева было предложено Г. М. Адельсоном-Вельским и Е. М. Ландисом. Их критерий сбалансированности сформулирован так:
Дерево называется сбалансированным тогда и только тогда, когда высоты двух поддеревьев каждой из его вершин отличаются не более чем на единицу.
Деревья, удовлетворяющие такому условию, часто называют АВЛ-деревьями (по имени их открывателей). Все идеально сбалансированные деревья являются также АВЛ-деревьями.

oleg1966

Че-то я не пойму, так чем же отличаются "идеально сбалансированное дерево" от "сбалансированного дерева" ?

shpanenoc

Может быть, идеально сбалансированное - это такое дерево, что все его уровни, кроме, возможно, последнего, полностью заполнены? Что-то подобное видел у Кормена, но могу ошибаться.

spider44

Определение идеально сбалансированного дерева выше правильно написали.

spider44

Че-то я не пойму, так чем же отличаются "идеально сбалансированное дерево" от "сбалансированного дерева" ?
Отличие в том, что в критерии сбалансированного дерева для каждой вершины в её двух поддеревьях различаются не более чем на единицу их высОты, а в определении идеально сбалансированного дерева - количество вершин.

valex1971

Я-то откуда знаю? Макагня какая-то...
Оставить комментарий
Имя или ник:
Комментарий: