Изменения

|definition='''Тонкое дерево ''' <tex>T^kT_k</tex> ранга <tex>k</tex> — это дерево, которое может быть получено из биномиального дерева <tex>B^kB_k</tex> удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына.}} Заметим, что у листьев детей нет, а если у корня <tex>B_k</tex> удалить самого левого сына, то <tex>B_k</tex> превратится в <tex>B_{k-1}</tex>. Ранг тонкого дерева равен количеству детей корня. Для любого узла <tex>x</tex> в дереве <tex>T_k</tex> обозначим: <tex>Degree(x)</tex> — количество детей узла <tex>x</tex>; <tex>Rank(x)</tex> — ранг соответствующего узла в биномиальном дереве <tex>B_k</tex>.  {{Утверждение|id=proposal1. |about=Свойства тонкого дерева|statement=1)Для любого узла <tex>x</tex> либо <tex>Degree(x)=Rank(x)</tex>, в этом случае говорим, что узел <tex>x</tex> не помечен (полный); либо <tex>Degree(x)=Rank(x)-1</tex>, в этом случае говорим, что узел <tex>x</tex> помечен (неполный).<br>2)Корень не помечен (полный).<br>3)Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>0,1,2,...,Degree(x)-1</tex>.<br>4)Узел <tex>x</tex> помечен тогда и только тогда, если его ранг на <tex>2</tex> больше, чем ранг его самого левого сына, или его ранг равен <tex>1</tex> и он не имеет детей.<br>}} {{Определение|id=def1. |definition='''Тонкий лес''' — это набор ''тонких деревьев'', ранги которых не обязательно попарно различны.}} {{Определение|id=def1. |definition='''Тонкая куча''' — это кучеобразно нагруженный ''тонкий лес''.}} Заметим, что в тонкой куче могут встречаться тонкие деревья одинакового ранга, в то время как в биномиальной куче все деревья должны иметь попарно различные ранги. {{Утверждение|id=proposal2. |statement=Для любого натурального числа <tex>n</tex> существует тонкий лес, который содержит ровно <tex>n</tex> элементов и состоит из тонких деревьев попарно различных рангов.|proof=Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.}} Пусть <tex>D(n)</tex> — максимально возможный ранг узла в тонкой куче, содержащей <tex>n</tex> элементов. {{Теорема|id=th1. |about=О максимальном ранге узла|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex>\Phi=\frac{1+\sqrt{5}}{2}</tex> — золотое сечение.|proof=Сначала покажем, что узел ранга <tex>k</tex> в тонком дереве имеет не менее <tex>F_k \geqslant \Phi^{k-1}</tex> потомков, включая самого себя, где <tex>F_k</tex> — <tex>k</tex>-е число Фибоначчи, определяемое соотношениями <tex>F_0=1</tex>, <tex>F_1=1</tex>, <tex>F_k=F_{k-2}+F_{k-1}</tex> для <tex>k \geqslant 2</tex>. Действительно, пусть <tex>T_k</tex> — минимально возможное число узлов, включая самого себя, в тонком дереве ранга <tex>k</tex>. По свойствам <tex>1</tex> и <tex>3</tex> ''тонкого дерева'' получаем следующие соотношения: <tex>T_0=1,T_1=1,T_k \geqslant 1+\sum_{i=0}^{k-2}T_i</tex> для <tex>k \geqslant 2</tex> Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что <tex>T_k \geqslant F_k</tex> для любых <tex>k</tex>. Неравенство <tex>F_k \geqslant \Phi^{k-1}</tex> хорошо известно. Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> ''тонкого дерева'' в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\Phi}(n)+1</tex>. Действительно, выберем в тонкой куче дерево максимального ранга. Пусть <tex>n^*</tex> — количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \Phi^{D(n)-1}</tex>. Отсюда следует, что <tex>D(n)\leqslant\log_{\Phi}(n)+1</tex>.