红黑树的结构

类型定义包括两个部分:一个root节点和多个树节点

root节点

root节点保存红黑树的树根节点

typedef struct rb_tree() {
    Node* node;
} RBRoot;

树节点

树节点用于保存红黑树节点中的信息包括

  • 节点的颜色 color 
  • 节点存储的有效信息 key 
  • 以及节点的左孩子节点 left ,右孩子节点 right 和父节点 parent 
typedef struct RBTreeNode {
    unsigned char color;
	Type key;
	struct RBTreeNode* left;
	struct RBtreeNode* right;
	struct RBtreeNode* parent;
} Node, *RBTree;

主要有六个函数用于实现红黑树:红黑树的创建销毁左旋右旋插入节点删除节点

创建

分配一个root节点

RBRoot* create_rbtree() {
    RBRoot* root = (RBRoot*) malloc( sizeof( RBRoot ) );
    root->node   = NULL;
    return root;
}

销毁

销毁主要分四个步骤:

  1. 销毁左子树
  2. 销毁右子树
  3. 释放树根节点空间
  4. 释放root节点空间
static void rbtree_destroy( RBTree tree ) {
    if ( tree == NULL ) return;
    if ( tree->left != NULL ) rbtree_destroy( tree->left );
    if ( tree->right != NULL ) rbtree_destroy( tree->right );

    free( tree );
}
void destroy_rbtree( RBRoot* root ) {
    if ( root != NULL ) rbtree_destroy( root->node );

    free( root );
}

为了实现在红黑树的插入与删除后,并且保持红黑树的性质不变,需要用到下面两个对树的基本操作左旋和右旋

左旋

树的左旋示意图
左旋操作

对节点b进行左旋操作,进行左旋后减少了左子树的深度,增大了右子树的深度

static void rbtree_left_rotate( RBRoot* root, Node* x ) {
    Node* y = x->right;

    x->right = y->left;
    if ( y->left != NULL ) y->left->parent = x;

    y->parent = x->parent;

    if ( x->parent == NULL ) {
        root->node = y;
    } else {
        if ( x->parent->left == x )
            x->parent->left = y;
        else
            x->parent->right = y;
    }

    y->left   = x;
    x->parent = y;
}

右旋

数的右旋
右旋操作

右旋操作与左旋操作相反,上图对节点a进行右旋操作,减少了右子树的深度,增大了左子树的深度

static void rbtree_right_rotate( RBRoot* root, Node* y ) {
    Node* x = y->left;

    y->left = x->right;
    if ( x->right != NULL ) x->right->parent = y;

    x->parent = y->parent;

    if ( y->parent == NULL ) {
        root->node = x;
    } else {
        if ( y == y->parent->right )
            y->parent->right = x;
        else
            y->parent->left = x;
    }

    x->right = y;

    y->parent = x;
}

插入节点

红黑树的插入分为两步:首先将待插入节点标记为红色并安装二叉查找树的方法插入;第二步对红黑树进行调整,使其保持红黑树的特性。根据不同的情况需要做出不同的调整:

  1. 情况一:新节点N位于树的根上,没有父节点
    1. 直接将其标记为黑色即可
  2. 情况二:新节点N的父节点P是黑色
    1. 直接插入,无需修正
  3. 情况三:父节点P与叔父节点U都为红色
    1. 将父节点P与叔父节点U标记为黑色
    2. 将祖父节点G标记为红色
    3. 将祖父节点G作为新插入节点重新进行修正(重新执行修正)
  4. 情况四:父节点P为红色,叔父节点U不为红色(新节点与父节点不同侧)
    • 父节点P为祖父节点G的左子节点新节点N为父节点P的右子节点
      1. 对节点N进行左旋操作
      2. 对节点N的左子树(左旋操作前的父节点P)执行情况5
    • 父节点P为祖父节点G的右子节点新节点N为父节点P的左子节点
      1. 对节点N进行右旋操作
      2. 对节点N的右子树(右旋操作前的父节点P)执行情况5
  5. 情况五:父节点P为红色,叔父节点U不为红色
    1. 将父节点P标记为黑色
    2. 将祖父节点G标记为红色
    3. 父节点P为祖父节点G的右子节点新节点N为父节点P的右子节点
      1. 对父节点P进行右旋操作
    4. 父节点P为祖父节点G的左子节点新节点N为父节点P的左子节点
      1. 对父节点P进行左旋操作
