AVL-деревья (AVL-tree) были названы по имени российских математиков Адель-
сона-Вельского (Adelson-Velskii) и Ландау (Landis), которые их изобрели. В каждом
узле AVL-дерева глубина левого и правого поддеревьев отличаются не более чем на
единицу На рис. 7.2 изображено несколько AVL-деревьев.
Несмотря на то что AVL-дерево может быть несколько выше, чем полное дерево,
содержащее то же самое количество узлов, оно имеет такую же глубину O(logN).
Следовательно, поиск узла в AVL-дереве занимает время порядка O(log(N)), то есть
достаточно мало. Не так очевидно, что можно добавлять или удалять элементы из AVL-дерева за время O(logN) при сохранении баланса дерева. Рис. 7.2. AVL-деревья
Опубликовал Kest
October 23 2009 07:41:07 ·
0 Комментариев ·
11697 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.