21 (1106258)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 211Красно-черные деревьяКрасно-черное дерево – двоичное дерево поиска, каждаявершина которого окрашена либо в красный, либо в черный цветПоля – цвет, дети, родителиtypedef struct rbtree {int key;char color;struct rbtree *left, *right, *parent;} rbtree, *prbtree;Будем считать, что если left или right равны NULL, то это“указатели” на фиктивные листы, т.е. все вершины внутренние2Красно-черные деревьяСвойства красно-черных деревьев:1.2.3.4.Каждая вершина либо красная, либо черная.Каждый лист (фиктивный) – черный.Если вершина красная, то оба ее сына – черные.Все пути, идущие от корня к любому листу, содержат одинаковоеколичество черных вершин264117142116107123nilnilnilnil15nilnil19nilnilnil2320nil4730nilnil28nilnil38nilnilnil35nilnil39nilnil3Красно-черные деревьяОбозначим bh(x) – "черную" высоту поддерева с корнем х (самувершину в число не включаем), т.е.

количество черных вершин отх до листаЧерная высота дерева – черная высота его корняЛемма: Красно-черное дерево с n внутренними вершинами (безфиктивных листьев) имеет высоту не более 2log2(n+1).(1) Покажем вначале, что поддерево х содержит не меньше2bh(x) – 1 внутренних вершин(1a) Индукция. Для листьев bh = 0, т.е. 2bh(x) – 1 = 20– 1 = 0.(1б) Пусть теперь х – не лист и имеет черную высоту k.Тогда каждый сын х имеет черную высоту не меньше k – 1(красный сын имеет высоту k, черный – k – 1).(1в) По предположению индукции каждый сын имеет не меньше2k-1 – 1 вершин. Поэтому поддерево х имеет не меньше 2k-1 – 1 +2k-1 – 1 + 1 = 2k – 1.4Красно-черные деревьяЛемма: Красно-черное дерево с n внутренними вершинами (безфиктивных листьев) имеет высоту не более 2log2(n+1).(2) Теперь пусть высота дерева равна h.(2а) По свойству 3 черные вершины составляют не меньшеполовины всех вершин на пути от корня к листу. Поэтомучерная высота дерева bh не меньше h/2.(2б) Тогда n ≥ 2h/2 – 1 и h ≤ 2log2(n + 1).

Лемма доказана.Следовательно, поиск по красно-черному дереву имеетсложность O (log2n).5Красно-черные деревья: вставка вершиныСначала мы используем обычную процедуру занесения новойвершины в двоичное дерево поиска:красим новую вершину в красный цвет.Если дерево было пустым, то красим новый корень в черныйцветСвойство 4 при вставке изначально не нарушено, т.к. новаявершина краснаяЕсли родитель новой вершины черный (новая – красная), тосвойство 3 также не нарушеноИначе (родитель красный) свойство 3 нарушено6Красно-черные деревья: вставка вершиныСлучай 1: “дядя” (второй сын родителя родителя текущейвершины) тоже красный (как текущая вершина и родитель)Возможно выполнить перекраску:родителя и дядю (вершины A и D) – в черный цвет,деда – (вершина C) – в красный цветСвойство 4 не нарушено (черные высоты поддеревьевсовпадают)СперекраскаAαδγDADBβСεαδBβεγ7Красно-черные деревья: вставка вершиныСлучай 2: “дядя” (второй сын родителя родителя текущейвершины) черныйШаг 1: Необходимо выполнить левый поворот родителятекущей вершины (вершины A)ССЛевыйповоротδAαBβγAγδBαβ8Красно-черные деревья: вставка вершиныСлучай 2: “дядя” (второй сын родителя родителя текущейвершины) черныйШаг 2: Необходимо выполнить правый поворотвершины C, после чего …Шаг 3: … перекрасить вершины B и CВсе поддеревья имеют черные корни и одинаковуючерную высоту, поэтому свойства 3 и 4 верныПравыйповоротCδBγAαBAαCβγδβ9Пирамидальная сортировка (heapsort)Можно использовать дерево поиска для сортировкиНапример, последовательный поиск минимального элемента,удаление его и вставка в отсортированный массивНедостатки:Сложность такого алгоритма есть O (nh), где h – высотадереваТребуется дополнительная память для дереваТребуется построить само дерево (с минимальной высотой)Можно ли построить похожий алгоритм без требований кдополнительной памяти?10Пирамидальная сортировка: пирамида (двоичная куча)Рассматриваем массив a как двоичное дерево:Элемент a[i] является узлом дереваЭлемент a[i/2] является родителем узла a[i]Элементы a[2*i] и a[2*i+1] являются детьми узла a[i]Для всех элементов пирамиды выполняется соотношение(основное свойство кучи):a[i] >= a[2*i] и a[i] >= a[2*i+1]илиa[i/2] <= a[i]Сравнение может быть как в большую, так и в меньшую сторонуЗамечание.

