АВЛ-дерево

---

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельского Георгия Максимовича и Ландиса Евгения Михайловича.

${\displaystyle h\;\leqslant \;\left\lfloor {\frac {\log _{2}(n+a)}{b}}-c\right\rfloor \;\leqslant \;\left\lfloor 1{,}45\log _{2}(n+2)\right\rfloor \;}$

${\displaystyle a={\frac {1+{\frac {3}{\sqrt {5}}}}{2}}\approx \;1{,}17082039324994}$ (округлить вверх),

${\displaystyle b=\log _{2}\left({\frac {1+{\sqrt {5}}}{2}}\right)\approx 0{,}694241913630617}$ (округлить вниз),

${\displaystyle c=2-{\frac {\log _{2}5}{2b}}\approx \;0{,}327724061815446}$ (округлить вниз).

---