|style="background-color:#FFF;padding:2px 10px"| ''Здесь мы снова обратились к правому поддереву. Рассуждаем аналогично.''
|}
Разберём алгоритм на примере последовательности для приведённого выше дерева. Она выглядит так: ''8 2 1 4 3 5''. Сначала в корень записывается ''8''. Затем его левым сыном становится вершина с номером ''2'', а её левым сыном — ''1''. Следующее значение — ''4'' — уже нарушает убывающую подпоследовательность. Подберём для него вершину, где лежит значение, меньшее его, причём такая вершина максимальна. В противном случае он будет превосходить и прародителя, находясь в его левом поддереве, а это противоречит определению дерева поиска. Очевидно, что нельзя также подвесить его и к вершине, которая хранить большее значение. Для вершины ''4'' родителем будет узел с числом ''2''. Сделаем его правым сыном рассматриваемую вершину. Затем снова дадим левых потомков последней добавленной вершине, опять же, пока не найдём ключ, нарушающий порядок убывания. В нашем случае в дерево дописывается ''3''. Для следующего значения снова ищем родителя, для которого он станет правым сыном. Это значение равно ''4''. Добавляем ''5'' как правого сына для вершины ''4''. Вершины закончились, мы построили дерево.
==См. также==
