This is the first article I participated in beginners’ introduction

Since the red-black tree implementation needs to be refactored, it is now necessary to concentrate and compare common red-black tree implementations.

The plan is divided into the following parts

  1. Red-black tree requirements analysis
  2. Common red-black tree implementation analysis
    1. Linux rbtree
    2. STL rbtree
    3. ngnix rbtree
    4. .
  3. Compare and choose a better red-black tree implementation
  4. implement

This is the first part, the demand analysis of red-black tree.

First, the definition of red-black tree

Before we start analyzing and comparing the implementation methods, let’s go through the definition briefly

A binary search tree is defined as a red-black tree if it satisfies the following properties: (1) each node is either red or black (add one memory bit for color); (2) Each leaf node (null pointer NIL) is black; (3) If a node is red, its children should be black; (4) There are the same number of black nodes on each simple path from any given node to its descendants.

(Pictures from 30 images that take you to the bottom of a red-black tree – Jianshu.com)

Ii. Overview of existing functions:

Qualifiers and types Functions and specifications
void RBTree_Init(RBTree *rbt);

Initialize 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);

Gets the next node
RBTreeNode * RBTree_Search(RBTree* rbt, int key);

Red-black trees find nodes
void* RBTree_GetData(RBTree* rbt, int key);

A red-black tree looks up a node and retrieves data from that node
RBTreeNode * RBTree_Insert(RBTree *rbt, int key, void *data);

Insert a new node
int RBTree_Erase(RBTree *rbt, int key);

Delete nodes in a red-black tree
void RBTree_EraseNode(RBTree *rbt, RBTreeNode *node);

Delete red-black tree by node
int RBTree_CustomErase(RBTree *rbt, const void *keydata);

Deletes nodes with specified data
RBTreeNode * RBTree_CustomSearch(RBTree* rbt, const void *keydata);

A red-black tree finds nodes according to the specified data
void* RBTree_CustomGetData(RBTree* rbt, const void *keydata);

Gets the specified node data
RBTreeNode * RBTree_CustomInsert(RBTree *rbt, const void *keydata, void *data);

Insert as specified

RBTree_Init

void RBTree_Init(RBTree *rbt);
Copy the code

Initialize the

Parameter Description:

  • rbt– Target red black tree

Return description:

  • There is no

RBTree_Destroy

void RBTree_Destroy(RBTree *rbt);
Copy the code

Destroy the red black tree

Parameter Description:

  • rbt– Target red black tree

Return description:

  • There is no

RBTree_First

 RBTreeNode *RBTree_First(const RBTree *rbt);
Copy the code

Returns the first node of the red-black tree

Parameter Description:

  • rbt– Target red black tree

Return description:

  • Returns the first red-black tree node

RBTree_Next

RBTreeNode *RBTree_Next(const RBTreeNode *node);
Copy the code

Returns the next node of the red-black tree

Parameter Description:

  • node– Red black tree node

Return description:

  • Returns the next node of the input node

RBTree_Search

RBTreeNode* RBTree_Search(RBTree* rbt, int key);
Copy the code

Call rb_search_auxiliary() to search the red-black tree

Parameter Description:

  • rbt– Target red black tree
  • key– Search sequence number

Return description:

  • Returns the node found

RBTree_GetData

void* RBTree_GetData(RBTree* rbt, int key);
Copy the code

Call rb_search_AUXILIARY () to search the red-black tree to find the specified node and return its data.

Parameter Description:

  • rbt– Target red black tree
  • key– Search sequence number

Return description:

  • Returns the (void*) data of the node found

RBTree_Insert

RBTreeNode* RBTree_Insert(RBTree *rbt, int key, void *data);
Copy the code

Insert new node

Parameter Description:

  • rbt– Target red black tree
  • key– Search sequence number
  • rbt– The value of the new node

Return description:

  • Returns the inserted node

RBTree_Erase

int RBTree_Erase(RBTree *rbt, int key);
Copy the code

Delete nodes by serial number

Parameter Description:

  • rbt– Target red black tree
  • key– Node number of the search

Return description:

  • Returns 0 on success, -1 on failure

RBTree_EraseNode

void RBTree_EraseNode(RBTree *rbt, RBTreeNode *node);
Copy the code

Delete nodes by node

Parameter Description:

  • rbt– Target red black tree
  • node– Target node

Return description:

RBTree_CustomErase

  int RBTree_CustomErase(RBTree *rbt, const void *keydata);
Copy the code

Custom operation – Delete nodes by key data

Parameter Description:

  • rbt– Target red black tree
  • keydata– Target data

Return description:

  • Returns 0 on success, -1 on failure

RBTree_CustomSearch

  RBTreeNode* RBTree_CustomSearch(RBTree* rbt, const void *keydata);
Copy the code

Custom operations – Search nodes by key data

Parameter Description:

  • rbt– Target red black tree
  • keydata– Target data

Return description:

  • Returns the node found, or null if not found

RBTree_CustomGetData

  void* RBTree_CustomGetData(RBTree* rbt, const void *keydata);
Copy the code

Custom operation – Search node by key data returns its value

Parameter Description:

  • rbt– Target red black tree
  • keydata– Target data

Return description:

  • Returns the value of the node found

RBTree_CustomInsert

  RBTreeNode* RBTree_CustomInsert(RBTree *rbt, const void *keydata, void *data);
Copy the code

Custom operation – Insert nodes according to key data

Parameter Description:

  • rbt– Target red black tree
  • keydata– Target data
  • data– Insert data

Return description:

  • Returns the newly inserted node

Conclusion:

Through requirements analysis, I clearly understand what I need to specifically manage blood operations, and specific input and output, I will be in the following source code analysis to further focus on how to achieve these operations.