static void rbtree_insert_fixup( RBRoot* root, Node* node ) {
    Node *parent, *gparent;

    while ( ( parent = rb_parent( node ) ) && rb_is_red( parent ) ) {
        gparent = rb_parent( parent );

        if ( parent == gparent->left ) {
            {
                Node* uncle = gparent->right;
                if ( uncle && rb_is_red( uncle ) ) {
                    rb_set_black( uncle );
                    rb_set_black( parent );
                    rb_set_red( gparent );
                    node = gparent;
                    continue;
                }
            }

            if ( parent->right == node ) {
                Node* tmp;
                rbtree_left_rotate( root, parent );
                tmp    = parent;
                parent = node;
                node   = tmp;
            }

            rb_set_black( parent );
            rb_set_red( gparent );
            rbtree_right_rotate( root, gparent );
        } else {
            {
                Node* uncle = gparent->left;
                if ( uncle && rb_is_red( uncle ) ) {
                    rb_set_black( uncle );
                    rb_set_black( parent );
                    rb_set_red( gparent );
                    node = gparent;
                    continue;
                }
            }

            if ( parent->left == node ) {
                Node* tmp;
                rbtree_right_rotate( root, parent );
                tmp    = parent;
                parent = node;
                node   = tmp;
            }

            rb_set_black( parent );
            rb_set_red( gparent );
            rbtree_left_rotate( root, gparent );
        }
    }

    rb_set_black( root->node );
}
static void rbtree_insert( RBRoot* root, Node* node ) {
    Node* y = NULL;
    Node* x = root->node;

    while ( x != NULL ) {
        y = x;
        if ( node->key < x->key )
            x = x->left;
        else
            x = x->right;
    }
    rb_parent( node ) = y;

    if ( y != NULL ) {
        if ( node->key < y->key )
            y->left = node;
        else
            y->right = node;
    } else {
        root->node = node;
    }

    node->color = RED;

    rbtree_insert_fixup( root, node );
}
int insert_rbtree( RBRoot* root, Type key ) {
    Node* node;

    if ( search( root->node, key ) != NULL ) return -1;

    if ( ( node = create_rbtree_node( key, NULL, NULL, NULL ) ) == NULL )
        return -1;

    rbtree_insert( root, node );

    return 0;
}

删除节点

节点的删除也分为两个步骤:节点的删除删除后的修正

节点的删除分为三种情况:

  1. 节点没有子树,直接删除
  2. 节点只有一个子树,用子节点替代此节点,在子节点上进行修正
  3. 节点有两个子树,用右子树最小值节点替代此节点,在新节点上进行修正

对于删除后的修正,如果删除节点是红色,则无需修正,否则需要修正,分多种情况:

  1. 情况一:N是新的根
    1. 无需修正
  2. 情况二:兄弟节点S是红色
    1. 对父节点P进行左旋,交换N的父节点P与祖父节点G的颜色
    2. 进入情况三
  3. 情况三:N的父节点G,兄弟节点S和S的儿子都是黑色
    1. 将兄弟节点S设置为红色
    2. 对父节点P从情况一开始重新修正
  4. 情况四:N的父节点G为红色,兄弟节点S和S的儿子都是黑色
    1. 交换N的兄弟和父亲的颜色
  5. 情况五:N的父节点G为红色,兄弟节点S为红色,S的右儿子为黑色,N为其父节点的左儿子
    1. 在S上做右旋
    2. 交换S和它的父节点颜色
    3. 进入情况六
  6. 情况六:S是黑色,S的右儿子是红色,N为其父节点的左儿子
    1. 在N的父节点P上做左旋
    2. 交换N和父节点的颜色
    3. 将S的右子树设置为黑色
