Поиск в бинарном дереве

Двоичное дерево поиска - это двоичное дерево, для кот выполняются следующие дополнительные условия.

1) Оба поддерева - левое и правое, являются двоичными деревьями поиска.

2) У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение узла X.

3)У всех узлов правого поддерева произвольного узла X значения ключей данных больше, чем значение X.

еще непрос-мотренной вершине, если непросмотр смеж верш нет, то происх возврат от текущей вершины назад к ранее пройденной. Обход в ширину - метод обхода гр: в начале рассматр все вершины смежные с текущей, затем смежные с верш получен-ными на пред шаге.

Для обхода в глубину использ-ся – стек LIFO(линейн.список, в кот. все включ-я и исключ-я произво-ся на одном конце списка – вершине стека)

Для обхода в ширину использ-ся – очередь FIFO(линейн.список,в кот. все включ-я произв-ся в одн. конце списка, а исключ-я в др.) Обходы бинарных деревьев Прямой обход: Попасть в корень, Обойти левое поддерево, Обойти правое поддерево. Обратный обх: Об л подде, Об п поддер, Поп в кор Симметричный обх: Об л поддер, Поп в кор, Об пр поддерево.

Кратчайший путь- для двух фиксиров верш путь наим длины, соедин-й указ верш.

Задача поиска кратчайших путей на графе:

Заданы n вер графа и целые длины дуг м/у ними. Найти наим возможную длину пути из v₁ в v_k, и из v1 в любую др?

Если веса дуг неотриц, то м использ алгоритм Дейкстры, если есть отриц веса, но нет циклов отриц веса, то м исп алгоритм Флойда (если есть такие циклы то оптим реш не ∃).

Алгоритм Дейкстры:

Дан взвешенный граф G(V, U) без рёбер и дуг отриц веса. Найти кратч.путь из вершины «a» до всех ост-х вершин графа.

∀ вершине из V сопоставим метку - мин. известное расс-тояние от этой вершины до a. На ∀ шаге «посещ-ся» 1 верш и пытаемся уменьшать метки. Работа алг заверш, когда все верш посещены.

Инициализация. Метка верш M(a) = 0, метки остальных вершин = ∞ T - непосещ вершины =V.

Шаг алгоритма. Если T-пусто, конец алгоритма. Иначе выбир u T, т.ч. M(u)=min{M(v)} v T.

Для ∀ смеж с u вер рассчит-м

M’(vi)=M(u)+ e, e ={vi,u}(вес ребра). Если M’(v_i)<M(v’) то M(v’) = M’(v_i). Рассмотрев всех соседей: T=T\u, и повторим шаг. Алгоритм Флойда: Дано: непyст взвеш гpаф G=(V, E) с пpоизв-ми весами ребер. Найти: кpатч-й пyть м/у всеми парами вершин гр, если в гр нет циклов отриц сумм-й длины.

Инициализация:

1. Постр матр D⁰ размерности |V| x |V|, эл-ты кот.:

D_ii⁰= 0; D_ij⁰= Weight(v_i, v_j), где i≠j, если в графе есть ребро (vi, vj); D_ij⁰= бескон-ть , где i≠j, если нет ребра (v_i, v_j).

2. m:=0.

Осн часть: 1. Построим матр D^m+1 по D^m, вычисляя ее элем:

D_ij^m+1=min{D_ij^m, D_i(m+1)^m + D_(m+1)j^m}, где i≠j; D_ii^m+1=0.

