Изменения

{{Определение|definition = Left Левостороннее красно-leaning Redчерное дерево {{-Black Trees --}} тип сбалансированного двоичного дерева поиска, гарантирующий такую же асимптотическую сложность операций, как у красно-черного дерева поиска. }} ==Свойства==*Корневой узел всегда черный.*Каждый новый узел всегда окрашен в красный цвет.*Каждый дочерний нулевой узел листа дерева считается черным. 

Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево. Первая операция трансформируют <tex>3</tex>-узел (совокупность из <tex>3<code/tex>узлов, где <tex>2</tex> узла являются наследниками третьего, причем одна из связей является красной), левый потомок которого окрашен в красный, в <tex>3</tex>-узел, правый потомок которого окрашен в красный,вторая операция {{---}} наоборот. Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.===Псевдокод===[[File:rotateRight.png|310px|thumb|upright|Rotate Right]] '''Node''' rotateRight(h : '''Node'''): x = h.left h.left= x.right x.right = h x.color = h.color h.color = RED '''return''' x[[File:rotateLeft.png|310px|thumb|upright|Rotate Left]] '''Node''' rotateLeft(h : '''Node''') x= h.right h.right= x.left x.left = h x.color = h.color h.color = RED '''return''' x</code>

<code>==Переворот цветов==В красно-черных деревьях используется такая операция как '''переворот цветов''' , которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов на любом пути от корня до листа, но может привести к появлению двух последовательных красных узлов.===Псевдокод===[[File: ColorFlip.png|320px|thumb|upright| Переворот цветов]] '''Nodevoid''' rotateLeftflipColors(h : '''Node'''h): x h.color = '''!''' h.rightcolor h.right = x.left x.left color = '''!''' h x.color = hleft.color h.right.color = RED '''return!''' x</code>h.right.color

==Вставка==Вставка в ЛСКЧД базируется на <tex>4</tex> простых операциях: *Вставка нового узла к листу дерева:Если высота узла нулевая, возвращаем новый красный узел.[[File:insertNode.png|310px|thumb|upright|Вставка нового узла]]*Расщепление узла с <tex>4</tex>-я потомками:Если левый предок и правый предок красные, запускаем переворот цветов от текущего узла.[[File:Split4node.png|310px|thumb|upright|Расщепление узла]]*Принудительное вращение влево:[[File:Enforce.png|310px|thumb|upright|Принудительное вращение]]Если правый предок красный, вращаем текущую вершину влево.*Балансировка узла с <tex>4<code/tex>-я потомками:[[File:Balance4node.png|310px|thumb|Балансировка]]Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.  ===Псевдокод=== '''void''' flipColorsinsert(h key : '''NodeKey''', value : '''Value''' h): h.color root = !h.colorinsert(root, key, value) h.left.color = !h.left.color h.right.color = !h.right root.color</code>==Методы==BLACK

<code> '''Node''' insert( h : '''Node''', key : '''Key''', value : '''Value''') <span style="color:#008000">// Вставка нового листа</span> '''if''' h == ''null '' '''return''' '''new''' Node(key, value) <span style="color:#008000">// Расщепление узла с <tex>4</tex>-я потомками</span> '''if''' isRed(h.left) '''&&''' isRed(h.right) colorFlip(h) <span style="color:#008000">// Стандартная вставка [[Дерево поиска, наивная реализация|в дереве поиска]]</span> '''intif''' cmp key = key.compareTo(h.key) '''if''' cmp == 0 h.val = value '''else''' '''if''' cmp key < 0 h.key h.left = insert(h.left, key, value) '''else''' h.right = insert(h.right, key, value) <span style="color:#008000">// Принудительное вращение влево</span> '''if''' isRed(h.right) '''&&''' ''' !'''isRed(h.left) h = rotateLeft(h) <span style="color:#008000">// Балансировка узла с <tex>4</tex>-я потомками</span> '''if''' isRed(h.left) '''&&''' isRed(h.left.left) h = rotateRight(h) '''return''' ''h''</code>

==Поиск==Поиск в левосторонних красно-черных деревьях эквивалентен поиску в [[Дерево поиска, наивная реализация|наивной реализации дерева поиска]].Для поиска элемента в красно-черных деревьях дереве поиска можно воспользоваться циклом,который проходит от корня до искомого элемента. Если же элемент отсутствует, цикл пройдет до листа дерева и прервется. Для каждого узла цикл сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае цикл повторяет для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <codetex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева. ===Псевдокод=== '''Value''' search(key : '''Key'''): '''Node''' x = root '''while ''' (x != null) '''int!''' cmp = key.compareTo(x.keynull) '''if''' cmp key == 0x.key

'''if''' cmp key < 0x.key x = x.left '''else''' '''if''' cmp key > 0 x.key x = x.right '''return''''' null</code>''

