Реализации алгоритмов/АВЛ-дерево: различия между версиями

В АВЛ-дереве высоты <math>h</math> не меньше <math>F_h</math> узлов, где <math>F_h</math> — [[w:Числа Фибоначчи|число Фибоначчи]]. Поскольку <math>F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}} = \frac{\phi^n - (-\phi )^{-n}}{\phi - (-\phi )^{-1}}</math>,

где <math>\phi=\frac{1 + \sqrt{5}}{2}</math> — [[w:золотое сечение|золотое сечение]],

то имеем оценку на высоту АВЛ-дерева <math>h = O(log(n))</math>, где <math>n</math> — число узлов. Следует помнить, что <math>O(log(n))</math> — [http[wikt://ru.wiktionary.org/wiki/мажоранта |мажоранта]], и её можно использовать только для оценки (Например, если в дереве только два узла, значит в дереве два уровня, хотя <math>log(2)=1</math>). Для точной оценки глубины дерева следует использовать пользовательскую подпрограмму.