243
правки
Изменения
→Восстановление дерева по результату обхода preorderTraversal
| style="background-color:#FFF;padding:2px 10px"| 8 '''2''' <span style="color:red">'''1'''</span> 4 3 5
|-
|style="background-color:#FFF;padding:2px 10px"| 8 '''2 ''' 1 <span style="color:red">'''4'''</span> 3 5
|style="background-color:#FFF;padding:2px 10px"| Для первой вершины, нарушившей убывающую последовательность, ищем максимальное значение, меньшее его.
|style="background-color:#FFF;padding:2px 10px"| ''На моменте вывода следующего номера процедура обратилась уже к какому-то из правых поддеревьев, так как влево идти уже некуда. Значит, нам необходимо найти узел, для которого данная вершина являлась бы правым сыном. Очевидно, что в её родителе не может лежать значение, которое превосходит число, находящееся в ней. Но эту вершину нельзя подвесить и к меньшим, иначе нашёлся бы более старший предок, также хранящий какое-то значение, которое меньше, чем в исследуемой. Для этого предка вершина бы попала в левое поддерево. И тогда возникает противоречие с определением дерева поиска. Отсюда следует, что родитель определяется единственным образом {{- --}} он хранит максимум среди ключей, не превосходящих значения в подвешиваемой вершине, что и требовалось доказать.''
|-
|style="background-color:#FFF;padding:2px 10px"| 8 2 1 <span style="color:red">'''4 3'''</span> 5