==УдалениеИсправление правых красных связей==<code>*Использование Переворота цветов и вращений void deleteMin(): root = deleteMin(root) rootсохраняет баланс черной связи.color = BLACK*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4</codetex>-я потомками <span style="color:#008000">// Исправление правых красных связей<code/span> '''Node''' deleteMinfixUp( h : '''Node'''): '''if''' isRed(h.left right) h =rotateLeft(h) <span style= null"color:#008000">// Вращение <tex>2</tex>-ой красной пары пары</span> '''return''' null '''if''' !isRed(h.left) '''&&''' !isRed(h.left.left) h = moveRedLeftrotateRight(h) h.left <span style= deleteMin(h.left)"color:#008000">// Балансировка узла с <tex>4</tex>-я потомками</span> '''returnif''' fixUpisRed(h.left)</code><code> '''Node&&''' moveRedLeftisRed(h.right) colorFlip(h) '''Nodereturn''' h) ==Удаление максимума==* Спускаемся вниз по правому краю дерева.* Если поиск заканчивается на узле с <tex>4</tex>-мя или <tex>5</tex>-ю потомками, просто удаляем узел. [[File:34-nodeRemove.png|310px|thumb|center| Узлы до и после удаления]] * Удаление узла с <tex>2</tex>-я потомками нарушает балансСоответственно, спускаясь вниз по дереву необходимо поддерживать следующий инвариант : количество потомков узла не должно быть ровно <tex>2</tex>-м.[[File:changeNode.png|600px|thumb|center| ]]

Будем поддерживать инвариант: для любого узла либо сам узел, либо правый предок узла '''красный'''.Будем придерживаться тактики , что удалять лист легче, чем внутренний узел. Заметим, что если правый потомок вершины и правый потомок правого потомка вершины черные, необходимо переместить левую красную ссылку вправо для сохранения инварианта.[[File:MinEasy.png|400px|thumb|right| Перемещение красной ссылки. Простой случай]]  [[File:MinHard.png|400px|thumb|right| Перемещение красной ссылки. Сложный случай]] ===Псевдокод=== '''void''' deleteMax() root = deleteMax(root) root.color = BLACK   '''Node''' moveRedLeft(h : '''Node''') colorFlip(h) '''if''' isRed(h.right.left h.right = rotateRight(h.right) h = rotateLeft(h) colorFlip(h) '''return''' h   '''Node''' deleteMax(h : '''Node''') '''if''' isRed(h.left) <span style="color:#008000">// вращаем все 3-вершины вправо</span> h = rotateRight(h) <span style="color:#008000">// поддерживаем инвариант (h должен быть красным)</span> '''if''' h.right == ''null'' return ''null'' <span style="color:#008000">// заимствуем у брата если необходимо</span> '''if''' !isRed(h.right) '''&&''' !isRed(h.right.left) h = moveRedRight(h) <span style="color:#008000">// опускаемся на один уровень глубже </span> h.left = deleteMax(h.left) <span style="color:#008000">// исправление правых красных ссылок и 4-вершин на пути вверх</span> '''return''' fixUp(h) ==Удаление минимума==Поддерживаем инвариант: вершина или левый ребенок вершины красный. Заметим, что если левый потомок вершины и левый потомок левого потомка вершины черные, необходимо переместить красную ссылку для сохранения инварианта.[[File:MoveRedLeftEasy.png.png |400px|thumb|upright|Перемещение красной ссылки. Простой случай]][[File:MoveRedLeftNoEasy.png|400px|thumb|upright|Перемещение красной ссылки. Сложный случай]]===Псевдокод=== '''Node''' moveRedLeft(h : '''Node''') colorFlip(h) if isRed(h.right.left) h.right = rotateRight(h.right) h = rotateLeft(h) colorFlip(h) '''return''' h  '''void''' deleteMin() root = deleteMin(root) root.color = BLACK  '''Node''' deleteMin(h : '''Node''') <span style="color:#008000">// удаляем узел на нижнем уровне(h должен быть красным по инварианту)</span> if h.left == ''null'' '''return''' ''null'' <span style="color:#008000">// Если необходимо, пропушим красную ссылку вниз</span> '''if (!'''isRed(h .left) '''&& !'''isRed(h.left.left)) h = moveRedLeft(h) <span style="color:#008000">// опускаемся на уровень ниже </codespan> h.left = deleteMin(h.left) '''return''' fixUp(h)

<code> '''Node’’’ moveRedRight(h :'''Node''' ): colorFlip(h) '''if''' isRed(h.left.left)) h = rotateRight(h) colorFlip(h) '''return''' h </code><code> '''void''' delete(key : '''Key'''): root = delete(root, key)Асимптотика== rootАсимптотика методов в левосторонних красно-черных деревьях эквивалентна асимптотике [[Красно-черное дерево|базовой реализации красно-черных деревьях]].color = BLACK </code>

<code> '''Node''' delete('''Node''' : h, '''Key''' : key): '''if''' key.compareTo(h.key) < 0) '''if''' !isRed(h.left) '''&&''' !isRed(h.left.left) h = moveRedLeft(h) h.left = delete(h.left, key) '''else''' '''if''' isRed(h.left) h = rotateRight(h) '''if''' key.compareTo(h.key) == 0 '''&&''' (hСм.right также == null) '''return''' null*[[Красно-черное дерево]] '''if''' !isRed(h.right) && !isRed(h.right.left)*[[Дерево поиска, наивная реализация]] h = moveRedRight(h) '''if''' key.compareTo(h.key) =Источники информации== 0 h.val = get(h.right* Robert Sedgewick "Left-leaning Red-Black Trees" , min(h.right).key) h.key = min(h.right).key h.right = deleteMin(h.right) '''else''' h.right = delete(h.rightDepartment of Computer Science, key)Princeton University '''return''' fixUp(h)</code>[[Категория: Алгоритмы и структуры данных]]