Изменения

Разберём алгоритм на примере последовательности <tex>\mathtt{8}</tex> <tex>\mathtt{2}</tex> <tex>\mathtt{1}</tex> <tex>\mathtt{4}</tex> <tex>\mathtt{3}</tex> <tex>\mathtt{5}</tex>.

{| style="background-color:#CCC;margin:0.5px"

!style="background-color:#EEE"| Состояние

| 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"| Для вершины, нарушившей убывающую последовательность, ищем максимальное значение, меньшее его. В данном случае оно равно <tex>\mathtt{2}</tex>. Затем добавляем вершину.

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

|style="background-color:#FFF;padding:2px 10px"| ''Зайдя в правое поддерево, процедура обхода снова до упора начала двигаться влево, поэтому действуем аналогичным образом.''

|-

|style="background-color:#FFF;padding:2px 10px"| Для этой вершины ищем максимальное значение, меньшее его. Затем добавляем вершину.

|style="background-color:#FFF;padding:2px 10px"| ''Здесь процедура снова обратилась к правому поддереву. Рассуждения аналогичны. Ключ родителя этой вершины равен <tex>\mathtt{4}</tex>.''