Tree.h в OpenBSD: навязчивое двоичное дерево без зависимостей (2002)

treehвopenbsdнавязчивоедвоичноедеревобеззависимостей2002

/ Авторские права

Нильс Провос
Все права защищены. Распространение и использование в исходной и двоичной формах, с или без модификации, допускаются при соблюдении следующих условий которые встретились: 1. При повторном распространении исходного кода должно сохраняться указанное выше авторское право обратите внимание, этот список условий и следующий отказ от ответственности. 2. Распространение в двоичной форме должно воспроизводить указанное выше авторское право уведомление, этот список условий и следующий отказ от ответственности в документация и / или другие материалы, поставляемые с дистрибутивом. ДАННОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПРЕДОСТАВЛЯЕТСЯ АВТОРОМ “ КАК ЕСТЬ ” И ЛЮБОЙ ЯВНО ИЛИ ПОДРАЗУМЕВАЕМЫЕ ГАРАНТИИ, ВКЛЮЧАЯ, НО НЕ ОГРАНИЧЕННЫЕ К ПОДРАЗУМЕВАЕМЫМ ГАРАНТИЯМ ОТКАЗ ОТ КОММЕРЧЕСКОЙ ЦЕННОСТИ И ПРИГОДНОСТИ ДЛЯ ОПРЕДЕЛЕННОЙ ЦЕЛИ ОТКАЗЫВАЕТСЯ. АВТОР НИ ПРИ КАКИХ ОБСТОЯТЕЛЬСТВАХ НЕ НЕСЕТ ОТВЕТСТВЕННОСТИ ЗА ЛЮБЫЕ ПРЯМЫЕ, КОСВЕННЫЕ, СЛУЧАЙНОЕ, ОСОБЕННОЕ, ПРИМЕРНОЕ ИЛИ ПОСЛЕДСТВИЕ УБЫТКИ (ВКЛЮЧАЯ, НО НЕ ОГРАНИЧИВАЕТСЯ ЗАКУПКОЙ ЗАМЕНЫ ТОВАРЫ ИЛИ УСЛУГИ; ПОТЕРЯ ИСПОЛЬЗОВАНИЯ, ДАННЫЕ ИЛИ ПРИБЫЛЬ; ИЛИ ПЕРЕРЫВ ДЕЯТЕЛЬНОСТИ), ОДНАКО ВЫЗВАННЫМ И НА ЛЮБОМ ТЕОРИЯ ОТВЕТСТВЕННОСТИ, ЛИБО В КОНТРАКТЕ, СТРОГОЙ ОТВЕТСТВЕННОСТИ ИЛИ ПЕРЕДАЧИ (ВКЛЮЧАЯ НЕБРЕЖНОСТЬ ИЛИ ИНОЕ), ВОЗНИКАЮЩИМ В ЛЮБОМ СЛУЧАЕ В РЕЗУЛЬТАТЕ ИСПОЛЬЗОВАНИЯ ДАННОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ, ДАЖЕ ЕСЛИ ПРЕДУПРЕЖДЕНО ВОЗМОЖНОСТЬ ТАКОГО ПОВРЕЖДЕНИЯ. / # ifndef _SYS_TREE_H _ # outline _ SYS_TREE_H _ / Этот файл определяет структуру данных для разных типов деревьев: раскидистые деревья и красно-черные деревья. Расширяемое дерево – это самоорганизующаяся структура данных. Каждая операция на дерево вызывает растяжение. Экран перемещает запрошенный узел к корню дерева и частично перебалансирует его. Это имеет то преимущество, что локальность запроса приводит к более быстрому поиску, так как

