Detailed design of red black tree – 4

This is the 14th day of my participation in the August Text Challenge.More challenges in August

The final design

#ifndef UTIL_RBTREE_H
#define UTIL_RBTREE_H

typedef struct rbtree_node_t_ rbtree_node_t;
typedef struct rbtree_t_ rbtree_t;

struct rbtree_node_t_ {
	int key;
	unsigned char color;
	void *data;
	rbtree_node_t *left;
	rbtree_node_t *right;
	rbtree_node_t *parent;
};

struct rbtree_t_ {
	rbtree_node_t *root;        // the pointer of the root of the tree
	rbtree_node_t *sentinel;    // sentinel as black leaf node
	int (*compare)(void *, const void *);
	void (*destroy)(void *);
};

/* macros */
#define rbtree_set_compare_func(tree, func) (tree)->compare = func
#define rbtree_set_destroy_func(tree, func) (tree)->destroy = func

#define rbtree_red(node) ((node)->color = 1)
#define rbtree_black(node) ((node)->color = 0)
#define rbtree_is_red(node) ((node)->color)
#definerbtree_is_black(node) (! ((node)->color))
#define rbtree_is_empty(tree) ((tree)->root == (tree)->sentinel)
// sentinel for black leaf node
#define rbtree_sentinel_init(node) rbtree_black(node)

// public methods
void rbtree_init(rbtree_t *tree, rbtree_node_t *sentinel);
void rbtree_insert_value(rbtree_t *tree, rbtree_node_t *node);
void rbtree_insert(rbtree_t *tree, rbtree_node_t *node);
void rbtree_delete(rbtree_t *tree, rbtree_node_t *node);
rbtree_node_t *rbtree_search_by_key(rbtree_t *tree, int key);
rbtree_node_t *rbtree_next(rbtree_t *tree, rbtree_node_t *node);
rbtree_node_t *rbtree_search_by_data(rbtree_t *tree, const void *keydata);
void *rbtree_get_data_by_data(rbtree_t *tree, const void *keydata);
void *rbtree_get_data_by_key(rbtree_t *tree, int key);
void rbtree_destory(rbtree_t *tree);

/* get the minimum key of node in a subtree of the rbtree */
rbtree_node_t *rbtree_get_min(rbtree_t *tree, rbtree_node_t *node);

#endifImplementation file ' 'c#include <stdio.h>
#include ".. /include/yutil/rbtree.h"

static inline void rbtree_clear(rbtree_node_t *node)
{
	node->left = NULL;
	node->right = NULL;
	node->parent = NULL;
	node->data = NULL;
	node->key = 0;
}
/** red-black tree to find nodes */
static rbtree_node_t *rbtree_search_(rbtree_t *tree, int key,
				     const void *keydata)
{
	rbtree_node_t *node = tree->root;
	int ret;

	while(node ! = tree->sentinel) {if (tree->compare && keydata) {
			ret = tree->compare(node->data, keydata);
			if (ret == 0) {
				return node;
			}
			node = (ret < 0)? node->right : node->left;continue;
		}
		if (key == node->key) {
			return node;
		}

		node = (key < node->key) ? node->left : node->right;
	}
	return NULL;
}

// repalce old_node in the tree by new_node
static inline void rbtree_replace_(rbtree_t *tree, rbtree_node_t *old_node,
				   rbtree_node_t *new_node)
{
	new_node->parent = old_node->parent;

	// repalce
	if (old_node == tree->root) {
		tree->root = new_node;
	} else if (old_node == old_node->parent->left) {
		old_node->parent->left = new_node;
	} else {
		old_node->parent->right = new_node;
	}

	old_node->parent = new_node;
}

/** * left rotate * * node temp * / \ ==> / \ * a temp node y * / \ / \ * b y a b */
static inline void rbtree_left_rotate(rbtree_t *tree, rbtree_node_t *node)
{
	rbtree_node_t *temp = node->right;

	// replace temp with left[temp]
	node->right = temp->left;
	// if left[temp] is not NIL, then it has a parent
	if(temp->left ! = tree->sentinel) { temp->left->parent = node; }// replace node with temp
	rbtree_replace_(tree, node, temp);
	temp->left = node;
}

