- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

C语言手撕红黑树---彻底理解红黑树实现原理

Lion Long 发表于 2023/04/13 22:37:50 2023/04/13

【摘要】红黑树是一种自平衡二叉查找树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。红黑树的特点是：每个节点要么是黑色，要么是红色。根节点是黑色。每个叶子节点（nil节点，空节点）是黑色的。如果一个节点是红色的，则它的两个子节点都是黑色的。对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。这些规则保证了红黑树的平衡性，使得在最坏情况下，红黑

一、环境准备

（1）VMWare+Ubuntu。

（2）vscode+ssh，连接到Linux系统，使用remote插件。

（3）gcc。

（4）XShell工具，连接调试。

此环境仅为本人的环境，仅供参考，读者只要有能编译程序的环境即可。

本章以代码实现为主，理论原理为辅助。

二、手撕红黑树代码

红黑树具有一下性质：

（1）每个结点不是红的就是黑的；

（2）根结点是黑的；

（3）每个叶子结点是黑的；

（4）如果一个结点是红的，则它的两个儿子是黑的；

（5）对每个节点，从该结点到其子孙结点的所有路径上，都包含相同数目的黑结点；即黑高。这决定红黑树的平衡。

（6）一个结点到叶子节点最长的黑结点路径和最短黑结点路径关系为 (2*n-1):1。

2.1、定义红黑树node节点

根据红黑树的特性，定义红黑树的节点结构体，成员包括：

color，红黑树节点的颜色，使用unsigned char类型定义，为了字节对齐，节省内存空间，一般将其放在结构体的最后一个。

parent，节点的父节点，为性质调整而定义的。
left，左子树。
right，右子树。
key。
value。

通常的定义方式：

#define KEY_TYPE    int
enum RB_COLOR{RED=0,BLACK};

typedef struct _rbtree_node
{
    /* data */
    KEY_TYPE                key;
    void*                   value;
    
    struct _rbtree_node*    left;   
    struct _rbtree_node*    right;  
    struct _rbtree_node*    parent; 
    unsigned char           color;  
    
}rbtree_node;

优化，定义成一个模板，使其可复用：

#define KEY_TYPE    int

enum RB_COLOR{RED=0,BLACK};


#define RBTREE_ENTRY(name,type)\
    struct name                         \
    {                                   \
        struct _rbtree_node*    left;   \
        struct _rbtree_node*    right;  \
        struct _rbtree_node*    parent; \
        unsigned char           color;  \
    }
    


typedef struct _rbtree_node
{
    /* data */
    KEY_TYPE                key;
    void*                   value;

    RBTREE_ENTRY(,_rbtree_node) node;
    // RBTREE_ENTRY(,_rbtree_node) node2;
    // RBTREE_ENTRY(,_rbtree_node) node3;

    
}rbtree_node;

2.2、定义红黑树的根节点

定义完节点，通常会定义一个链表的头，用于指向第一个节点和最后一个节点，以及其他信息。

typedef struct _RedBlackTree
{
    /* data */
    rbtree_node *root;
    rbtree_node *nil;

}RedBlackTree;

根据红黑树的性质（每个叶子结点是黑的），nil成员代表红黑树的最后一个节点，是一个黑节点，所有的末尾节点都指向它。

2.3、实现左旋

红黑树的性质发生破坏时，需要通过旋转来调整整个结构使其满足红黑树的性质。

旋转过程中需要改变3个方向6个指针的指向。

实现左旋函数，需要传入两个参数：

根节点，可以判断当前节点是否为叶子节点。
旋转节点。

