21 (Лекции 2013-го года)

Курс «Алгоритмы и алгоритмические языки»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.