Изменения

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

One way to view redЧтобы поддерживать левосторонние красно-black BST algorithms is as maintaining the following invariant properties under insertion and deletionчерные двоичные деревья поиска необходимо соблюдать следующие инварианты при вставке и удалении:• No path from the root to the bottom contains two consecutive red links* Ни один путь от корня до листьев дерева не содержит двух последовательных красных узлов.• The number of black links on every such path is the same* Количество черных узлов на каждом таком пути одинаково.These invariants imply that the length of every path in a red-black tree with N nodes is no longer than 2 lg N . This worst case is realizedОсновные операции, for exampleиспользуемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, in a tree whose nodes are all black except forthose along a single path of alter- nating red and black nodesназываются вращением вправо и вращением влево.The basic operations that bal- anced-tree algorithms use to main- tain balance under insertion and deletion are known as rotations. In the context of red-black trees, these operations are easily understood as the transformations needed to transform a Первая операция трансформируют <tex>3</tex>-node whose red link leans to the left to a узел (совокупность из <tex>3-node whose red link leans to the right and vice- versa. The Java code for these op- erations (for a Node type that we will consider late that contains a left link</tex> узлов, a right linkгде <tex>2</tex> узла являются наследниками третьего, and a color eld that can be set to the value RED to represent the color of the incoming linkпричем одна из связей является красной) is given to the left and to the right on this page. Rotations obvi- ously preserve the two invariants stated above.In red-black trees, we also use a simple operation known as a color левый потомок которого окрашен в красный, в ip (shown at the bottom of thispage). In terms of 2-<tex>3</tex>-4 treesузел, правый потомок которого окрашен в красный, a color ip is the essential operation: it corresponds to splitting a 4вторая операция {{---node and passing the middle node up to the parent}} наоборот. A color ip obviously does not change the number of black links on any path from the root to the bottomВращения сохраняют два указанных выше инварианта, but it may introduce two consecu- tive red links higher in the tree, which must be correctedне изменяют поддеревья узла.Red-black BST algorithms differ on whether and when they do rotations and color ips, in order to maintain the global invariants stated at the top of this page===Псевдокод===[[File:rotateRight.<code>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>==Переворот цветов==В красно-черных деревьях используется такая операция как '''переворот цветов''' , которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов на любом пути от корня до листа, но может привести к появлению двух последовательных красных узлов.===Псевдокод===[[File: ColorFlip.png|320px|thumb|upright| Переворот цветов]] '''void''' flipColors(h : '''Node''' h) h.color = '''!''' h.color h.left.color = '''!''' h.left.color h.right.color = '''!''' h.right.color

<code> '''Node''' rotateLeft(h : '''Node'''): x = h.right h.right = x.left x.left Вставка= h x.color = h.color h.color = RED '''return''' xВставка в ЛСКЧД базируется на <tex>4</codetex>простых операциях:

<code> '''void''' flipColors(h : '''Node''' h)*Вставка нового узла к листу дерева: hЕсли высота узла нулевая, возвращаем новый красный узел.color = '''!'''h[[File:insertNode.colorpng|310px|thumb|upright|Вставка нового узла]]*Расщепление узла с <tex>4</tex>-я потомками: h.left.color = Если левый предок и правый предок '''!'''hкрасные, запускаем переворот цветов от текущего узла.left[[File:Split4node.colorpng|310px|thumb|upright|Расщепление узла]]*Принудительное вращение влево: h[[File:Enforce.right.color = '''!'''h.rightpng|310px|thumb|upright|Принудительное вращение]]Если правый предок красный, вращаем текущую вершину влево.color*Балансировка узла с <tex>4</codetex>-я потомками:[[File:Balance4node.png|310px|thumb|Балансировка]]Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.

==Методы=Псевдокод=== '''void''' insert(key : '''Key''', value : '''Value''' ) root = insert(root, key, value) root.color = BLACK

<code> '''Node''' insert( h : '''Node''', key : '''Key''', value : '''Value''') <span style="color:#008000">// Вставка нового листа</span> '''if''' h == ''null''

<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 = h.key.compareTo( h.key) val = value '''else''' '''if''' key < h.key cmp == 0 h.val left = insert(h.left, 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>

h = rotateRight(h) '''return''' ''h''</code>

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

'''if''' cmp key > 0 x.key x = x.right '''return''' ''null'' ==Исправление правых красных связей==*Использование Переворота цветов и вращений сохраняет баланс черной связи.*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4</tex>-я потомками <span style="color:#008000">// Исправление правых красных связей</span> '''Node''' fixUp(h : '''Node''') '''if''' isRed(h.right) h = rotateLeft(h) <span style="color:#008000">// Вращение <tex>2</tex>-ой красной пары пары</span> '''if''' isRed(h.left) '''&&''' isRed(h.left.left) h = rotateRight(h) <span style="color:#008000">// Балансировка узла с <tex>4</tex>-я потомками</span> '''if''' isRed(h.left) '''&&''' isRed(h.right) colorFlip(h) '''return''' h ==Удаление максимума==* Спускаемся вниз по правому краю дерева.* Если поиск заканчивается на узле с <tex>4</tex>-мя или <tex>5</tex>-ю потомками, просто удаляем узел. [[File:34-nodeRemove.png|310px|thumb|center| Узлы до и после удаления]] * Удаление узла с <tex>2</tex>-я потомками нарушает балансСоответственно, спускаясь вниз по дереву необходимо поддерживать следующий инвариант : количество потомков узла не должно быть ровно <tex>2</codetex>-м.[[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

==Удаление==f cient implementation of the delete operation is a challenge in many symbol-table implementa- tions, and red-black trees are no exception. Industrial-strength implementations run to over 100 lines of code, and text books generally describe the operation in terms of detailed case studies, eschewing full implementations. Guibas and Sedgewick presented a delete implementation in [7], but it is not fully speci ed and depends on a call-by-reference approach not commonly found in modern code. The most popular method in common use is based on a parent pointers '''Node''' deleteMax(see [6]h : '''Node'''), which adds substantial overhead and does not reduce the number of cases to be handled.The code on the next page is a full implementation of <tex>delete '''if''' isRed()</tex> for LLRB 2-3 treesh. It is based on the reverse of the approach used for insert in top-down 2-3-4 trees: we perform rotations and color ips on the way down the search path to ensure that the search does not end on a 2-node, so that we can just delete the node at the bottom. We use the method <tex>fixUp(left) </tex> to share the code for the span style="color ip and rotations following therecursive calls in the <tex:#008000">insert()</tex> code.With <tex>fixUp()</tex>, we can leave right-leaning red links and unbalanced 4-nodes along the search path, securethat these conditions will be xed on the way up the tree. (The approach is also effective 2-вращаем все 3-4 trees, but requires an extra rotation when the right nodeoff the search path is a 4-node.)As a warmup, consider the delete-the-minimum operation, where the goal is to delete the bottom node on the left spine while maintaining balance. To do so, we maintain the invariant that the current node or its left child is red. We can do so by moving to the left unless the current node is red and its left child and left grandchild are both black. In that case, we can do a color ip, which restores the invariant but may introduce successive reds on the right. In that case, we can correct the condition with two rotations and a color ip. These operations are implemented in the <tex>moveRedLeft()вершины вправо</texspan> method on the next page. With <tex>moveRedLeft h = rotateRight(h)</tex>, the recursive implementation of <tex>deleteMin()</tex> above is straightforward.For general deletion, we also need <tex>moveRedRight()</tex>, which is similar, but simpler, and we need to rotate left-leaning red links to the right on the search path to maintain the invariant. If the node to be deleted is an internal node, we replace its key and value elds with those in the minimum node in its right subtree and then delete the minimum in the right subtree (or we could rearrange pointers to use the node instead of copying elds). The full implementation of <texspan style="color:#008000">delete()</tex> that dervies from this discussion is given on the facing page. It uses one-third to one-quarter the amount of code found in typical implementations. It has been demonstrated before [2, 11, 13] that maintaining a eld in each node containing its height can lead to code for delete that is similarly concise, but that extra space is a high price to pay in a practical implementation. With <tex>LLRB</tex> trees, we can arrange for concise code having a logarithmic performance guarantee and using no extra space.<code> '''void''' deleteMinподдерживаем инвариант (h должен быть красным) root = deleteMin(root); root.color = BLACK;</codespan> '''Nodeif''' deleteMin(h : '''Node''') if (h.left right == ''null'') ''' return''' ''null''; <span style="color:#008000">// заимствуем у брата если необходимо</span> '''if !'''!isRed(h.leftright) '''&& !'''!isRed(h.leftright.left) h = moveRedLeftmoveRedRight(h); <span style="color:#008000">// опускаемся на один уровень глубже </span> h.left = deleteMindeleteMax(h.left); <span style="color:#008000">// исправление правых красных ссылок и 4-вершин на пути вверх</span> '''return''' fixUp(h); ==Удаление минимума==Поддерживаем инвариант: вершина или левый ребенок вершины красный.

Delete-the-minimum code for LLRB 2-3 treesЗаметим, что если левый потомок вершины и левый потомок левого потомка вершины черные, необходимо переместить красную ссылку для сохранения инварианта.[[File:MoveRedLeftEasy.png.png |400px|thumb|upright|Перемещение красной ссылки. Простой случай]][[File:MoveRedLeftNoEasy.png|400px|thumb|upright|Перемещение красной ссылки. Сложный случай]]<code>===Псевдокод=== '''voidNode''' deleteMinmoveRedLeft(h : '''Node''') colorFlip(h): root = deleteMin if isRed(rooth.right.left) root h.color right = BLACKrotateRight(h.right)</code> h = rotateLeft(h) colorFlip(h) '''return''' h

<code> '''Nodevoid''' deleteMin( h : '''Node'''): '''if''' h.left root == ''null'' '''return''' ''null'' '''if''' !isReddeleteMin(h.left) '''&&''' !isRed(h.left.leftroot) h = moveRedLeft(h) h root.left color = deleteMin(h.left) '''return''' fixUp(h)</code>BLACK

<code> '''Node''' moveRedLeftdeleteMin(h : '''Node''' ) <span style="color: #008000">// удаляем узел на нижнем уровне(hдолжен быть красным по инварианту):</span> colorFlip( if h).left == ''null'' '''return''' ''null'' <span style="color:#008000">// Если необходимо, пропушим красную ссылку вниз</span> '''if (!''' isRed(h.right.left) '''&& !'''isRed(h.right = rotateRight(hleft.rightleft)) h = rotateLeftmoveRedLeft(h) colorFlip<span style="color:#008000">// опускаемся на уровень ниже </span> h.left = deleteMin(h.left) '''return''' fixUp(h </code> )

<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>[[Категория: Алгоритмы и структуры данных]]