Если D_im^m + D_mi^m < 0 для какого-то i, то в графе ∃ цикл (отриц длины, проход ч/з верш vi; => ВЫХОД.

2. m:=m+1; если m<|V|, то шаг (1), иначе эл-ты посл-й матрицы D|V| равны длинам кратч путей м/у соотв-ми вершинами; КОНЕЦ

- если таких подзадач неск-ко, то из них выбир подз самого низкого уровня, если и их неск., то выбир. случайно.

На ∀ шаге метода элем разбиения подверг-ся прове-рке для выяснения, содержит данное подмн-во оптимал-е реш-е или нет. Проверка осущ-ся путём вычисл-я оценки снизу для цел. функ. на данном подмн-ве. Если оценка снизу не < рекорда, то подмн-во м. б. отброшено. Проверяемое подмн-во м. б. отброшено, когда в нем удается найти наилучшее реш. Если зн-е цел. функции на найденном реш-и < рекорда, то смена рекорда. Если удается отбросить все эл-ты разбиения, то рекорд — оптимальн. реш. з-чи. Иначе: из неотброш-х подмн-в выбир-ся с наимен. зн-м нижней оценки, и оно подверг-ся разбиению. Для нов. подмн-в вновь проверка и т.д.

Динам-е программ-е (ДП) - это вычислит метод для эф-фективного реш-я задач с пересекающимися подз-ми.

Идея ДП состоит в разбиении з-чи на неск. (простых) подз-ч, решении кажд. из них, а затем вычислении исх-го резул-та. Для реш-я подз-ч этот же алгоритм примен-ся рекурсивно. Для кажд. подз запомин-ся вычисл-й ответ, и если на каком-то шаге встретилась подз-ча 2-й раз, то вычисл-я для нее не произв-ся. За счет больш. кол-ва пересек-ся подзадач это значит-но уменьшает время работы.

Оптимальность для подз-ч. З-ча обладает св-м оптим-ти для подз-ч, если оптим-е реш-е з-чи содержит оптим-е реш-я её подз-ч. Для такой з-чи использ-е ДП м. б. полезным для реш.

З-ча обладает этим св-м, если улучшая реш-е подз-чи, мы улучшим и реш-е исх-й з-чи (из оптим-го реш-я подз-ч должно получаться оптим-е реш-е исх-й з-чи). Как только св-во оптим-ти для подз-ч установлено, становится ясно, с каким именно множ подз-ч будет иметь дело алгоритм.

Если мн-во подз-ч имеет простую структуру и есть некот. парам. p, кот. уменьш-ся при разбиении на подз-чи, то м. применять ДП, не используя рекурсию: для этого в начале вычисл. ответ для всех подз-ч с наим. p, затем для всех подз-ч со 2-м по вел-не p и.т.д. пока не вычислим ответ для исх. з-чи.

Перекрывающиеся подз-чи - 2 св-во з-ч существенное при использ ДП,- небольшое число различных подз-ч.

Пересек-ся подз-и в ДП – подз-чи, кот. используются для реш-я некот. кол-ва з-ч (не одной) большего размера (у подз-ч есть общие «подподз-чи»). (пример: вычисл-е послед-ти Фибоначчи, F3 = F2 + F1 и F4 = F3 + F2 ) Простой рекурс-й подход будет расходовать время на вычис-е реш-е для з-ч, которые он уже решал. Для избания такого - сохраняють реш-я подз-ч.

Свойства задач, к кот. примимо ДП:

перекрывающиеся подзадачи;

оптимальность для подз-ч;

возможность запоминания реш-ия часто встреч-я подз-ч.

Эти два элемента меняются местами, и процесс просмо-тра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В рез-те массив окажется разбитым на две части - левую, в кот значения ключей будут меньше x, и правую со значениями ключей, большими x. Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент. O(nlog n) – O(n²)

пирамидальная сортировка: его идея состоит в том, что массив a[1], a[2], ..., a[n] преобразуется в пирамиду, обладающую тем свойством, что для каждого a[i] выполняются условия a[i] <= a[2i] и a[i] <= a[2i+1]. Затем пирамида используется для сортировки: элем из корня удаляются по одному за раз и дерево перестраивается. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент.

Сортировка слиянием Фон-Неймана:

Пусть даны 2 упорядоченных массива:

,алгоритм слияния заключ в получении 1 упорядоченного массива

Пусть i=1 и j = 1.Сравниваются элемент xi и yj. Если xi > yj, то yj заносится в z и j=j+1? Иначе xi заносится в z и i=i+1. Алгоритм заканчивает работу, когда будет достигнута граница одного из массивов. Оставшаяся часть записывается в хвост z.

Поиск проходит последоват вглубь, на каждом этапе значение сравнивается с вершиной, если равно, то нашли, если меньше то отправляемся в левое поддерево, иаче в правое.

Балансировка дерева: Всегда желательно, чтобы все пути в дереве от корня до листьев имели примерно одинаковую длину, т.е. чтобы глубина и левого, и правого под-деревьев была примерно одинакова в любом узле. Иначе производительность снижается (в худшем случае до последовательного поиска как в связном списке).