требование используемые узлы перемещаются на вершину дерева. С другой стороны, каждый поиск вызывает запись в память. Теорема баланса ограничивает общее время доступа для m операций и n вставляет в изначально пустое дерево как O ((m + n) lg n). амортизированная стоимость для последовательности из m обращений к расширенному дереву равна O (lg п); Красно-черное дерево – это двоичное дерево поиска с цветом узла в виде дополнительный атрибут. Он выполняет набор условий: – каждый путь поиска от корня до листа состоит из такое же количество черных узлов, – каждый красный узел (кроме корня) имеет черного родителя, – каждый листовой узел черный. Каждая операция над красно-черным деревом ограничена как O (lg n). Максимальная высота красно-черного дерева 2lg (n + 1). / # outline SPLAY_HEAD ( имя, тип ) struct имя { struct тип sph_root; / корень дерева / } # outline SPLAY_INIT (корень) делать { (корень) -> sph_root = НОЛЬ; } в то время как ( 0 ) #определять SPLAY_ENTRY (тип) struct { struct kind spe_left; / левый элемент / struct kind spe_right; / правый элемент / } # outline SPLAY_LEFT ( вяз, поле ) (вяз) -> subject.spe_left # outline SPLAY_RIGHT ( вяз, поле ) (вяз) -> subject.spe_right # outline SPLAY_ROOT ( head ) (голова) -> sph_root / SPLAY_ROTATE_ {LEFT, RIGHT} ожидайте, что tmp удерживает SPLAY_ {RIGHT, LEFT} / #определять SPLAY_ROTATE_RIGHT ( head, tmp, subject ) do { SPLAY_LEFT ((голова) -> sph_root , поле) = SPLAY_RIGHT (tmp, subject); SPLAY_RIGHT (tmp, subject) = (head) -> sph_root ; (голова) -> sph_root = tmp; } в то время как ( 0 ) # outline SPLAY_ROTATE_LEFT ( head, tmp, subject ) do { SPLAY_RIGHT ((голова) -> sph_root , subject) = SPLAY_LEFT (tmp, subject); SPLAY_LEFT (tmp , поле) = (голова) -> sph_root ; (голова) -> sph_root = tmp; } пока ( 0 ) #определять SPLAY_LINKLEFT ( head, tmp, subject ) do { SPLAY_LEFT (tmp, subject) = (head) -> sph_root ; tmp = (голова) -> sph_root ; (голова) -> sph_root = SPLAY_LEFT ((голова) -> sph_root , поле); } в то время как ( 0 ) # outline SPLAY_LINKRIGHT ( head, tmp, subject ) делать { SPLAY_RIGHT (tmp, subject) = (head) -> sph_root ; tmp = (голова) -> sph_root ; (голова) -> sph_root = SPLAY_RIGHT ((голова) -> sph_root , поле ); } пока ( 0 ) # outline SPLAY_ASSEMBLE ( head, node, left, proper, subject ) do { SPLAY_RIGHT (слева, поле) = SPLAY_LEFT ((голова) -> sph_root , поле); SPLAY_LEFT (справа, поле) = SPLAY_RIGHT ((голова) -> sph_root , поле); SPLAY_LEFT ((голова) -> sph_root , поле) = SPLAY_RIGHT (узел, поле); SPLAY_RIGHT ((голова) -> sph_root , поле) = SPLAY_LEFT (узел, поле); } в то время как ( 0 ) / Создает прототипы и встроенные функции / # outline SPLAY_PROTOTYPE ( имя, тип, поле, cmp ) void title ## _ SPLAY ( struct title *, struct тип ; пустота имя ## _ SPLAY_MINMAX ( struct имя *, int ); static __inline void имя ## _ SPLAY_INSERT ( struct имя голова, struct тип вяз) { if ((голова) -> sph_root == НОЛЬ) { SPLAY_LEFT (вяз, поле) = SPLAY_RIGHT (вяз , поле) = NULL ; } еще { int __comp; имя ## _ SPLAY (голова, вяз) ; __comp = (cmp) (вяз, (голова) -> sph_root ); если (__comp < 0 ) { SPLAY_LEFT (вяз, поле) = SPLAY_LEFT ((голова) -> sph_root , поле); SPLAY_RIGHT (вяз, поле) = (голова) -> sph_root ; SPLAY_LEFT ((голова) -> sph_root , поле) = NULL ; } else if (__comp> 0 ) { SPLAY_RIGHT ( вяз, поле) = SPLAY_RIGHT ((голова) -> sph_root , поле) ; SPLAY_LEFT (вяз, поле) = (голова) -> sph_root ; SPLAY_RIGHT ((голова) -> sph_root , поле) = NULL ; } еще возвращаться; } (голова) -> sph_root = (вяз); } static __inline void имя ## _ SPLAY_REMOVE ( struct title head, struct тип вяз) { struct тип __ tmp; if ((голова) -> sph_root == НОЛЬ) возвращаться; имя ## _ SPLAY (голова, вяз); if ((cmp) (вяз, (голова) -> sph_root ) == 0 ) { если ( SPLAY_LEFT ((голова) -> sph_root , поле) == НОЛЬ) { (голова) -> sph_root = SPLAY_RIGHT ((голова) -> sph_root , поле); } еще { __tmp = SPLAY_RIGHT ((голова ) -> sph_root , поле); (голова) -> sph_root = SPLAY_LEFT ((голова) -> sph_root , поле); имя ## _ SPLAY (голова, вяз); SPLAY_RIGHT ((голова) -> sph_root , поле) = __tmp; } } } / Находит узел с тем же ключом, что и вяз / статический __inline struct тип имя ## _ SPLAY_FIND ( struct имя голова, struct тип вяз) { if ((голова) -> sph_root == НОЛЬ) возвращаться( НОЛЬ); имя ## _ SPLAY (голова, вяз); if ((cmp) (вяз, (голова) -> sph_root ) == 0 ) возвращаться (голова -> sph_root ); return ( NULL ); } статический __inline struct тип имя ## _ SPLAY_NEXT ( struct имя заголовок, struct тип вяз) { title ## _ SPLAY (голова, вяз); если ( SPLAY_RIGHT (вяз, поле)! = NULL ) { вяз = SPLAY_RIGHT (вяз, поле); пока ( SPLAY_LEFT (вяз, поле)! = NULL ) { вяз = SPLAY_LEFT (вяз, поле); } } еще вяз = NULL ; return (вяз); } статический __inline struct тип имя ## _ SPLAY_MIN_MAX ( struct title head, int val) { имя ## _ SPLAY_MINMAX (голова, val); возвращаться ( SPLAY_ROOT (голова)); } / Работа основного дисплея. Перемещает узел близко к ключу вяза наверх / # outline SPLAY_GENERATE ( имя, тип, поле, cmp ) void title ## _ SPLAY ( struct title head, struct тип вяз) { struct тип __node, __ left, __ proper, __ tmp; int __comp; SPLAY_LEFT (& __ узел, поле) = SPLAY_RIGHT (& __ узел, поле) = NULL ; __left = __right = & __ node; пока ((__comp = (cmp) (вяз, (голова) -> sph_root ))) { if (__comp < 0 ) { __tmp = SPLAY_LEFT ( (голова) -> sph_root , поле); if (__tmp == NULL ) перерыв; если ((cmp) (вяз, __tmp) < 0 ) { SPLAY_ROTATE_RIGHT (голова, __tmp, поле); if ( SPLAY_LEFT ((голова) -> sph_root , поле) == NULL ) перерыв; } SPLAY_LINKLEFT (голова, __права, поле); } еще if (__comp> 0 ) { __tmp = SPLAY_RIGHT ((голова) -> sph_root , поле); if (__tmp == NULL ) перерыв; если ((cmp) (вяз, __tmp)> 0 ) { SPLAY_ROTATE_LEFT (голова, __tmp , поле); if ( SPLAY_RIGHT ( (голова) -> sph_root , поле) == NULL ) перерыв; } SPLAY_LINKRIGHT (голова, __влево, поле); } } SPLAY_ASSEMBLE (голова, & __ узел, __влево, __права, поле); } / Играть с минимальным или максимальным элементом Используется для поиска минимального или максимального элемента в дереве . / недействительно имя ## _ SPLA Y_MINMAX ( struct title head, int __comp) { struct тип __node, __ left, __ proper, __ tmp; SPLAY_LEFT (& __ узел, поле) = SPLAY_RIGHT (& __ узел, поле) = NULL ; __left = __right = & __ узел; пока ( 1 ) { if (__comp < 0 ) { __tmp = SPLAY_LEFT ((голова) -> sph_root , поле); if (__tmp == NULL ) перерыв; если (__comp < 0 ) { SPLAY_ROTATE_RIGHT (голова, __tmp, поле ); if ( SPLAY_LEFT ((голова) -> sph_root , subject) == NULL ) перерыв; } SPLAY_LINKLEFT (голова, __права, поле); } еще if (__comp> 0 ) { __tmp = SPLAY_RIGHT ((голова) -> sph_root , поле); если (__tmp == NULL ) перерыв; if (__comp> 0 ) { SPLAY_ROTATE_LEFT (голова, __tmp, поле); if ( SPLAY_RIGHT ((голова) – > sph_root , subject) == NULL ) перерыв; } SPLAY_LINKRIGHT (голова, __влево, поле); } } SPLAY_ASSEMBLE (голова, & __ узел, __влево, __права, поле); } # определить SPLAY_NEGINF 1 #определять SPLAY_INF 1 # outline SPLAY_INSERT ( имя, x, y ) имя ## _ SPLAY_INSERT (x, y) #определять SPLAY_REMOVE ( имя, x, y ) имя ## _ SPLAY_REMOVE (x, y) # outline SPLAY_FIND ( имя, x, y ) имя ## _ SPLAY_FIND (x, y) #определять SPLAY_NEXT ( имя, x, y ) имя ## _ SPLAY_NEXT (x, y) # outline SPLAY_MIN ( имя, x ) имя ## _ SPLAY_MIN_MAX (x, SPLAY_NEGINF) #определять SPLAY_MAX ( имя, x ) имя # #_SPLAY_MIN_MAX (x, SPLAY_INF) #определять SPLAY_FOREACH ( x, имя, руководитель ) for ((x) = SPLAY_MIN (имя, голова); (x)! = НОЛЬ; (x) = SPLAY_NEXT (имя, голова, x)) / Макросы, определяющие дерево красного цвета / #определять RB_HEAD ( имя, тип ) struct имя { struct тип rbh_root; / корень дерева / } # outline RB_INIT ( корень ) do { (корень) -> rbh_root = NULL ; } пока ( 0 ) # определить RB_BLACK 0 #определять RB_RED 1 # определить RB_ENTRY ( тип ) struct { struct тип rbe_left; / левый элемент / struct тип rbe_right; / правый элемент / struct тип rbe_parent; / родительский элемент / int rbe_color; / цвет узла / } # outline RB_LEFT ( вяз, поле ) (вяз) -> subject.rbe_left # outline RB_RIGHT ( вяз, поле ) (вяз) -> subject.rbe_right #определять RB_PARENT ( вяз, поле ) (вяз) -> subject.rbe_parent #определять RB_COLOR ( вяз, поле ) (вяз) -> subject.rbe_color #определять RB_ROOT ( голова ) (голова) -> rbh_root # outline RB_SET ( вяз, родитель, поле ) делать { RB_PARENT (вяз, поле) = родительский; RB_LEFT (вяз, поле) = RB_RIGHT (вяз, поле) = NULL ; RB_COLOR (вяз, поле) = RB_RED; } пока ( 0 ) #определять RB_SET_BLACKRED ( черный, красный, поле ) do { RB_COLOR (черный , поле) = RB_BLACK; RB_COLOR (красный, поле) = RB_RED; } пока ( 0 ) # ifndef RB_AUGMENT # outline RB_AUGMEN Т ( x ) # endif # outline RB_ROTATE_LEFT ( head, elm, tmp, subject ) делать { (tmp) = RB_RIGHT (вяз, поле); если (( RB_RIGHT (вяз, поле) = RB_LEFT (tmp, поле))) { RB_PARENT ( RB_LEFT (tmp, поле ), поле) = (вяз); } RB_AUGMENT (вяз); if (( RB_PARENT (tmp, subject) = RB_PARENT (вяз, поле))) { if ((вяз) == RB_LEFT ( RB_PARENT (вяз, поле), поле)) RB_LEFT ( RB_PARENT (вяз, поле), поле) = (tmp); еще RB_RIGHT ( RB_PARENT (вяз, поле), поле) = (tmp); ДОГОВОР АУДИТОРИИ ( ОБЪЯВЛЕНИЕ ОБЪЯВЛЕНИЙ ())) вяз, поле)); } еще (голова) -> rbh_root = (tmp); RB_LEFT (tmp, subject) = (elm ); RB_PARENT (вяз, поле ) = (tmp); RB_AUGMENT (tmp); } пока ( 0 ) # outline RB_ROTATE_RIGHT ( голова, вяз, tmp, поле ) do { (tmp) = RB_LEFT (вяз, поле); if (( RB_LEFT (вяз, поле) = RB_RIGHT (tmp, subject))) { RB_PARENT ( RB_RIGHT (tmp, subject), subject) = (вяз); } RB_AUGMENT (вяз); if (( RB_PARENT (tmp, поле) = RB_PARENT (вяз, поле))) { if ((вяз) == RB_LEFT ( RB_PARENT (вяз, поле), поле)) RB_LEFT ( RB_PARENT (вяз, поле), поле) = (tmp); еще RB_RIGHT ( RB_PARENT (вяз, поле), поле) = (tmp); RB_AUGMENT ( RB_PARENT (вяз, поле)); } еще (голова) -> rbh_root = (tmp); RB_RIGHT (tmp, поле) = (вяз); RB_PARENT (вяз, поле) = (tmp); RB_AUGMENT (tmp); } в то время как ( 0 ) / Создает прототипы и встроенные функции / #определять RB_PROTOTYPE ( имя, тип, поле, cmp ) void имя ## _ RB_INSERT_COLOR ( struct имя *, struct тип ; пустота имя ## _ RB_REMOVE_COLOR ( struct title *, struct тип *, struct тип ; void имя ## _ RB_REMOVE ( struct имя *, struct тип ; struct тип имя ## _ RB_INSERT ( struct title *, struct тип ; struct тип имя ## _ RB_FIND ( struct имя *, struct тип ; struct тип имя ## _ RB_NEXT ( struct имя *, struct тип ; struct тип имя ## _ RB_MINMAX ( struct имя *, int ); / Основная операция rb. Перемещает узел ближе к ключу вяза наверх / # outline RB_GENERATE ( имя, тип, поле, cmp ) пустота имя ## _ RB_INSERT_COLOR ( struct имя голова, struct тип вяз) { struct kind guardian, gparent, tmp; whereas ((guardian = RB_PARENT (вяз, поле)) && RB_COLOR (родительский элемент, поле) == RB_RED ) { gparent = RB_PARENT (родитель, поле); if (guardian == RB_LEFT (gparent , поле)) { tmp = RB_RIGHT (gparent, поле); if (tmp && RB_COLOR (tmp, subject) == RB_RED) { RB_COLOR (tmp, поле) = RB_BLACK; RB_SET_BLACKRED (родитель, родитель, поле); вяз = gparent; Продолжать ; } если ( RB_RIGHT (родитель, поле) == вяз) { RB_ROTATE_LEFT (заголовок, родитель, tmp, поле); tmp = guardian; родитель = вяз; вяз = tmp; } RB_SET_BLACKRED (родитель, родитель, поле); RB_ROTATE_RIGHT (голова, gparent, tmp, subject); } еще { tmp = RB_LEFT (gparent, поле) ; if (tmp && RB_COLOR (tmp, поле) == RB_RED) { RB_COLOR (tmp, поле) = RB_BLACK; RB_SET_BLACKRED (родитель, родитель, поле); вяз = gparent; Продолжать
; } if ( RB_LEFT (родительский элемент, поле) = = вяз) { RB_ROTATE_RIGHT (заголовок, родительский элемент, tmp, поле); tmp = guardian; guardian = elm; вяз = tmp; } RB_SET_BLACKRED (родительский, родительский, поле); RB_ROTATE_LEFT (голова, gparent, tmp, поле); } } RB_COLOR (голова -> rbh_root , поле) = RB_BLACK; } пустота имя ## _ RB_REMOVE_COLOR ( struct имя голова, struct тип родительский, struct тип вяз) { struct тип tmp; в то время как ((вяз == NULL || RB_COLO R (вяз, поле) == RB_BLACK) && вяз! = RB_ROOT (голова)) { если ( RB_LEFT (родитель, поле) == вяз) { tmp = RB_RIGHT (родитель, поле); если ( RB_COLOR (tmp, subject) == RB_RED) { RB_SET_BLACKRED (tmp, родительский элемент, поле); RB_ROTATE_LEFT (заголовок, родительский элемент, tmp, поле); tmp = RB_RIGHT (родительский элемент, поле); } if (( RB_LEFT (tmp, subject) == NULL || RB_COLOR ( RB_LEFT ( tmp, subject), subject) == RB_BLACK) && ( RB_RIGHT (tmp, subject) == NULL || RB_COLOR ( RB_RIGHT (tmp, subject), subject) == RB_BLACK)) { RB_COLOR (tmp, subject) = RB_RED; вяз = родительский; guardian = RB_PARENT (вяз, поле); } еще { if ( RB_RIGHT (tmp, subject) == NULL || RB_COLOR ( RB_RIGHT (tmp, subject), subject) == RB_BLACK) { struct тип oleft ; if ((oleft = RB_LEFT (tmp, subject))) RB_COLOR (левое, поле) = RB_BLACK; RB_COLOR (tmp, поле) = RB_RED; RB_ROTATE_RIGHT (head, tmp, oleft, subject); tmp = RB_RIGHT (родитель, поле); } RB_COLOR (tmp, поле) = RB_COLOR (родительский элемент, поле); RB_COLOR (родительский элемент, поле) = RB_BLACK; если ( RB_RIGHT (tmp, поле)) RB_COLOR ( RB_RIGHT (tmp, поле), поле) = RB_BLACK; RB_ROTATE_LEFT (заголовок, родительский элемент, tmp, поле); вяз = RB_ROOT (голова); перерыв; } } еще { tmp = RB_LEFT (родитель, поле); если ( RB_COLOR (tmp, subject) == RB_RED) { RB_SET_BLACKRED (tmp, родительский элемент, поле); RB_ROTATE_RIGHT (голова, родительский элемент, tmp, поле ); tmp = RB_LEFT (родительский элемент, поле); } if (( RB_LEFT (tmp, subject) == NULL || RB_COLOR ( RB_LEFT (tmp, поле), поле) == RB_BLACK) && ( RB_RIGHT (tmp, subject) == NULL || RB_COLOR ( RB_RIGHT (tmp, subject), subject) == RB_BLACK)) { RB_COLOR (tmp, subject) = RB_RED; вяз = родительский; guardian = RB_PARENT (вяз, поле); } еще { если ( RB_LEFT (tmp, subject) == NULL || RB_COLOR ( RB_LEFT (tmp, поле), поле) == RB_ ЧЕРНИТЬ) { struct тип oright; если (( oright = RB_RIGHT (tmp, поле)) ) RB_COLOR (oright, поле) = RB_BLACK; RB_COLOR (tmp, subject) = RB_RED; RB_ROTATE_LEFT ( head, tmp, oright, subject); tmp = RB_LEFT (родитель, поле); } RB_COLOR (tmp, поле) = RB_COLOR ( родитель, поле); RB_COLOR (родитель, поле) = RB_BLACK; если ( RB_LEFT (tmp, поле))

