Изменения

Перейти к: навигация, поиск

Дерево поиска, наивная реализация

400 байт добавлено, 21:40, 15 января 2017
Восстановление дерева по результату обхода preorderTraversal
[[Файл:BST_from_seq.gif|right|thumb|260px|Восстановление дерева поиска по последовательности ключей]]
Как мы помним, процедура <tex>\mathrm{preorderTraversal}</tex> выводит значения в узлах поддерева следующим образом: сначала идёт до упора влево, затем на каком-то моменте делает шаг вправо и снова движется влево. Это продолжается до тех пор, пока не будут выведены все вершины. Полученная последовательность позволит нам однозначно определить расположение всех узлов поддерева. Первая вершина всегда будет в корне. Затем, пока не будут использованы все значения, будем последовательно подвешивать левых сыновей к последней добавленной вершине, пока не найдём номер, нарушающий убывающую последовательность, а для каждого такого номера будем искать вершину без правого потомка, хранящую наибольшее значение, не превосходящее того, которое хотим поставить, и подвешиваем к ней элемент с таким номером в качестве правого сына.  '''func''' seq2bst(A[n]: '''T''') v = root <font color="green">// root {{Когда мы, желая найти такую вершину, встречаем какую---}} корень дерева поисканибудь другую, уже имеющую правого сына, проходим по ветке вправо.</font> vМы имеем на это право, так как если такая вершина стоит, то процедура обхода в ней уже побывала и поворачивала вправо, поэтому спускаться в другую сторону смысла не имеет.key = A[0] i = 1 '''while''' A[i] < A[i-1] <font color="green">// Пока идёт убывающая последовательностьВершину с максимальным ключом, с которой будем начинать поиск, будем добавлять левых сыновейзапоминать. Она будет обновляться каждый раз, когда появляется новый максимум.</font> 3 4 5
Разберём алгоритм на примере последовательности <tex>\mathtt{8}</tex> <tex>\mathtt{2}</tex> <tex>\mathtt{1}</tex> <tex>\mathtt{4}</tex> <tex>\mathtt{3}</tex> <tex>\mathtt{5}</tex>.
243
правки

Навигация