Тонкая куча - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:42:19Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:25, 1 сентября 2022

2022-09-01T03:25:21Z

176.195.102.171 в 05:01, 7 мая 2018

2018-05-07T05:01:56Z

Vitalik: Почему "meld", если "merge"! :)

2016-10-28T19:31:47Z

Почему "meld", если "merge"! :)

Shersh: /* Тонкая куча */

2015-06-08T21:39:57Z

‎Тонкая куча

Maksnov в 12:51, 8 июня 2015

2015-06-08T12:51:28Z

Maksnov в 08:41, 7 июня 2015

2015-06-07T08:41:48Z

Внесённые изменения

Genyaz в 08:03, 11 июня 2013

2013-06-11T08:03:30Z

Genyaz в 07:57, 11 июня 2013

2013-06-11T07:57:59Z

Genyaz: /* extractMin */

2013-06-05T11:10:23Z

‎extractMin

← Предыдущая		Версия 16:42, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Тонкая куча''' (англ. ''Thin heap'') {{---}} структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[Фибоначчиева куча\|фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.		'''Тонкая куча''' (англ. ''Thin heap'') {{---}} структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[Фибоначчиева куча\|фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.

← Предыдущая		Версия 03:25, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Тонкая куча''' (англ. ''Thin heap'') {{---}} структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[Фибоначчиева куча\|фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.		'''Тонкая куча''' (англ. ''Thin heap'') {{---}} структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и [[Фибоначчиева куча\|фибоначчиева куча]], но имеющая большую практическую ценность из-за меньших констант.

@@ Строка 125: / Строка 125: @@
 }}
-Пусть <tex>\mathtt{Node}</tex> {{---}} узел тонкого дерева, а <tex>\mathtt{ThinHeap}</tex> {{---}} тонкая куча, причем <tex>\mathtt{ThinHeap}</tex> содержит ссылки на первый и последний корень <tex>\mathtt{first}</tex> и <tex>\mathtt{last}</tex> соответственно.
+Пусть <tex>\mathtt{Node}</tex> {{---}} узел тонкого дерева, а <tex>\mathtt{ThinHeap}</tex> {{---}} тонкая куча, причём <tex>\mathtt{ThinHeap}</tex> содержит ссылки на первый и последний корень <tex>\mathtt{first}</tex> и <tex>\mathtt{last}</tex> соответственно.
 Также введем вспомогательную функцию проверки узла на тонкость, для этого воспользуемся тем, что у левого сына узла <tex>x</tex> ранг равен <tex>\mathtt{Degree(x) - 1}</tex>.

@@ Строка 103: / Строка 103: @@
 ||<tex>\mathrm{getMin}</tex>||<tex>O(1)</tex>
 |-align="center" bgcolor=#FFFFFF
-|<tex>\mathrm{meld}</tex>||<tex>O(1)</tex>
+|<tex>\mathrm{merge}</tex>||<tex>O(1)</tex>
 |-align="center" bgcolor=#FFFFFF
 |<tex>\mathrm{extractMin}</tex>||<tex>O(\log(n))</tex>
@@ Строка 180: / Строка 180: @@
 Стоимость <tex>O(1)</tex>.
-=== meld ===
+=== merge ===
 Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
 <code>
-  '''ThinHeap''' meld(H1: '''ThinHeap''', H2: '''ThinHeap'''):
+  '''ThinHeap''' merge(H1: '''ThinHeap''', H2: '''ThinHeap'''):
      '''if''' H1.first == ''null''
         '''return''' H2

@@ Строка 33: / Строка 33: @@
 <br clear="all" />