133 RB_COLOR ( RB_LEFT (tmp, поле), поле) = RB_BLACK; RB_ROTATE_RIGHT (заголовок, родительский элемент, tmp, поле); вяз = RB_ROOT (голова); перерыв; } } } if (вяз) RB_COLOR (вяз, поле) = RB_BLACK; } пустота имя ## _ RB_REMOVE ( struct title head, struct тип вяз) { struct тип дочерний, родительский; int цвет; если ( RB_LEFT (вяз, поле) == NULL ) ребенок = RB_RIGHT (вяз, поле); еще if ( RB_RIGHT (вяз, поле) == НОЛЬ) ребенок = RB_LEFT (вяз, поле); еще { struct тип previous = elm, left; вяз = RB_RIGHT (вяз, поле); в то время как ((left = RB_LEFT (вяз , поле))) вяз = левый; youngster = RB_RIGHT (вяз, поле); guardian = RB_PARENT (вяз, поле); цвет = RB_COLOR (вяз, поле); if (ребенок) RB_PARENT (потомок, поле) = родитель; если (родитель) { if ( RB_LEFT (родительский элемент, поле) == вяз)

616 RB_LEFT (родительский, fi поле) = ребенок;

621 еще RB_RIGHT (родительский элемент, поле) = дочерний элемент; RB_AUGMENT (родительский); } еще RB_ROOT (голова) = потомок; если ( RB_PARENT (вяз, поле) == старый) guardian = elm; (вяз) -> поле = (старое) -> поле ; если ( RB_PARENT (старое, поле)) { если ( RB_LEFT ( RB_PARENT (старый, поле), поле) == старый) RB_LEFT ( RB_PARENT (старое, поле), поле) = вяз; еще RB_RIGHT ( RB_PARENT (старое, поле), поле) = вяз; RB_AUGMENT ( RB_PARENT (старое, поле)); } еще RB_ROOT (голова) = вяз; RB_PARENT ( RB_LEFT (старое, поле), поле) = вяз; если ( RB_RIGHT (старое, поле)) RB_PARENT ( RB_RIGHT (старый, поле), поле) = вяз; if (родительский) { left = guardian; делать { RB_AUGMENT (слева); } пока ((left = RB_PARENT (слева, поле))); } goto цвет; } guardian = RB_PARENT (вяз, поле); цвет = RB_COLOR (вяз, поле); if (ребенок) RB_PARENT (дочерний элемент, поле) = родительский; if (родительский) { если ( RB_LEFT (родитель, поле) == вяз) RB_LEFT (родительский , поле) = ребенок; еще RB_RIGHT (родительский элемент, поле) = дочерний элемент; RB_AUGMENT (родительский); } еще RB_ROOT (голова) = ребенок; цвет: если (цвет == RB_BLACK) имя ## _ RB_REMOVE_COLOR (голова, родитель, ребенок); } / Вставляет узел в дерево RB / struct тип 287 имя ## _ RB_INSERT ( struct title head, struct тип вяз) { struct kind tmp; struct kind guardian = NULL ; int comp = 0 ; tmp = RB_ROOT (голова); в то время как (tmp) { guardian = tmp; comp = (cmp) (вяз, родитель); если (comp < 0 ) tmp = RB_LEFT (tmp, поле); еще if (comp> 0 ) tmp = RB_RIGHT (tmp, поле); еще return (tmp);

