243
правки
Изменения
→Поиск максимального поддерева, являющегося BST, в заданном двоичном дереве
[[Файл:BST_from_seq.gif|right|thumb|260px|Восстановление дерева поиска по последовательности ключей]]
Заметим, что <tex>\mathtt{dfsPrint}</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево и так до тех пор, пока не будет выведено <tex>\mathtt{maxdp}</tex> вершин. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына.
Разберём алгоритм на примере последовательности для приведённого выше дерева. Она выглядит так: ''8 2 1 4 3 5''. Сначала в корень записывается ''8''. Затем его левым сыном становится вершина с номером ''2'', а её левым сыном - ''1''. Следующее значение - ''4'' - уже нарушает убывающую подпоследовательность. Подберём для него вершину, где лежит значение, меньшее его, причём такая вершина максимальна (в противном случае он будет превосходить и прародителя, находясь в его левом поддереве, а это противоречит определению дерева поиска). Это узел с числом ''2''. Сделаем его правым сыном рассматриваемую вершину. Затем снова дадим левых потомков последней добавленной вершине, опять же, пока не найдём ключ, нарушающий порядок убывания. В нашем случае в дерево дописывается ''3''. Для следующего значения снова ищем родителя, для которого он станет правым сыном. Это значение равно ''4''. Добавляем ''5'' как правого сына для вершины ''4''. Итак, мы построили дерево.