Определение предполагает нумерацию элементовмассива от 1 до nДля нумерации от 0 до n-1:a[i] >= a[2*i+1] и a[i] >= a[2*i+2]11Пирамидальная сортировка: пирамида (двоичная куча)Для всех элементов пирамиды выполняется соотношение:a[i] >= a[2*i] и a[i] >= a[2*i+1]илиa[i/2] <= a[i]Сравнение может быть как в большую, так и в меньшую сторону12Пирамидальная сортировка: просеивание элементаКак добавить элемент в уже существующуюпирамиду?Алгоритм:Поместим новый элемент в корень пирамидыЕсли этот элемент меньше одного из сыновей:Элемент меньше наибольшего сынаОбменяем элемент с наибольшим сыном(это позволит сохранить свойство пирамидыдля другого сына)Повторим процедуру для обмененного сына13Пирамидальная сортировка: просеивание элементаstatic void sift (int *a, int l, int r) {int i, j, x;i = l; j = 2*l; x = a[l];/* j указывает на наибольшего сына */if (j < r && a[j] < a[j + 1])j++;/* i указывает на отца */while (j <= r && x < a[j]) {/* обмен с наибольшим сыном: a[i] == x */a[i] = a[j]; a[j] = x;/* продвижение индексов к следующему сыну */i = j; j = 2*j;/* выбор наибольшего сына */if (j < r && a[j] < a[j + 1])j++;}}14Пирамидальная сортировка: просеивание элемента/* l, r - от 0 до n-1 */static void sift (int *a, int l, int r) {int i, j, x;/* Теперь l, r, i, j от 1 до n, а индексы массивауменьшаются на 1 при доступе */l++, r++;i = l; j = 2*l; x = a[l-1];/* j указывает на наибольшего сына */if (j < r && a[j-1] < a[j])j++;/* i указывает на отца */while (j <= r && x < a[j-1]) {/* обмен с наибольшим сыном: a[i-1] == x */a[i-1] = a[j-1]; a[j-1] = x;/* продвижение индексов к следующему сыну */i = j; j = 2*j;/* выбор наибольшего сына */if (j < r && a[j-1] < a[j])j++;}}15Пирамидальная сортировка: просеивание элементаВызов sift (2, 10) для левого поддерева16Пирамидальная сортировка: просеивание элементаВызов sift (2, 10) для левого поддерева17Пирамидальная сортировка: просеивание элементаВызов sift (2, 10) для левого поддерева18Пирамидальная сортировка: алгоритм(1)(2)Построим пирамиду по сортируемому массивуЭлементы массива от n/2 до n являются листьямидерева, а следовательно, правильными пирамидами изодного элементаДля остальных элементов в порядке уменьшения индексапросеиваем их через правую часть массиваОтсортируем массив по пирамидеПервый элемент массива максимален (корень пирамиды)Поменяем первый элемент с последним(таким образом, последний элемент отсортирован)Теперь для первого элемента свойство кучи нарушено:повторим просеивание первого элемента в пирамидеот первого до предпоследнегоСнова поменяем первый и предпоследний элемент и т.п.19Пирамидальная сортировка: программаvoid heapsort (int *a, int n) {int i, x;/* Построим пирамиду по сортируемому массиву *//* Элементы нумеруются с 0 -> идем от n/2-1 */for (i = n/2 - 1; i >= 0; i--)sift (a, i, n - 1);for (i = n – 1; i > 0; i--) {/* Текущий максимальный элемент в конец */x = a[0]; a[0] = a[i]; a[i] = x;/* Восстановим пирамиду в оставшемся массиве */sift (a, 0, i – 1);}}20Пирамидальная сортировка: пример21Пирамидальная сортировка: пример22Пирамидальная сортировка: пример23Пирамидальная сортировка: пример24Пирамидальная сортировка: пример25Пирамидальная сортировка: сложность алгоритма(1)Построим пирамиду по сортируемому массиву(2)Элементы массива от n/2 до n являются листьямидерева, а следовательно, правильными пирамидами из 1 элементаДля остальных элементов в порядке уменьшения индексапросеиваем их через правую часть массиваОтсортируем массив по пирамидеПервый элемент массива максимален (корень пирамиды)Поменяем первый элемент с последним(таким образом, последний элемент отсортирован)Теперь для первого элемента свойство кучи нарушено:повторим просеивание первого элемента в пирамидеот первого до предпоследнегоСнова поменяем первый и предпоследний элемент и т.п.Сложность этапа построения пирамиды есть O(n)Сложность этапа сортировки есть O(n log n)Сложноcть в худшем случае также O(n log n)Среднее количество обменов – n/2* log n26.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций