Добавление элемента

Пусть дан пирамидально-упорядоченный массив A_i, (i=1,…,N). Требуется добавить к нему еще один элемент A_i+1 и переупорядочить массив. Для этого введем текущий номер элемента в массиве k. В начальный момент положим k= N+1.

Свойство пирамидально-упорядоченности выполняется для всех соответствующих пар элементов, кроме, быть может, пары (k,k/2). Если для этой пары свойство A_[k/2] ³ A_k выполняется, то массив пирамидально упорядочен и ничего больше делать не надо. Иначе поменяем местами пару элементов с индексами k и k/2. При этом элемент с индексом k/2 не уменьшится, поэтому поддерево, с него начинающееся, но идущее по другой ветке, чем (k,k/2) останется пирамидально-упорядоченным (т.е., например для четного k, останется верным A_[k/2] ³ A_k+1).

Перед обменом местами элементов с индексами (k,k/2), элемент A_[k/2] был не меньше всех элементов в поддереве, начинающегося с A_[k/2], кроме, быть может, A_k. Поэтому, после обмена местами элементов с индексами (k,k/2), элемент A_k будет не меньше всех элементов в поддереве, начинающегося с A_k. Осталось присвоить k=[k/2], и выполнить те же самые действия для нового k.

Таким образом, мы произведем не более [log N]+1 обменов местами соседних элементов, из чего следует, что процедура добавления элемента в пирамиду может быть произведена за время O(log N).

Корректировка положения элемента

Пусть дан пирамидально-упорядоченный массив A_i, (i=1,…,N). Для текущего элемента в массиве с номером k изменим значение элемента A_k. Требуется переупорядочить массив.

Если A_k³ A_2k и A_k³ A_2k+1, то задача полностью сводится к предыдущей.

Пусть, для определенности, A_k< A_2k. Но тогда A_[k/2] ³ A_k (т.к. A_[k/2] ³ A_2k> A_k), из чего получаем, что все элементы из поддерева, начинающегося с k- го элемента массива не превосходят A_[k/2]. В этом случае возможно применить процедуру Heapify(A,k,N). Время ее работы O(log N).

¢

Лекция 9

Бинарные деревья поиска

Бинарными деревьями называют деревья, в которых, как правило, задан корневой элемент или корень и для каждой вершины существует не более двух потомков. Например, для задания одной вершины бинарного дерева целых чисел в языке С можно использовать следующую структуру

Typedef struct STree_

{

Int value;

struct STree_ *prev;

struct STree_ *left, *right;

} STree;

здесь указатель prev указывает на родительский элемент данной вершины, а left и right – на двух потомков, которых традиционно называют левым и правым. Величина value называется ключом вершины.

Бинарное дерево называется деревом поиска, если для любой вершины дерева a ключи всех вершин в правом поддереве больше или равны ключа a, а в левом – меньше. Неравенства можно заменить на строгие, если известно, что в дереве нет равных элементов.

Далее мы постараемся придерживать синтаксиса языка С, т.е., как правило, мы будем использовать в качестве вершины дерева a переменную типа

STree *a;

Отсутствие потомка обозначается нулевым значением соответствующего указателя.

Часто, если это не будет приводить к двусмысленностям, под сравнением элементов мы будем подразумевать сравнение соответствующих ключей.

Ветвью дерева называется последовательность вершин дерева, каждый последующий элемент в которой является потомком предыдущего.

Длиной ветви дерева называется количество элементов в ветви.

Высотой дерева называется максимальная длина всех ветвей дерева.

Основные операции, которые можно совершать с бинарными деревьями:

· поиск элемента в дереве (т.е. элемента с ключом, равным заданному)

· добавление элемента в дерево

· удаление элемента из дерева

· поиск минимального и максимального элемента в дереве

· если рассмотреть дерево поиска, как упорядоченную по возрастанию последовательность элементов, то: для текущего элемента поиск следующего/предыдущего

· для данной вершины дерева v разбиение дерева поиска T на два дерева поиска T₁ и T₂ таких, что все элементы в T₁ меньше или равны v, и все элементы в T₂ больше или равны v

· для двух деревьев поиска T₁ и T₂ таких, что все элементы в T₁ меньше или равнывсех элементов в T₂ (будем далее для таких деревьев говорить, что дерево T₁ меньше или равно дерева T₂: T₁ £ T₂): слияние деревьев в одно дерево поиска T

Покажем, что все эти операции можно совершить за время O(h), где h – высота рассматриваемого дерева.

---

Дата добавления: 2015-10-30