static void rbtree_left_rotate(RedBlackTree *T,rbtree_node *x)
{
    rbtree_node *y = x->right;
    // 1
    x->right=y->left;
    if(y->left != T->nil)
        y->left->parent=x;

    // 2
    y->parent=x->parent;
    if(x->parent==T->nil)
        T->root=y;
    else if(x==x->parent->left)
        x->parent->left=y;
    else
        x->parent->right=y;

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

重点理解x->parent的身份：x->parent是否是根节点，x是x->parent的左子树还是右子树。

2.4、实现右旋

和左旋类似，只需要将左旋的位置做一个对调（左、右呼唤，x、y互换）。

static void rbtree_right_rotate(RedBlackTree *T,rbtree_node *y)
{
    rbtree_node *x = y->left;
    // 1
    y->left=x->right;
    if(x->right != T->nil)
        x->right->parent=y;

    // 2
    x->parent=y->parent;
    if(y->parent==T->nil)
        T->root=x;
    else if(y==y->parent->right)
        y->parent->right=x;
    else
        y->parent->left=x;

    // 3
    x->right=y;
    y->parent=x;
    
    
}

2.5、实现插入

实现插入函数，需要传入两个参数：

根节点，可以判断当前节点是否为叶子节点。
插入的节点。

关键点：

不管插入的数据是什么有多大，都是先插入最底层（即叶子节点的上一层）。这个过程需要遍历，如果遍历过程中查找到key已存在，由业务场景决定如何处理（比如丢弃，再比如如果key是一个时间戳可以对时间戳进行微调使key变为唯一）。
上色，要保证插入任何节点的前后都满足红黑树的特性（黑高），所以首先是红色，然后再调整。
当插入节点的父节点是红色时，需要调整。这个的大前提是插入的节点始终是红色的。

当插入结点时，可以推断出以下情况（比如插入的结点是z）：

（1）z是红色；

（2）z的父节点；

（3）z的祖父结点是黑色；

（4）z的叔结点不确定。

插入节点z的叔结点不确定，就有以下情况：

（1）父结点是祖父结点的左子树的情况；叔结点是红色的、叔结点是黑色而且当前结点是左孩子、叔结点是黑色的，而且当前结点是右孩子。

（2）父结点是祖父结点的右子树的情况和【父结点是祖父结点的左子树的情况】同理。


void rbtree_insert_fixup(RedBlackTree *T,rbtree_node *z)
{
    // z->color == RED
    while(z->parent->color==RED)
    {
        if(z->parent==z->parent->parent->left)
        {
            // The parent of z is the left subtree of the grandfather
            rbtree_node *y=z->parent->parent->right;
            if(y->color==RED)
            {
                y->color=BLACK;
                z->parent->color=BLACK;
                z->parent->parent->color=RED;

                // You have to make sure Z is red every time you go through it.
                z=z->parent->parent;// z->color == RED
            }
            else
            {
                //This cannot be done in one step, it must be done in the middle:
                // The state with a large number of nodes on the left is easy to rotate.
                
                if(z->parent->right==z)
                {
                    z=z->parent;
                    rbtree_left_rotate(T,z);
                }

                // The number of nodes to the left of the root node is large
                // Especially if you have two red nodes bordering each other.
                // Need to rotate.
                
                // Change the color, and then rotate
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                rbtree_right_rotate(T,z->parent->parent);
                
            }

        }
        else
        {// The parent of z is the right subtree of the grandfather
            rbtree_node *y=z->parent->parent->left;
            if(y->color==RED)// Uncle node is red
            {
                z->parent->parent->color=RED;
                z->parent->color=BLACK;
                y->color=BLACK;

                z=z->parent->parent;// z->color == RED
            }
            else
            {
                if(z==z->parent->left)
                {
                    z=z->parent;
                    rbtree_right_rotate(T,z);
                }
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                rbtree_left_rotate(T,z->parent->parent);
            }

        }
    }
    T->root->color=BLACK;
}

void rbtree_insert(RedBlackTree *T,rbtree_node *z)
{
    rbtree_node* pre=T->nil;
    rbtree_node* cur=T->root;
    while(cur!=T->nil)
    {
        pre=cur;
        if(z->key>cur->key)
            cur=cur->right;
        else if(z->key<cur->key)
            cur=cur->left;
        else
            return;
    }
	
	z->parent=pre;
    if(pre==T->nil)
	{
        T->root=z;
	}
    else
    {
        if(pre->key>z->key)
            pre->left=z;
        else
            pre->right=z;
    }
	
    
    z->left=T->nil;
    z->right=T->nil;

    z->color=RED;
	rbtree_insert_fixup(T,z);
}

这个过程，需要考虑x和y都是nil的情况；而且每次循环，z必须让其是红色。

2.6、红黑树删除结点

红黑树删除的结点有几个情况：

（1）结点没有左右子树。

（2）结点有左子树或右子树。

（3）结点有左子树且有右子树

三、完整的红黑树实现代码

RedBlackTree.h

#ifndef _FLY_RED_BLACK_TREE_H_
#define _FLY_RED_BLACK_TREE_H_

#define KEY_TYPE    int

enum RB_COLOR{RED=0,BLACK};

#if 0
#define RBTREE_ENTRY(name,type)\
    struct name                         \
    {                                   \
        struct _rbtree_node*    left;   \
        struct _rbtree_node*    right;  \
        struct _rbtree_node*    parent; \
        unsigned char           color;  \
    }
    
#endif

typedef struct _rbtree_node
{
    /* data */
    KEY_TYPE                key;
    void*                   value;
    
    struct _rbtree_node*    left;   
    struct _rbtree_node*    right;  
    struct _rbtree_node*    parent; 
    unsigned char           color;  
#if 0
    RBTREE_ENTRY(,_rbtree_node) node;
    // RBTREE_ENTRY(,_rbtree_node) node2;
    // RBTREE_ENTRY(,_rbtree_node) node3;
#endif
    
}rbtree_node;

typedef struct _RedBlackTree
{
    /* data */
    rbtree_node *root;
    rbtree_node *nil;

}RedBlackTree;

extern void rbtree_insert(RedBlackTree *T,rbtree_node *z);
extern rbtree_node *rbtree_delete(RedBlackTree *T, rbtree_node *z) ;
extern rbtree_node *rbtree_search(RedBlackTree *T, KEY_TYPE key);

#endif

RedBlackTree.c

#include "RedBlackTree.h"


static void rbtree_left_rotate(RedBlackTree *T,rbtree_node *x)
{
    rbtree_node *y = x->right;
    // 1
    x->right=y->left;
    if(y->left != T->nil)
        y->left->parent=x;

    // 2
    y->parent=x->parent;
    if(x->parent==T->nil)
        T->root=y;
    else if(x==x->parent->left)
        x->parent->left=y;
    else
        x->parent->right=y;

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

static void rbtree_right_rotate(RedBlackTree *T,rbtree_node *y)
{
    rbtree_node *x = y->left;
    // 1
    y->left=x->right;
    if(x->right != T->nil)
        x->right->parent=y;

    // 2
    x->parent=y->parent;
    if(y->parent==T->nil)
        T->root=x;
    else if(y==y->parent->right)
        y->parent->right=x;
    else
        y->parent->left=x;

    // 3
    x->right=y;
    y->parent=x;
    
    
}

static void rbtree_insert_fixup(RedBlackTree *T,rbtree_node *z)
{
    // z->color == RED
    while(z->parent->color==RED)
    {
        if(z->parent==z->parent->parent->left)
        {
            // The parent of z is the left subtree of the grandfather
            rbtree_node *y=z->parent->parent->right;
            if(y->color==RED)
            {
                y->color=BLACK;
                z->parent->color=BLACK;
                z->parent->parent->color=RED;

                // You have to make sure Z is red every time you go through it.
                z=z->parent->parent;// z->color == RED
            }
            else
            {
                //This cannot be done in one step, it must be done in the middle:
                // The state with a large number of nodes on the left is easy to rotate.
                
                if(z->parent->right==z)
                {
                    z=z->parent;
                    rbtree_left_rotate(T,z);
                }

                // The number of nodes to the left of the root node is large
                // Especially if you have two red nodes bordering each other.
                // Need to rotate.
                
                // Change the color, and then rotate
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                rbtree_right_rotate(T,z->parent->parent);
                
            }

        }
        else
        {// The parent of z is the right subtree of the grandfather
            rbtree_node *y=z->parent->parent->left;
            if(y->color==RED)// Uncle node is red
            {
                z->parent->parent->color=RED;
                z->parent->color=BLACK;
                y->color=BLACK;

                z=z->parent->parent;// z->color == RED
            }
            else
            {
                if(z==z->parent->left)
                {
                    z=z->parent;
                    rbtree_right_rotate(T,z);
                }
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                rbtree_left_rotate(T,z->parent->parent);
            }

        }
    }
    T->root->color=BLACK;
}

void rbtree_insert(RedBlackTree *T,rbtree_node *z)
{
    rbtree_node* pre=T->nil;
    rbtree_node* cur=T->root;
    while(cur!=T->nil)
    {
        pre=cur;
        if(z->key>cur->key)
            cur=cur->right;
        else if(z->key<cur->key)
            cur=cur->left;
        else
            return;
    }
	
	z->parent=pre;
    if(pre==T->nil)
	{
        T->root=z;
	}
    else
    {
        if(pre->key>z->key)
            pre->left=z;
        else
            pre->right=z;
    }
	
    
    z->left=T->nil;
    z->right=T->nil;

    z->color=RED;
	rbtree_insert_fixup(T,z);
}

/**********************红黑树删除 start***************************/
rbtree_node *rbtree_mini(RedBlackTree *T, rbtree_node *x) {
	while (x->left != T->nil) {
		x = x->left;
	}
	return x;
}

rbtree_node *rbtree_maxi(RedBlackTree *T, rbtree_node *x) {
	while (x->right != T->nil) {
		x = x->right;
	}
	return x;
}

rbtree_node *rbtree_successor(RedBlackTree *T, rbtree_node *x)
{
	rbtree_node *y = x->parent;
	if (x->right != T->nil)
	{
		return rbtree_mini(T, x->right);
	}

	
	while ((y != T->nil) && (x == y->right)) {
		x = y;
		y = y->parent;
	}
	return y;
}
//调整
void rbtree_delete_fixup(RedBlackTree *T, rbtree_node *x) {

	while ((x != T->root) && (x->color == BLACK)) {
		if (x == x->parent->left) {

			rbtree_node *w = x->parent->right;
			if (w->color == RED) {
				w->color = BLACK;
				x->parent->color = RED;

				rbtree_left_rotate(T, x->parent);
				w = x->parent->right;
			}

			if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
				w->color = RED;
				x = x->parent;
			}
			else {

				if (w->right->color == BLACK) {
					w->left->color = BLACK;
					w->color = RED;
					rbtree_right_rotate(T, w);
					w = x->parent->right;
				}

				w->color = x->parent->color;
				x->parent->color = BLACK;
				w->right->color = BLACK;
				rbtree_left_rotate(T, x->parent);

				x = T->root;
			}

		}
		else {

			rbtree_node *w = x->parent->left;
			if (w->color == RED) {
				w->color = BLACK;
				x->parent->color = RED;
				rbtree_right_rotate(T, x->parent);
				w = x->parent->left;
			}

			if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
				w->color = RED;
				x = x->parent;
			}
			else {

				if (w->left->color == BLACK) {
					w->right->color = BLACK;
					w->color = RED;
					rbtree_left_rotate(T, w);
					w = x->parent->left;
				}

				w->color = x->parent->color;
				x->parent->color = BLACK;
				w->left->color = BLACK;
				rbtree_right_rotate(T, x->parent);

				x = T->root;
			}

		}
	}

	x->color = BLACK;
}

