Лекция 8 Красно-черные деревья План лекции 1.Определение красно-черного дерева и его высота. 2.Вращения 3.Вставка элемента, восстановление структуры дерева 4.Удаление элемента, процедура RB_Delete_Fixup.

Красно-черные деревья Красно-черное дерево –это двоичное дерево поиска, вершины которого разделены на красные и черные. Двоичное дерево поиска называется красно-черным деревом, если оно обладает следующими свойствами: Каждая вершина – либо черная, либо красная. Корень дерева является черным Каждый лист (NIL) – черный. Если вершина красная, оба ее ребенка черные. Все пути, идущие вниз от корня к листьям, содержат одинаковое количество черных вершин.

Красно-черное дерево

Высота красно-черного дерева Красно-черное дерево с n внутренними вершинами (т.е. не считая NIL-листьев) имеет высоту не больше 2*log(n+1) Поддерево с корнем в x содержит по меньшей мере 2 bh(x) – 1 внутренних вершин (bh(x) – черная высота вершины x). Для листьев черная высота равна 0. Если вершина не является листом и имеет черную высоту k, то оба ее ребенка имеют черную высоту не меньше k- 1. По предположению индукции левое и правое поддеревья вершины x содержат не менее 2 k-1 1вершин, поэтому поддерево с корнем в x содержит по меньшей мере 2 k k = 2 k -1 внутренних вершин. Черная высота дерева не меньше h/2.Тогда n>= 2 h/2 -1. Ч.т.д.

Вращения

Добавление вершины

Добавление вершины(2)

Добавление вершины (3)

Добавление вершины (4)

Удаление RB-DELETE (T, z) 1 if left[z] = nil[T] or right[z] = nil[T] 2 then y = z 3 else y = TREE- SUCCESSOR(z) 4 if left[y] != nil[T] 5 then x = left[y] 6 else x = right[y] 7 p[x] = p[y] 8 if p[y] = nil[T] 9 then root[T] = x 10 else if y = left[p[y]] 11 then left[p[y]] = x 12 else right[p[y]] = x 13 if y != z 14 then key[z] = key[y] 15 If y has other fields, copy them, too. 16 if color[y] = BLACK 17 then RB-DELETE- FIXUP (T,x) 18 return y

Удаление (2)

Удаление (3)