Сбалансированные деревья

Дерево называется сбалансированным (или АВЛ-деревом в     честь изобретателей этого метода Г.М. Адельсона-Вельского и E.М. Ландиса), если для любой его вершины высоты левого и правого поддеревьев этой вершины отличаются не более чем на 1. (В частности, когда одного из сыновей нет, другой -- если он есть -- обязан быть листом.)


$\scriptstyle{\blacktriangleright}$ 12.2.1. Найти минимальное и максимальное возможное количество вершин в сбалансированном дереве высоты n .

Решение. Максимальное число вершин равно 2n -- 1. Если mn -- минимальное число вершин, то, как легко видеть, mn + 2 = 1 + mn + mn+1 , откуда $m_n = \Phi_{n+2} - 1$   ($\Phi_n$ -- n -ое число Фибоначчи, $\Phi_1=1$, $\Phi_2=1$,$\Phi_{n+2} = \Phi_n + \Phi_{n+1}$).$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 12.2.2. Доказать, что сбалансированное дерево с n вершинами имеет высоту не больше $C\log n$ для некоторой константы C , не зависящей от n .

Решение. Индукцией по n легко доказать, что $\Phi_{n+2} \geqslant a^n$, где a -- больший корень квадратного уравнения a2=1+a , то есть $a = (\sqrt{5} + 1)/2$. Остается воспользоваться предыдущей задачей.$\scriptstyle\blacktriangleleft$


 
pvv
1/8/1999