红黑树的实现

2024-01-12 12:31:28

  1. 定义：
  • 每个结点要么是“红色”，要么是“黑色”(后面将说明)
  • 所有的叶结点都是空结点，并且是“黑色”的
  • 如果一个结点是“红色”的，那么它的两个子结点都是“黑色”的。
  • 结点到其子孙结点的每条简单路径都包含相同数目的“黑色”结点
  • 根结点永远是“黑色”的

首先，是先有红黑树，再通过无数的经验总结出来了红黑树特殊的性质。所以不必深入研究这些性质是怎么来的。

红黑树的实现

2.说明：

  • 红黑树全名平衡二叉检索树，主要应用于一些系统方面：
    • Linux进程调度 CFS
    • Nginx Timer事件管理
    • Epoll事件块的管理
  • 特性2中的叶子节点，是只为空(NIL或null)的节点。
  • 特性4，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接*衡的二叉树。

3.左旋右旋
红黑树的实现
红黑树的实现

首先，上述红黑树的性质是为了对该二叉树做出一些约束让红黑树达到查询的最佳的时间复杂度，在对一个平衡的红黑树进行插入或者删除操作之后，如果违反上述红黑树的性质，导致查询的时间复杂度下降。而通过左旋和右旋来让二叉树满足性质。

1.插入
红黑树的插入必定在叶子节点上进行的。
红黑树的实现

红黑树的实现

红黑树的实现

对应的插入节点再右子树上和上述情况刚好相反。

2.删除

  1. 当前结点的兄弟结点是红色的
  2. 当前结点的兄弟结点是黑色的，而且兄弟结点的
    两个孩子结点都是黑色的
  3. 当前结点的兄弟结点是黑色的，而且兄弟结点的
    左孩子是红色的，右孩子是黑色的
    当前结点是父结点的左子树的情况
  4. 当前结点的兄弟结点是黑色的，而且兄弟结点的
    右孩子是红色的

红黑树的实现
红黑树的实现
红黑树的实现
红黑树的实现

附上代码：
测试可通过，代码为C代码，但是C++编译器可通过， C编译器应该问题不大。

RbTree.h


typedef int KEY;
typedef int VALUE;
#define RED 1
#define BLACK 2

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


struct rbtree_node
{
	RBTREE_ENTRY(, rbtree_node) bst;

	KEY key;
	VALUE Value;
};


struct rbtree
{
	rbtree() {
		root = NULL;
	}
	struct rbtree_node* root;
	struct rbtree_node* nil;
};

RbTree.cpp

#include "RbTree.h"



struct rbtree_node* rbtree_node_create(int key, VALUE value)
{
	struct rbtree_node* new_node = (struct rbtree_node*)malloc(sizeof(rbtree_node));
	if (NULL == new_node)
	{
		return NULL;
	}
	new_node->bst.left = NULL;
	new_node->bst.right = NULL;
	new_node->bst.parent = NULL;
	new_node->bst.color = RED;
	new_node->key = key;
	new_node->Value = value;
	return new_node;
}


rbtree_node* rbtree_successor(rbtree* T, rbtree_node* x) {
	rbtree_node* y = x->bst.parent;

	if (x->bst.right != T->nil) {
		//return rbtree_mini(T, x->bst.right);
		rbtree_node * rnode = x->bst.right;
		while (rnode->bst.left != T->nil) {
			rnode = rnode->bst.left;
		}
		return rnode;
	}

	while ((y != T->nil) && (x == y->bst.right)) {
		x = y;
		y = y->bst.parent;
	}
	return y;
}


int rbtree_left_translate(rbtree* T, rbtree_node * x)
{
	if (NULL == T || NULL == x)
	{
		return -1;
	}

	rbtree_node* y = x->bst.right;

	//1
	y->bst.parent = x->bst.parent;
	if (x->bst.parent == T->nil)
	{
		T->root = y;
	}
	else if (x == x->bst.parent->bst.left)
	{
		x->bst.parent->bst.left = y;
	}
	else
	{
		x->bst.parent->bst.right = y;
	}
	

	//3
	if (y->bst.left != T->nil)
	{
		y->bst.left->bst.parent = x;
	}
	x->bst.right = y->bst.left;


	y->bst.left = x;
	x->bst.parent = y;
	


}