rbtree_node *rbtree_delete(RedBlackTree *T, rbtree_node *z) 
{
	rbtree_node *y = T->nil;
	rbtree_node *x = T->nil;

	if ((z->left == T->nil) || (z->right == T->nil))
	{
		y = z;
	}
	else
	{
		y=rbtree_successor(T, z);
	}

	if (y->left != T->nil)
		x = y->left;
	else if (y->right != T->nil)
		x = y->right;


	x->parent = y->parent;
	if (y->parent == T->nil)
		T->root = x;
	else if (y == y->parent->left)
		y->parent->left = x;
	else
		y->parent->right = x;


	if (y != z)
	{
		z->key = y->key;
		z->value = y->value;
	}
	// 调整
	if (y->color == BLACK) {
		rbtree_delete_fixup(T, x);
	}

	return y;
}

/**********************红黑树删除 end***************************/

/**********************红黑树查找 start***************************/
rbtree_node *rbtree_search(RedBlackTree *T, KEY_TYPE key) {

	rbtree_node *node = T->root;
	while (node != T->nil) {
		if (key < node->key) {
			node = node->left;
		}
		else if (key > node->key) {
			node = node->right;
		}
		else {
			return node;
		}
	}
	return T->nil;
}
/**********************红黑树查找 end***************************/