/** * right rotate * * node temp * / \ / \ * temp y ==> a node * / \ / \ * a b b y */
static inline void rbtree_right_rotate(rbtree_t *tree, rbtree_node_t *node)
{
	rbtree_node_t *temp = node->left;

	node->left = temp->right;
	if(temp->right ! = tree->sentinel) { temp->right->parent = node; } rbtree_replace_(tree, node, temp); temp->right = node; }static void rbtree_insert_rebalance(rbtree_t *tree, rbtree_node_t *node)
{
	rbtree_node_t *gparent;
	rbtree_node_t *uncle;
	while(node ! = tree->root && rbtree_is_red(node->parent)) { gparent = node->parent->parent;if (node->parent == gparent->left) {
			uncle = gparent->right;
			// case 1: uncle is red, then update node to gparent
			// case 2: uncle is balck or NIL
			if (rbtree_is_red(uncle)) {
				rbtree_black(node->parent);
				rbtree_black(uncle);
				rbtree_red(gparent);
				node = gparent;

			} else {
				// ensue node is the left kid, make gparent,
				// parent, node in one line
				if (node == node->parent->right) {
					node = node->parent;
					rbtree_left_rotate(tree, node);
					gparent = node->parent->parent;
				}
				// case 2 -> case 1rbtree_black(node->parent); rbtree_red(gparent); rbtree_right_rotate(tree, gparent); }}else {
			uncle = node->parent->parent->left;

			if (rbtree_is_red(uncle)) {
				rbtree_black(node->parent);
				rbtree_black(uncle);
				rbtree_red(gparent);
				node = gparent;
			} else {
				if(node == node->parent->left) { node = node->parent; rbtree_right_rotate(tree, node); gparent = node->parent->parent; } rbtree_black(node->parent); rbtree_red(gparent); rbtree_left_rotate(tree, gparent); }}}// ensure the root being black, useful when new node is root
	rbtree_black(tree->root);
}

static void rbtree_delete_rebalance(rbtree_t *tree, rbtree_node_t *node)
{
	rbtree_node_t *brother;
	while(node ! = tree->root && rbtree_is_black(node)) {if (node == node->parent->left) {
			brother = node->parent->right;

			if (rbtree_is_red(brother)) {
				rbtree_black(brother);
				rbtree_red(node->parent);
				rbtree_left_rotate(tree, node->parent);
				brother = node->parent->right;
			}

			if (rbtree_is_black(brother->left) &&
			    rbtree_is_black(brother->right)) {
				rbtree_red(brother);
				node = node->parent;

			} else {
				if(rbtree_is_black(brother->right)) { rbtree_black(brother->left); rbtree_red(brother); rbtree_right_rotate(tree, brother); brother = node->parent->right; } brother->color = node->parent->color; rbtree_black(node->parent); rbtree_black(brother->right); rbtree_left_rotate(tree, node->parent); node = tree->root; }}else {
			brother = node->parent->left;

			if (rbtree_is_red(brother)) {
				rbtree_black(brother);
				rbtree_red(node->parent);
				rbtree_right_rotate(tree, node->parent);
				brother = node->parent->left;
			}

			if (rbtree_is_black(brother->left) &&
			    rbtree_is_black(brother->right)) {
				rbtree_red(brother);
				node = node->parent;

			} else {
				if (rbtree_is_black(brother->left)) {
					rbtree_black(brother->right);
					rbtree_red(brother);
					rbtree_left_rotate(tree, brother);
					brother = node->parent->left;
				}

				brother->color = node->parent->color;
				rbtree_black(node->parent);
				rbtree_black(brother->left);
				rbtree_right_rotate(tree, node->parent);
				node = tree->root;
			}
		}
	}

	rbtree_black(node);
}

void rbtree_insert_value(rbtree_t *tree, rbtree_node_t *node)
{
	rbtree_node_t **temp = &tree->root;
	rbtree_node_t *parent = NULL;

	while(*temp ! = tree->sentinel) { parent = *temp; temp = (node->key < parent->key) ? &parent->left : &parent->right; } *temp = node; node->parent = parent; node->left = tree->sentinel; node->right = tree->sentinel; rbtree_red(node); }void rbtree_init(rbtree_t *tree, rbtree_node_t *sentinel)
{
	rbtree_sentinel_init(sentinel);
	tree->root = sentinel;
	tree->sentinel = sentinel;
	tree->compare = NULL;
	tree->destroy = NULL;
}

void rbtree_insert(rbtree_t *tree, rbtree_node_t *node)
{
	rbtree_node_t *sentinel = tree->sentinel;
	rbtree_node_t *temp = rbtree_search_(tree, node->key, node->data);

	if (temp)
		return;

	// if tree is empty
	if (rbtree_is_empty(tree)) {
		node->parent = NULL;
		node->left = sentinel;
		node->right = sentinel;
		rbtree_black(node);
		tree->root = node;

		return;
	}

	rbtree_insert_value(tree, node);

	/* re-balance tree */
	rbtree_insert_rebalance(tree, node);
}

void rbtree_delete(rbtree_t *tree, rbtree_node_t *node)
{
	rbtree_node_t *subst;
	rbtree_node_t *temp;
	rbtree_node_t *sentinel = tree->sentinel;
	int red;
	/* a binary tree delete */
	if (rbtree_is_empty(tree) || node == sentinel) {
		return;
	}

	if (node->left == sentinel) {
		temp = node->right;
		subst = node;

	} else if (node->right == sentinel) {
		temp = node->left;
		subst = node;

	} else {
		subst = rbtree_get_min(tree, node->right);
		temp = subst->right;
	}

	if (subst == tree->root) {
		tree->root = temp;
		rbtree_black(temp);
		if (tree->destroy && node->data) {
			tree->destroy(node->data);
		}
		rbtree_clear(node);

		return;
	}

	red = rbtree_is_red(subst);

	if (subst == subst->parent->left) {
		subst->parent->left = temp;

	} else {
		subst->parent->right = temp;
	}

	// if subst is the node to delete
	if (subst == node) {
		temp->parent = subst->parent;

	} else {
		if (subst->parent == node) {
			temp->parent = subst;

		} else {
			temp->parent = subst->parent;
		}

		subst->left = node->left;
		subst->right = node->right;
		subst->parent = node->parent;
		subst->color = node->color;

		if (node == tree->root) {
			tree->root = subst;

		} else {
			if (node == node->parent->left) {
				node->parent->left = subst;
			} else{ node->parent->right = subst; }}if(subst->left ! = sentinel) { subst->left->parent = subst; }if (subst->right != sentinel) {
			subst->right->parent = subst;
		}
	}

	if (tree->destroy && node->data) {
		tree->destroy(node->data);
	}
	rbtree_clear(node);

	if(! red) { rbtree_delete_rebalance(tree, temp); }return;
}

rbtree_node_t *rbtree_next(rbtree_t *tree, rbtree_node_t *node)
{
	rbtree_node_t *parent;
	if (node == tree->root) {
		return NULL;
	}
	if(node->right ! = tree->sentinel) {return rbtree_get_min(tree, node->right);
	}
	while ((parent = node->parent) && node == parent->right) {
		node = parent;
	}
	return parent;
}

static i = 0;
static void rbtree_node_destroy(rbtree_t *tree, rbtree_node_t *node)
{
	if (node == tree->sentinel) {
		return;
	}
	rbtree_node_destroy(tree, node->left);
	rbtree_node_destroy(tree, node->right);
	if (tree->destroy && node->data) {
		tree->destroy(node->data);
	}
	if (node->parent) {
		if (node->parent->left == node) {
			node->parent->left = tree->sentinel;
		} else {
			node->parent->right = tree->sentinel;
		}
	}
	rbtree_clear(node);
	// somthing wrong
}

void rbtree_destory(rbtree_t *tree)
{
	rbtree_node_destroy(tree, tree->root);
	tree->root = NULL;
}
rbtree_node_t *rbtree_get_min(rbtree_t *tree, rbtree_node_t *node)
{
	while(node->left ! = tree->sentinel) { node = node->left; }return node;
}

rbtree_node_t *rbtree_search_by_key(rbtree_t *tree, int key)
{
	return rbtree_search_(tree, key, NULL);
}
rbtree_node_t *rbtree_search_by_data(rbtree_t *tree, const void *keydata)
{
	return rbtree_search_(tree, 0, keydata);
}

void *rbtree_get_data_by_data(rbtree_t *tree, const void *keydata)
{
	rbtree_node_t *node;
	node = rbtree_search_by_data(tree, keydata, tree->compare);
	if (node) {
		return node->data;
	}
	return NULL;
}

void *rbtree_get_data_by_key(rbtree_t *tree, int key)
{
	rbtree_node_t *node;
	node = rbtree_search_by_key(tree, key);
	if (node) {
		return node->data;
	}
	return NULL;
}
Copy the code

After implementation, one problem is found. Although in the actual definition, all children should be black, but in practical use, it is possible to replace the sentinel node with NULL node, which saves space and greatly speeds up the judgment in many places. But in the actual operation process, I found that the sentinel node can not be directly used in the red black tree sentinel node NULL node, otherwise there will be an error to access the empty node during deletion, leave it to solve later.