前置知识
c++的二叉搜索树

红黑树的定义
红黑树在二叉搜索树的结构基础上，增加了一些规则：

1. 所有节点不是红色就是黑色

2. 根节点和叶子节点都是黑色

3. 如果一个节点是红色，那么它两个孩子是黑色

4. 从根节点到任意一个叶子节点的路径上经过的黑色节点数量都是一样的。

红黑树的应用场景
以下工程里会用到红黑树：

1. linux进程调度CFS

2. nginx timer事件管理

3. epoll事件块的管理

红黑树的代码实现

红黑树的结构定义

enum rbtree_color
{
    red = 0,
    black = 1,
};

typedef struct _rbtree_node
{
    unsigned char color;
    _rbtree_node *parent;
    _rbtree_node *left;
    _rbtree_node *right;
    int key;
}rbtree_node;

typedef struct _rbtree
{
    rbtree_node *root;
    rbtree_node *nil; // 空黑节点 所有叶子节点指向它
}rbtree;

获取叔父节点和祖父节点

rbtree_node *GrandFather(rbtree_node *n)
{
    if(n->parent)
    {
        return n->parent->parent;
    }

    return NULL;
}

rbtree_node *Uncle(rbtree_node *n)
{
    if(n->parent && GrandFather(n))
    {
        if(n->parent == GrandFather(n)->left)
        {
            return  GrandFather(n)->right;
        }
        else
        {
            return  GrandFather(n)->left;
        }
    }

    return NULL;
}

左旋和右旋

void rbtree_left_rotate(rbtree_node *x)
{
    if(x == NULL)
    {
        return;
    }

    rbtree_node *y = x->right;
    x->right = y->left;
    y->left = x;
    if(y->left != NULL)
    {
        y->left->parent = x;
    }

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


void rbtree_right_rotate(rbtree_node *y)
{
    if(y == NULL)
    {
        return;
    }

    rbtree_node *x = y->left;
    y->left = x->right;    
    x->right = y;
    if(x->right != NULL)
    {
        x->right->parent = y;
    }

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

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

新增节点

首先通过搜索规则定位到位置：

void InsertNode(rbtree *T, int key)
{
    rbtree_mode* n = (rbtree_mode*)malloc(sizeof(rbtree_node));
    n->color = red;
    n->key = key;

    if(T->root == NULL)
    {
        T->root = n;
    }
    else
    {
    
        rbtree_mode* cur = T->root;
        rbtree_node *p = cur;
        while(cur)
        {
            p = cur;
            if(key > cur->key)
            {
                cur = cur->right;
            }
            else if(key < cur->key)
            {
                cur = cur->left;
            }
            else
            {
                free(n);
                return; // 覆盖或者不处理
            }
        }
        
        if(key > p->key)
        {
            p->right = n;
        }
        else
        {
            p->left = n;
        }
        n->parent = p;
    }

    InsertCase1(n); // 调整红黑属性
}

插入新节点后，要重新调整红黑规则，分几种情况讨论，每种情况判断不符合就跳转到下一个条件处理：

情况一，新节点是根节点：

InsertCase1(rbtree_node *n)
{
    if(n->parent == NULL)
    {
        n->color = black;
    }
    else
    {
        InsertCase2(n);
    }
}

情况二，新节点的父亲是黑色：

void InsertCase2(rbtree_node *n)
{
    if(n->parent->color == red)
    {
        InsertCase3(n);
    }
}

情况三，父节点和叔父节点都是红色，把父节点和叔父节点改成黑色，祖父节点改成红色，然后把祖父节点当做新节点重新按情况一处理：

void InsertCase3(rbtree_node *n)
{
    if(n->parent->color == red && Uncle(n)->color == red)
    {
        n->parent->color = black;
        Uncle(n)->color = black;
        GrandFather(n)->color = red;
        InsertCase1(GrandFather(n));
    }
    else
    {
        InsertCase4(n);
    }
}

情况四，父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点，进行一次左旋调换新节点和其父节点的角色，然后按情况五处理以前的父节点P：

void InsertCase4(rbtree_node *n)
{
    if(n == n->parent->right && n->parent == GrandFather(n)->left)
    {
        rbtree_left_rotate(n);
        n = n->left;
    }
    else if(n == n->parent->left && n->parent == GrandFather(n)->right)
    {
        rbtree_right_rotate(n);
        n = n->right;
    }
    
    InsertCase5(n);
}

情况五，父节点P是红色而叔父节点U是黑色或缺少，新节点N是其父节点的左子节点，而父节点P又是其父节点G的左子节点。先对祖父节点进行右旋，在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G的父节点。并切换以前的父节点P和祖父节点G的颜色：

void InsertCase5(rbtree_node *n){
     n->parent->color = BLACK;
     GrandFather(n)->color = RED;
     if(n == n->parent->left && n->parent == GrandFather(n)->left) {
         rbtree_rotate_right(n->parent);
     } else {
         
         rbtree_rotate_left(n->parent);
     }
 }

删除节点

对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们要么找到它左子树中的最大元素、要么找到它右子树中的最小元素，并把它的值转移到要删除的节点中。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值（没有复制颜色），不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。

rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {
	while (x->left != T->nil) {
		x = x->left;
	}
	return x;
}

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

rbtree_node *rbtree_successor(rbtree *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(rbtree *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(rbtree *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;
}

技术参考
1. 红黑树

2. C/C++Linux服务器开发/后台架构师

c++的红黑树

前置知识
c++的二叉搜索树

红黑树的应用场景
以下工程里会用到红黑树：

1. linux进程调度CFS

2. nginx timer事件管理

3. epoll事件块的管理

红黑树的代码实现

技术参考
1. 红黑树

2. C/C++Linux服务器开发/后台架构师

Java相关栏目本月热门文章

c++的红黑树

前置知识 c++的二叉搜索树

红黑树的应用场景 以下工程里会用到红黑树： 1. linux进程调度CFS 2. nginx timer事件管理 3. epoll事件块的管理

红黑树的代码实现

技术参考 1. 红黑树 2. C/C++Linux服务器开发/后台架构师

Java相关栏目本月热门文章

前置知识
c++的二叉搜索树

红黑树的应用场景
以下工程里会用到红黑树：

1. linux进程调度CFS

2. nginx timer事件管理

3. epoll事件块的管理

技术参考
1. 红黑树

2. C/C++Linux服务器开发/后台架构师