Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Теоретические вопросы _ AVL-деревья

Автор: compiler 3.06.2008 1:25

Добрый день! Вот занялся познанием AVL-деревьев. Но сразу возник вопрос: как возможно следующие:

Цитата
...разность высот ее левого и правого поддеревьев была по абсолютной величине не больше единицы. При этом длины путей от корня к внешним вершинам могут различаться больше, чем на единицу.

То ли это вечер влияет, толи что-то другое... Но никак не могу придумать такое дерево wacko.gif
Очень бы хотелось увидеть пример...

Заранее благодарен.

Источник цитаты: http://www.intuit.ru/department/se/pbmsu/12/3.html

Автор: volvo 3.06.2008 1:39

Цитата
Очень бы хотелось увидеть пример...
Ну, вот так, скажем:
http://users.informatik.uni-halle.de/~jopsi/dinf204/avl_tree.gif

Высоты поддеревьев всех узлов не отличаются больше, чем на 1, в то же время есть пути (к листьям из корня), различающиеся по длине больше чем на 1...

Автор: compiler 3.06.2008 1:44

Цитата(volvo @ 2.06.2008 21:39) *
Ну, вот так, скажем: ...
пошел я спать)))

огромное спасибо!