-= Тонкая куча =
+== Тонкая куча ==
 {{Определение
@@ Строка 57: / Строка 57: @@
 |about=О максимальном ранге узла
 |statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex>\varphi=\dfrac{1+\sqrt{5}}{2}</tex> {{---}} золотое сечение.
-|proof=Сначала покажем, что узел ранга <tex>k</tex> в тонком дереве имеет не менее <tex>F_k \geqslant \Phi^{k-1}</tex> потомков, включая самого себя, где <tex>F_k</tex> — <tex>k</tex>-е число Фибоначчи.
+|proof=Сначала покажем, что узел ранга <tex>k</tex> в тонком дереве имеет не менее <tex>F_k \geqslant \varphi^{k-1}</tex> потомков, включая самого себя, где <tex>F_k</tex> — <tex>k</tex>-е число Фибоначчи.
 Действительно, пусть <tex>T_k</tex> {{---}} минимально возможное число узлов, включая самого себя, в тонком дереве ранга <tex>k</tex>. По свойствам <tex>1</tex> и <tex>3</tex> тонкого дерева получаем следующие соотношения:
@@ Строка 63: / Строка 63: @@
 <tex>T_0=1,T_1=1,T_k \geqslant 1+\sum\limits_{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> [[Фибоначчиева куча#Лемма3|хорошо известно]].
+Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что <tex>T_k \geqslant F_k</tex> для любых <tex>k</tex>. Неравенство <tex>F_k \geqslant \varphi^{k-1}</tex> [[Фибоначчиева куча#Лемма3|хорошо известно]].
-Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> тонкого дерева в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\Phi}(n)+1</tex>.
+Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> тонкого дерева в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\varphi}(n)+1</tex>.
-Действительно, выберем в тонкой куче дерево максимального ранга. Пусть <tex>n^*</tex> {{---}} количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \Phi^{D(n)-1}</tex>.
+Действительно, выберем в тонкой куче дерево максимального ранга. Пусть <tex>n^*</tex> {{---}} количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \varphi^{D(n)-1}</tex>.
-Отсюда следует, что <tex>D(n)\leqslant\log_{\Phi}(n)+1</tex>.
+Отсюда следует, что <tex>D(n)\leqslant\log_{\varphi}(n)+1</tex>.
 }}

@@ Строка 56: / Строка 56: @@
 |id=max_rank_th
 |about=О максимальном ранге узла
-|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex dpi = "180">\Phi=\frac{1+\sqrt{5}}{2}</tex> {{---}} золотое сечение.
+|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex>\varphi=\dfrac{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>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_0=1,T_1=1,T_k \geqslant 1+\sum\limits_{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> [[Фибоначчиева куча#Лемма3|хорошо известно]].
@@ Строка 130: / Строка 130: @@
 <code>
-  '''bool''' isThin(x)
+  '''bool''' isThin(x: '''Node'''):
     '''if''' x.rank == 1
-       '''return''' x.child == null
+       '''return''' x.child == ''null''
     '''else'''
        '''return''' x.child.rank + 1 != x.rank
@@ Строка 141: / Строка 141: @@
 <code>
-  '''ThinHeap''' makeHeap()
+  '''ThinHeap''' makeHeap():
-     H.first = null
+     H.first = ''null''
-     H.last = null
+     H.last = ''null''
-     '''return''' H;
+     '''return''' H
 </code>
@@ Строка 154: / Строка 154: @@
 <code>
-  '''void''' insert(H, x)
+  '''void''' insert(H: '''ThinHeap''', x: '''Node'''):
-     '''if''' H.first == null
+     '''if''' H.first == ''null''
         H.first = x
         H.last = x
@@ Строка 174: / Строка 174: @@
 <code>
-  '''Node''' getMin(H)
+  '''Node''' getMin(H: '''ThinHeap'''):
      '''return''' H.first
 </code>
@@ Строка 185: / Строка 185: @@
 <code>
-  '''ThinHeap''' meld(H1, H2)
+  '''ThinHeap''' meld(H1: '''ThinHeap''', H2: '''ThinHeap'''):
-     '''if''' H1.first == null
+     '''if''' H1.first == ''null''
         '''return''' H2
      '''else'''
-        '''if''' H2.first == null
+        '''if''' H2.first == ''null''
            '''return''' H1
         '''else'''
@@ Строка 218: / Строка 218: @@
 <code>
-  '''Node''' extractMin(H)
+  '''Node''' extractMin(H: '''ThinHeap'''):
      <span style="color:#008000">// Удаляем минимальный корень из корневого списка</span>
      tmp = H.first
      H.first = H.first.right
-     '''if''' H.first == null
+     '''if''' H.first == ''null''
-        H.last = null
+        H.last = ''null''
      <span style="color:#008000">// Снимаем тонкость с его детей и добавляем их в корневой список</span>
      x = tmp.first.child
-     '''while''' x != null
+     '''while''' x != ''null''
         '''if''' isThin(x)
            x.rank = x.rank - 1
-        x.left = null
+        x.left = ''null''
         next = x.right
         insert(H, x)
@@ Строка 236: / Строка 236: @@
      max = -1
      x = H.first
-     '''while''' x != null
+     '''while''' x != ''null''
-        '''while''' aux[x.rank] != null
+        '''while''' aux[x.rank] != ''null''
            next = x.right
            '''if''' aux[x.rank].key < x.key
@@ Строка 245: / Строка 245: @@
            aux[x.rank].left = x
            x.child = aux[x.rank]
-           aux[x.rank] = null
+           aux[x.rank] = ''null''
            x.rank = x.rank + 1
         aux[x.rank] = x
@@ Строка 306: / Строка 306: @@
 <code>
-  '''void''' delete(H, x)
+  '''void''' delete(H: '''ThinHeap''', x: '''Node'''):
      decreaseKey(H, x, <tex>-\infty</tex>)
      extractMin()
@@ Строка 319: / Строка 319: @@
 [[Категория: Дискретная математика и алгоритмы]]
 [[Категория: Приоритетные очереди]]

@@ Строка 294: / Строка 294: @@
 Пусть узел <tex>y</tex> — это узел локализации родительского нарушения, а узел <tex>z</tex> — родитель узла <tex>y</tex>.
 Переместим все поддерево с корнем в <tex>y</tex> в корневой список и уменьшим ранг <tex>y</tex>.
-* Узел <tex>z</tex> не был тонким, пометим его как тонкий, тогда дерево станет корректным.
+# Если узел <tex>y</tex> не был старшим братом, то переходим к его левому брату, нарушение станет братским.
-* Узел <tex>z</tex> был тонким, тогда <tex>z</tex> {{---}} новый узел локализации родительского нарушения, переходим к нему.
+# Если узел <tex>y</tex> был старшим братом, то смотрим на родителя
 Продолжая эту процедуру, мы или остановимся, или дойдем до корня дерева, тогда достаточно сделать ранг корня на 1 больше ранга его самого левого сына.
-Каждый промежуточный шаг рекурсии уменьшает количество тонких узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость <tex>O(1)</tex>.
+Каждый промежуточный шаг рекурсии уменьшает количество тонких узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость <tex>O(1)</tex>. Также заметим, что мы всегда перемещаемся либо влево, либо вверх по нашему дереву, так что суммарно в худшем случае мы выполним <tex>O(\log(n))</tex> операций, а не <tex>O(n)</tex>, как в случае фибоначчиевой кучи.
 Стоимость <tex>O(1)</tex>.

@@ Строка 24: / Строка 24: @@
 |id=about_thin_tree
 |statement=Тонкое дерево обладает следующими свойствами:
-# Для любого узла <tex>x</tex> либо <tex>Degree(x)=Rank(x)</tex>, в этом случае говорим, что узел <tex>x</tex> не помечен (полон); либо <tex>Degree(x)=Rank(x)-1</tex>, в этом случае говорим, что узел <tex>x</tex> помечен (не полон).
+# Для любого узла <tex>x</tex> либо <tex>Degree(x)=Rank(x)</tex>, в этом случае говорим, что узел <tex>x</tex> не тонкий (полон); либо <tex>Degree(x)=Rank(x)-1</tex>, в этом случае говорим, что узел <tex>x</tex> тонкий (не полон).
-# Корень не помечен (полон).
+# Корень не тонкий (полон).
 # Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>0,1,2,...,Degree(x)-1</tex>.
-# Узел <tex>x</tex> помечен тогда и только тогда, когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1, и он не имеет детей.
+# Узел <tex>x</tex> тонкий тогда и только тогда, когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1, и он не имеет детей.
 }}
-[[Файл:Thin_trees.png|200x200px|слева|frame|Из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] ранга 3 получены два тонких дерева. Числа обозначают ранги узлов, закрашенные вершины являются помеченными (не имеют самого левого сына)]]
+[[Файл:Thin_trees.png|200x200px|слева|frame|Из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] ранга 3 получены два тонких дерева. Числа обозначают ранги узлов, закрашенные вершины являются тонкими (не имеют самого левого сына)]]
 <br clear="all" />
@@ Строка 85: / Строка 85: @@
 *<tex>rank</tex> {{---}} ранг узла.
-Для ускорения проверки на тонкость (''thinness'') можно отдельно хранить помеченность вершины.
+Для ускорения проверки на тонкость (''thinness'') можно отдельно хранить тонкость вершины.
 Также в вершине можно хранить любую дополнительную информацию.
@@ Строка 121: / Строка 121: @@
 Для [[Амортизационный анализ|амортизационного анализа]] операций применим [[Амортизационный анализ#Метод потенциалов|метод потенциалов]].
-Пусть функция потенциала определена как <tex>\Phi = n + 2 \cdot m</tex> где <tex>n</tex> {{---}} это количество тонких деревьев в куче, а <tex>m</tex> {{---}} это количество помеченных вершин.
+Пусть функция потенциала определена как <tex>\Phi = n + 2 \cdot m</tex> где <tex>n</tex> {{---}} это количество тонких деревьев в куче, а <tex>m</tex> {{---}} это количество тонких вершин.
 {{Утверждение
@@ Строка 132: / Строка 132: @@
 Пусть <tex>Node</tex> {{---}} узел тонкого дерева, а <tex>ThinHeap</tex> {{---}} тонкая куча, причем <tex>ThinHeap</tex> содержит ссылки на первый и последний корень <tex>first</tex> и <tex>last</tex> соответственно.
-Также введем вспомогательную функцию проверки узла на помеченность, для этого воспользуемся тем, что у левого сына узла <tex>x</tex> ранг равен <tex>Degree(x) - 1</tex>.
+Также введем вспомогательную функцию проверки узла на тонкость, для этого воспользуемся тем, что у левого сына узла <tex>x</tex> ранг равен <tex>Degree(x) - 1</tex>.
 <code>
-  bool isMarked(x)
+  bool isThin(x)
     if x.rank == 1
        return x.child == null
@@ Строка 212: / Строка 212: @@
 Чтобы извлечь минимальный элемент из тонкой кучи нужно:
 # Удалить корень с минимальным ключом из корневого списка.
-# Уменьшить ранг для всех его помеченных детей.
+# Уменьшить ранг для всех его тонких детей.
 # Cлить детей с корневым списком.
 # Объединять, пока возможно, тонкие деревья одного ранга.
@@ Строка 228: / Строка 228: @@
      H.first = H.first.right
      if H.first == null H.last = null
-     // Снимаем пометки с его детей и добавляем их в корневой список
+     // Снимаем тонкость с его детей и добавляем их в корневой список
      x = tmp.first.child
      while x != null
-        if isMarked(x)
+        if isThin(x)
            x.rank = x.rank - 1
         x.left = null
@@ Строка 284: / Строка 284: @@
 # Ранг узла <tex>y</tex> на три больше, чем ранг его самого левого сына.
 # Ранг узла <tex>y</tex> равен двум, и он не имеет детей.
-# Узел <tex>y</tex> есть помеченный корень дерева.
+# Узел <tex>y</tex> есть тонкий корень дерева.
 Пусть узел <tex>y</tex> — это узел локализации братского нарушения.
-* Узел <tex>y</tex> не помечен, тогда помещаем поддерево с корнем в самом левом сыне узла <tex>y</tex> на место пропущенного в братском списке. Узел <tex>y</tex> становится помеченным, дерево становится корректным, процедура исправления завершается.
+* Узел <tex>y</tex> не тонкий, тогда помещаем поддерево с корнем в самом левом сыне узла <tex>y</tex> на место пропущенного в братском списке. Узел <tex>y</tex> становится тонким, дерево становится корректным, процедура исправления завершается.
-* Узел <tex>y</tex> помечен, тогда уменьшаем ранг узла <tex>y</tex> на единицу. Теперь узлом локализации нарушения будет либо левый брат узла <tex>y</tex>, либо его родитель, тогда нарушение станет родительским.
+* Узел <tex>y</tex> тонкий, тогда уменьшаем ранг узла <tex>y</tex> на единицу. Теперь узлом локализации нарушения будет либо левый брат узла <tex>y</tex>, либо его родитель, тогда нарушение станет родительским.
 С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.
@@ Строка 295: / Строка 295: @@
 Переместим все поддерево с корнем в <tex>y</tex> в корневой список и уменьшим ранг <tex>y</tex>.
-* Узел <tex>z</tex> не был помечен, пометим его, тогда дерево станет корректным.
+* Узел <tex>z</tex> не был тонким, пометим его как тонкий, тогда дерево станет корректным.
-* Узел <tex>z</tex> был помечен, тогда <tex>z</tex> {{---}} новый узел локализации родительского нарушения, переходим к нему.
+* Узел <tex>z</tex> был тонким, тогда <tex>z</tex> {{---}} новый узел локализации родительского нарушения, переходим к нему.
 Продолжая эту процедуру, мы или остановимся, или дойдем до корня дерева, тогда достаточно сделать ранг корня на 1 больше ранга его самого левого сына.
-Каждый промежуточный шаг рекурсии уменьшает количество помеченных узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость <tex>O(1)</tex>.
+Каждый промежуточный шаг рекурсии уменьшает количество тонких узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость <tex>O(1)</tex>.
 Стоимость <tex>O(1)</tex>.