315 } RB_SET (вяз, родитель, поле); if (guardian! = NULL ) { если (comp < 0 ) RB_LEFT (родитель, поле) = вяз; еще RB_RIGHT (родитель, поле) = вяз; RB_AUGMENT (родительский); } еще RB_ROOT (голова) = вяз ; имя ## _ RB_INSERT_COLOR (голова, вяз); return ( NULL ); } / Находит узел с тем же ключом, что и вяз / struct тип

650 имя ## _ RB_FIND ( struct имя голова, struct тип вяз) { struct тип tmp = RB_ROOT (голова);

648 int comp; в то время как (tmp) { 278

642 comp = cmp (вяз, тмп);

631 if (comp < 0 ) 561 452 tmp = RB_LEFT (tmp, поле); еще if (comp> 0 )

638 tmp = RB_RIGHT (tmp, поле);

626 еще return (tmp); } return ( NULL ); } 602 struct тип имя ## _ RB_NEXT ( struct имя голова, struct тип вяз) { если ( RB_RIGHT (вяз, поле)) {

607 вяз = RB_RIGHT (вяз, поле); в то время как ( RB_LEFT (вяз, поле)) вяз = RB_LEFT (вяз, поле); } еще { если ( RB_PARENT (вяз, поле) && (вяз = = RB_LEFT ( RB_PARENT (вяз, поле), поле))) вяз = RB_PARENT (вяз, поле); еще { whereas ( RB_PARENT (вяз, поле) && (вяз == RB_RIGHT ( RB_PARENT (вяз, поле), поле))) вяз = RB_PARENT (вяз, поле); вяз = RB_PARENT (вяз, поле); } } return (вяз); } struct тип имя ## _ RB_MINMAX ( struct имя голова, int val) {

567 struct тип tmp = RB_ROOT (глава); struct тип guardian = NULL ; в то время как (tmp) { guardian = tmp; если (val < 0 ) tmp = RB_LEFT (tmp, поле); еще tmp = RB_RIGHT (tmp, поле); }

550 return (родительский); } 546 #определять RB_NEGINF 1 # outline RB_INF 1 #определять RB_INSERT ( имя, x , y ) имя ## _ RB_INSERT (x, y) #определять RB_REMOVE ( имя, x, y ) имя ## _ RB_REMOVE (x, y) # определить RB_FIND ( имя, x, y ) имя ## _ RB_FIND (x, y) # outline RB_NEXT ( имя, x, y ) имя ## _ RB_NEXT (x, y)

533 # outline RB_MIN ( имя, x ) имя ## _ RB_MINMAX (x, RB_NEGINF)

530 # outline RB_MAX ( имя, x ) имя ## _ RB_MINMAX (x, RB_INF) #определять RB_FOREACH ( x, имя, руководитель ) для ((x) = RB_MIN (имя, руководитель); (x)! = NULL ; (x) = имя ## _ RB_NEXT (голова, x)) # endif / _SYS_TREE_H_ /

Leave a comment

Your email address will not be published. Required fields are marked *