int rbtree_right_translate(rbtree* T, rbtree_node* x)
{
	if (NULL == T || NULL == x)
	{
		return -1;
	}

	rbtree_node* y = x->bst.left;

	//1
	y->bst.parent = x->bst.parent;
	if (x->bst.parent == T->nil)
	{
		T->root = y;
	}
	else if (x->bst.parent->bst.left = x)
	{
		x->bst.parent->bst.left = y;
	}
	else
	{
		x->bst.parent->bst.right = y;
	}


	if (y->bst.right != T->nil)
	{
		y->bst.right->bst.parent = x;
	}
	x->bst.left = y->bst.right;

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

// 插入一个节点之前，该红黑色必然是平衡二叉树，只有插入的当前节点(插入节点默认为红色)和父节点都为红色，破坏了二叉树的平衡， 才需要自平衡
void rbtree_insert_fixup(rbtree* T, rbtree_node* z)
{
	while (RED == z->bst.parent->bst.color)
	{
		if (z->bst.parent == z->bst.parent->bst.left)//当前插入节点在祖父节点的左子树 叔父节点祖父节点的右边
		{
			rbtree_node* y = z->bst.parent->bst.parent->bst.right;
			if (RED == y->bst.color)//叔父节点为红色
			{
				z->bst.parent->bst.color = BLACK;
				y->bst.color = BLACK;
				z->bst.parent->bst.parent->bst.color = RED;

				z = z->bst.parent->bst.parent;//改变了祖父节点的颜色，所以需要循环向上遍历是否满足性质
			}
			else//叔父节点为黑色，需要右旋
			{
				if (z == z->bst.parent->bst.right)//当前插入节点为父节点的右节点，需要先左旋
				{
					z = z->bst.parent;
					rbtree_left_translate(T, z);
				}

				z->bst.parent->bst.color = BLACK;
				z->bst.parent->bst.parent->bst.color = RED;
				rbtree_right_translate(T, z->bst.parent->bst.parent);

			}
		}
		else//当前插入节点在祖父节点的右子树
		{
			rbtree_node* y = z->bst.parent->bst.parent->bst.left;
			if (RED == y->bst.color)//叔父节点为红色
			{
				z->bst.parent->bst.color = BLACK;
				y->bst.color = BLACK;
				z->bst.parent->bst.parent->bst.color = RED;

				z = z->bst.parent->bst.parent;//改变了祖父节点的颜色，所以需要循环向上遍历是否满足性质
			}
			else//叔父节点为黑色，需要左旋
			{
				if (z == z->bst.parent->bst.left)//当前插入节点为父节点的左节点，需要先右旋
				{
					z = z->bst.parent;
					rbtree_right_translate(T, z);
				}

				z->bst.parent->bst.color = BLACK;
				z->bst.parent->bst.parent->bst.color = RED;
				rbtree_left_translate(T, z->bst.parent->bst.parent);

			}
		}

		//根节点为黑色
		T->root->bst.color = BLACK;
	}
}

void rbtree_insert(rbtree* T, rbtree_node* z) {


	rbtree_node* y = T->nil;
	rbtree_node* x = T->root;

	while (x != T->nil) {
		y = x;
		if (z->key < x->key) {
			x = x->bst.left;
		}
		else if (z->key > x->key) {
			x = x->bst.right;
		}
		else { //Exist 就退出
			return;
		}
	}

	z->bst.parent = y;
	if (y == T->nil) {
		T->root = z;
	}
	else if (z->key < y->key) {
		y->bst.left = z;
	}
	else {
		y->bst.right = z;
	}

	z->bst.left = T->nil;
	z->bst.right = T->nil;
	z->bst.color = RED;

	rbtree_insert_fixup(T, z);
}


void rbtree_delete_fixup(rbtree* T, rbtree_node* x) {

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

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

				rbtree_left_translate(T, x->bst.parent);
				w = x->bst.parent->bst.right;
			}

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

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

				w->bst.color = x->bst.parent->bst.color;
				x->bst.parent->bst.color = BLACK;
				w->bst.right->bst.color = BLACK;
				rbtree_left_translate(T, x->bst.parent);

				x = T->root;
			}

		}
		else {

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

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

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

				w->bst.color = x->bst.parent->bst.color;
				x->bst.parent->bst.color = BLACK;
				w->bst.left->bst.color = BLACK;
				rbtree_right_translate(T, x->bst.parent);

				x = T->root;
			}

		}
	}

	x->bst.color = BLACK;
}



rbtree_node* rbtree_delete(rbtree* T, rbtree_node* z) {

	rbtree_node* y = T->nil;
	rbtree_node* x = T->nil;

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

	if (y->bst.left != T->nil) {
		x = y->bst.left;
	}
	else if (y->bst.right != T->nil) {
		x = y->bst.right;
	}

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

	if (y != z) {
		z->key = y->key;
		z->Value = y->Value;
	}

	if (y->bst.color == BLACK) {
		rbtree_delete_fixup(T, x);
	}

	return y;
}
上一篇：BST中删除一个节点，并返回新的BST


下一篇：『数据结构与算法』二叉查找树（BST）