static void rbtree_delete_fixup( RBRoot* root, Node* node, Node* parent ) {
    Node* other;

    while ( ( !node || rb_is_black( node ) ) && node != root->node ) {
        if ( parent->left == node ) {
            other = parent->right;
            if ( rb_is_red( other ) ) {
                rb_set_black( other );
                rb_set_red( parent );
                rbtree_left_rotate( root, parent );
                other = parent->right;
            }
            if ( ( !other->left || rb_is_black( other->left ) ) &&
                 ( !other->right || rb_is_black( other->right ) ) ) {
                rb_set_red( other );
                node   = parent;
                parent = rb_parent( node );
            } else {
                if ( !other->right || rb_is_black( other->right ) ) {
                    rb_set_black( other->left );
                    rb_set_red( other );
                    rbtree_right_rotate( root, other );
                    other = parent->right;
                }
                rb_set_color( other, rb_color( parent ) );
                rb_set_black( parent );
                rb_set_black( other->right );
                rbtree_left_rotate( root, parent );
                node = root->node;
                break;
            }
        } else {
            other = parent->left;
            if ( rb_is_red( other ) ) {
                rb_set_black( other );
                rb_set_red( parent );
                rbtree_right_rotate( root, parent );
                other = parent->left;
            }
            if ( ( !other->left || rb_is_black( other->left ) ) &&
                 ( !other->right || rb_is_black( other->right ) ) ) {
                rb_set_red( other );
                node   = parent;
                parent = rb_parent( node );
            } else {
                if ( !other->left || rb_is_black( other->left ) ) {
                    rb_set_black( other->right );
                    rb_set_red( other );
                    rbtree_left_rotate( root, other );
                    other = parent->left;
                }
                rb_set_color( other, rb_color( parent ) );
                rb_set_black( parent );
                rb_set_black( other->left );
                rbtree_right_rotate( root, parent );
                node = root->node;
                break;
            }
        }
    }
    if ( node ) rb_set_black( node );
}
void rbtree_delete( RBRoot* root, Node* node ) {
    Node *child, *parent;
    int   color;

    if ( ( node->left != NULL ) && ( node->right != NULL ) ) {
        Node* replace = node;

        replace = replace->right;
        while ( replace->left != NULL ) {
            replace = replace->left;
        }

        if ( rb_parent( node ) ) {
            if ( rb_parent( node )->left == node ) {
                rb_parent( node )->left = replace;
            } else {
                rb_parent( node )->right = replace;
            }
        } else {
            root->node = replace;
        }

        child  = replace->right;
        parent = rb_parent( replace );

        color = rb_color( replace );

        if ( parent == node ) {
            parent = replace;
        } else {
            if ( child ) rb_set_parent( child, parent );
            parent->left = child;

            replace->right = node->right;
            rb_set_parent( node->right, replace );
        }

        replace->parent    = node->parent;
        replace->color     = node->color;
        replace->left      = node->left;
        node->left->parent = replace;

        if ( color == BLACK ) rbtree_delete_fixup( root, child, parent );
        free( node );

        return;
    }

    if ( node->left != NULL ) {
        child = node->left;

    } else {
        child = node->right;
    }

    parent = node->parent;
    color  = node->color;

    if ( child ) child->parent = parent;

    if ( parent ) {
        if ( parent->left == node ) {
            parent->left = child;
        } else {
            parent->right = child;
        }
    } else {
        root->node = child;
    }

    if ( color == BLACK ) rbtree_delete_fixup( root, child, parent );
    free( node );
}
void delete_rbtree( RBRoot* root, Type key ) {
    Node *z, *node;

    if ( ( z = search( root->node, key ) ) != NULL ) rbtree_delete( root, z );
}

参考

  1. linux/rbtree.h at 5bfc75d92efd494db37f5c4c173d3639d4772966 · torvalds/linux (github.com)
  2. linux/rbtree.c at 5bfc75d92efd494db37f5c4c173d3639d4772966 · torvalds/linux (github.com)
最后修改日期: 2022-02-02