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