This is the 11th day of my participation in the August Wenwen Challenge.More challenges in August

Red-black tree is a self-balanced binary search tree due to the characteristics of node color. But unlike, say, Balanced Binary Trees, it contains a color-coded piece of data. Its various constraints make the longest possible path from root to leaf no more than twice as long as the shortest possible path. Although red-black tree implementation is relatively complex, but the performance is good, so red-black tree is widely used in the kernel. Red-black trees can be used in the following scenarios

  1. Conflict handling of hash tables

    Red-black trees are efficient when there are many nodes. When there are fewer nodes, the linked list is more convenient.

  2. Dynamic insert, delete, and query scenarios.

In general, red-black trees can provide the following interfaces:

void RBTree_Init(RBTree *rbt); // Initializes the red-black tree
void RBTree_Destroy(RBTree *rbt); // Destroy the red-black tree
RBTreeNode * RBTree_First(const RBTree *rbt); // Get the first node
RBTreeNode * RBTree_Next(const RBTreeNode *node); // Get the next node
RBTreeNode * RBTree_Search(RBTree* rbt, int key); // the red-black tree looks for nodes
void*        RBTree_GetData(RBTree* rbt, int key); // The red-black tree looks for the node and retrieves the node data
RBTreeNode * RBTree_Insert(RBTree *rbt, int key, void *data); // Insert a new node
int  RBTree_Erase(RBTree *rbt, int key); // Delete the nodes in the red-black tree
void RBTree_EraseNode(RBTree *rbt, RBTreeNode *node); // Delete red-black tree by node
int  RBTree_CustomErase(RBTree *rbt, const void *keydata); // Delete nodes with specified data
RBTreeNode * RBTree_CustomSearch(RBTree* rbt, const void *keydata); // The red-black tree looks up the node according to the specified data
void*        RBTree_CustomGetData(RBTree* rbt, const void *keydata); // Get the specified node data
RBTreeNode * RBTree_CustomInsert(RBTree *rbt, const void *keydata, void *data); // Insert data as specified
Copy the code

The structure design

The following structure refers to the nginx structure design

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

Compare this to the node structure design in Linux

struct rb_node
{
    unsigned long  rb_parent_color;
#define    RB_RED        0
#define    RB_BLACK    1
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
Copy the code

The rb_parent_color field contains both the address of the parent node and the color of the parent node. (Take advantage of memory alignment features).