AVL деревья не сбалансированы по весу?

В предыдущем вопросе было определение деревьев с балансом веса и вопрос, касающийся красно-черных деревьев.

Этот вопрос, чтобы задать тот же вопрос, но для деревьев AVL .

Вопрос в том, что, учитывая определение $\mu$ сбалансированных деревьев, как в другом вопросе,

Существует ли такое $\mu \gt 0$ , чтобы все достаточно большие AVL-деревья были $\mu$ сбалансированы?

Я предполагаю, что есть только одно определение деревьев AVL, и нет никакой двусмысленности.

Претензии : Нет, нет таких $\mu$ .

Доказательство : мы даем бесконечную последовательность деревьев AVL растущего размера, значение баланса веса стремится к $0$ , что противоречит утверждению.

Пусть полное дерево высоты h ; у него 2 часа + 1 - $C_h$$h$$2^{h+1}-1$ узел.

Пусть - дерево Фибоначчи высоты h ; имеет F h + 2 - 1 узлов. [ 1 , 2 , TAoCP 3 ]$S_h$$h$$F_{h+2} - 1$

Пусть теперь с T h = N ( S h , C h ) последовательностью деревьев, которую мы называем контрпримером.$(T_h)_{i\geq 1}$$T_h = N(S_h,C_h)$

Рассмотрим балансировочное значение корня для некоторого h ∈ N + :$T_h$$h \in \mathbb{N}_+$

$\qquad \displaystyle \begin{align*} \frac{F_{h+2}}{2^{h+1} + F_{h+2} - 1} &= \frac{1}{1 + \frac{2^{h+1}}{F_{h+2}} - \frac{1}{F_{h+2}{}}} \\ &\sim \frac{F_{h+2}}{2^{h+1}} \\ &= \frac{\frac{1}{\sqrt{5}}(\phi^{h+2} - \hat{\phi}^{h+2})}{2^{h+1}} \\ &\sim \frac{\phi^{h+2}}{\sqrt{5}\cdot 2^{h+1}} \underset{h \to \infty}{\to} 0 \end{align*}$

Это завершает доказательство.

Обозначение :

• - это n- ечисло Фибоначчи$F_n$$n$
• являетсяЗолотым сечением, ф ≈ - $\phi \approx 1.6$$\hat{\phi} \approx -0.62$ сопряженной.
• означает, что f и g асимптотически равны, т.е. lim n → ∞ f ( n $f \sim g$$f$$g$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$ .

Нота бене : деревья Фибоначчи - это именно те деревья AVL с наименьшим количеством узлов для данной высоты (или, что эквивалентно, максимальной высоты для данного числа узлов).

Приложение : Как мы можем придумать деревья Фибоначчи, если бы не слышали, как их упоминал профессор? Ну, как бы выглядело дерево AVL высотой с как можно меньшим количеством узлов? Конечно, вам нужен рут. Одно из поддеревьев должно иметь высоту h - 1 , и мы должны выбрать его с как можно меньшим количеством узлов. Другой может иметь высоту h - 2, не нарушая условия выравнивания высоты, и мы выбираем его также с как можно меньшим количеством узлов. По сути, мы строим деревья, которые хотим рекурсивно! Это первые четыре:$h$$h-1$$h-2$

^{[ источник ]}

Мы устанавливаем повторение для числа узлов в построенном таким образом дереве с высотой h :$f(h)$$h$

$\qquad \displaystyle \begin{align*} f(1) &= 1 \\ f(2) &= 2 \\ f(h) &= f(h-1) + f(h-2) + 1 \qquad n \geq 3 \end{align*}$

Решение этого приводит к который мы использовали выше.$f(h) = F_{h+2} - 1$

Такое же доказательство дано (с меньшими подробностями) в бинарных поисковых деревьях ограниченного баланса Nievergelt и Reingold (1972).