|
Читайте также: |
АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельского Георгия Максимовича и Ландиса Евгения Михайловича.
В АВЛ-дереве высоты h имеется не меньше Fh узлов, где Fh — число Фибоначчи.
Поскольку 
,
где 
— золотое сечение,
то имеем оценку на высоту АВЛ-дерева h=O(log(n)), где h — число узлов. Следует помнить, что h=O(log(n)) — мажоранта (функция), и её можно использовать только для оценки (Например, если в дереве только два узла, значит в дереве два уровня, хотя log(2)=1).
Дата добавления: 2015-08-10; просмотров: 83 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Свойства | | | Малое правое вращение |