288
правок
Изменения
Нет описания правки
x = x.right
'''return''' ''null''
==Удаление==
*Использование <tex>flipColor</tex> и <tex>rotate</tex> сохраняют баланс черной связи.
* Необходимо исправить правые красные связи и устранить узлы с <tex>4-</tex>я потомками
'''Node''' fixUp(h : '''Node'''){
'''if''' (isRed(h.right))
h = rotateLeft(h);
'''if''' (isRed(h.left) && isRed(h.left.left))
h = rotateRight(h);
'''if''' (isRed(h.left) && isRed(h.right))
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 (see [6]), which adds substantial overhead and does not reduce the number of cases to be handled.
