Korbin

C语言红黑树实现

红黑树的结构

类型定义包括两个部分：一个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的左子节点 a. 对节点N进行右旋操作 b. 对节点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)