四、使用示例

#include <stdio.h>
#include <stdlib.h>
#include "../src/RedBlackTree.h"

/**********************红黑树使用示例 start***************************/
// 遍历
void rbtree_traversal(RedBlackTree *T, rbtree_node *node) {
	if (node != T->nil) {
		rbtree_traversal(T, node->left);
		printf("key:%d, color:%d\n", node->key, node->color);
		rbtree_traversal(T, node->right);
	}
}

int main() {

	int keyArray[20] = { 24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15 };

	RedBlackTree *T = (RedBlackTree *)malloc(sizeof(RedBlackTree));
	if (T == NULL) {
		printf("malloc failed\n");
		return -1;
	}

	T->nil = (rbtree_node*)malloc(sizeof(rbtree_node));
	T->nil->color = BLACK;
	T->root = T->nil;

	rbtree_node *node = T->nil;
	int i = 0;
	for (i = 0; i < 20; i++) {
		node = (rbtree_node*)malloc(sizeof(rbtree_node));
		node->key = keyArray[i];
		node->value = NULL;
		printf("insert arr[%d]=%d\n",i,keyArray[i]);
		rbtree_insert(T, node);
		printf("insert end\n");

	}
	printf("----------------------------------------\n");
	rbtree_traversal(T, T->root);
	printf("----------------------------------------\n");

	for (i = 0; i < 20; i++) {
		printf("search key = %d\n", keyArray[i]);
		rbtree_node *node = rbtree_search(T, keyArray[i]);

		if(node!=T->nil)
		{
			printf("delete key = %d\n", node->key);
			rbtree_node *cur = rbtree_delete(T, node);
			free(cur);
		}
		else
			break;
		
		printf("show rbtree: \n");
		rbtree_traversal(T, T->root);
		printf("----------------------------------------\n");
	}
    if(T!=NULL)
        free (T);
}

// gcc -o example main.c ../src/RedBlackTree.c
/**********************红黑树使用示例 end***************************/

总结

红黑树是一种自平衡二叉查找树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。红黑树的特点是：

每个节点要么是黑色，要么是红色。
根节点是黑色。
每个叶子节点（nil节点，空节点）是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的。
对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

这些规则保证了红黑树的平衡性，使得在最坏情况下，红黑树的查找、插入和删除操作的时间复杂度都是O(log n)。红黑树被广泛应用于各种编程语言的标准库中，如C++的STL中的map和set。

点赞
收藏
关注作者

0/1000

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

加入云驻计划，成为创作者

华为云周边好礼
免费体验产品
特殊身份标识
线下官方门票
内部专家零距离
与10000+优质创作者共同成长

立即加入

C语言手撕红黑树---彻底理解红黑树实现原理

一、环境准备

二、手撕红黑树代码

2.1、定义红黑树node节点

2.2、定义红黑树的根节点

2.3、实现左旋

2.4、实现右旋

2.5、实现插入

2.6、红黑树删除结点

三、完整的红黑树实现代码

四、使用示例

总结

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

C语言手撕红黑树---彻底理解红黑树实现原理

一、环境准备

二、手撕红黑树代码

2.1、定义红黑树node节点

2.2、定义红黑树的根节点

2.3、实现左旋

2.4、实现右旋

2.5、实现插入

2.6、红黑树删除结点

三、完整的红黑树实现代码

四、使用示例

总结

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

推荐阅读

相关产品