1 Red-black tree characteristics
- Each node is either black or red.
- The root node is black.
- Each leaf node (
NIL(It’s black.[Note: here the leaf node refers to empty (NilorNULL) leaf nodes! ]- If a node is red, its children must be black.
- All paths from a node to its descendants contain the same number of black nodes.
2 Build a red-black tree
2.1 Red-black tree node structure
// If you are not working hard, you are working hard
typedef struct RBTreeNode {
int data; / / data domain
int color; //0 black 1 red
struct RBTreeNode *parent;// Parent node
struct RBTreeNode *left; // Left child
struct RBTreeNode *right; // Right child
} RBTreeNode;
Copy the code2.2 Newly inserted self-equilibrium analysis
Insert root node @do into black 8(red) => 8(black) 2. Insert is a root node At this time depends on the color of the father and uncle (a). His father is black @ do then insert does not destroy the red-black tree balance, can be inserted directly the Parent | 8 (black) / 4 (red) (2). The father is red (and the grandfather must be black) depending on the uncle color [1]. Uncle is red (then uncle must have no children) @do father uncle is black, Red grandfather, grandfather of recursive self balancing the Parent the Parent | | 8 (black) 8 (red) / \ \ 4 (red) 10 (red) = > 4 (black) to 10 (black) = > reblace (8) / / 2 (red) 2 (red) [2]. Nil is more common. Black appears in bottom-to-top recursive reblace [1] depending on whether the father is the left node of the grandfather and whether the insertion node is in the left or right tree of the father. 1. Left node where father is grandfather 1.1: The new node will be placed in the left tree of the parent at @do and put the parent in black and the grandfather in red, To grandfather right-lateral Parent the Parent the Parent | | | 8 (black) grandfather left red (red) 4 (black)/father buy black/to 8 right / \ 4 (red) = > 4 (black) = > 2 (red) 8 (red) / / 2 (red) 2 (red) 1.2 Insert the new node in the father's right tree @ do into 1.1 scene Parent the Parent the Parent the Parent | | | | 8 (black) 8 (black) grandfather left red (red) 5 (black)/into/father buy black 1.1 / for 8 right / \ 4 (red) = > 5 (red) 5 (black) = = > > 4 (red) 8 (red), / / 5 (red) 4 (red) 4 (red) 2. 2.1 The newly inserted node in the father's right tree @do is set black for the father and red for the grandfather. To grandfather left handed the Parent the Parent the Parent | | | 8 (black) grandfather left red (red) 10 (black) buy black \ \ father of eight sinistral / \ 10 (red) 10 (black) = = > > 8 (red) 12 (red) \ \ 12 (red) 12 (red) 2.2 Insert the new node in the father's right tree into 2.1 scene Parent the Parent the Parent the Parent | | | | 8 (black) 8 (black) grandfather left red (red) 9 (black) buy black \ \ into \ 2.1 father of eight sinistral / \ 10 (red) = > 9(red) => 9(black) => 8(red) 10(red) / \ \ 9(red) 10(red) 10(red) 10(red) 10(red)Copy the code2.3 a left-handed
/** * left-handed * parent parent * 8 12 * 4 12 8 50 * 9 50 => 4 9 70 * 70 */
RBTreeNode *left_rotation(RBTreeNode *root)
{
struct RBTreeNode *new_root;
new_root = root->right;
root->right = new_root->left;
// Set the parent of 9 to the old root, i.e. 8
if(new_root->left ! =NULL)
{
new_root->left->parent = root;
}
// The parent of the new root is the old parent
new_root->parent = root->parent;
// Then handle the parent of the old root
if (root->parent == NULL)
{
// The old root is the root node
new_root->parent = NULL;
}else{
// Judge your father
if (new_root->parent->left == root)
{
new_root->parent->left = new_root;
}else{
new_root->parent->right = new_root;
}
}
root->parent = new_root;
new_root->left = root;
return new_root;
}
Copy the code2.4 a right-handed
/** * right-handed * parent parent * 8 4 * 4 12 2 8 * 2 6 => 1 6 12 * 1 */
RBTreeNode *right_rotation(RBTreeNode *root)
{
struct RBTreeNode *new_root;
new_root = root->left;
root->left = new_root->right;
// Set the parent of 6 to the old root, that is, 8
if(new_root->right ! =NULL)
{
new_root->right->parent = root;
}
// The parent of the new root is the old parent
new_root->parent = root->parent;
// Then handle the parent of the old root
if (root->parent == NULL)
{
// The old root is the root node
new_root->parent = NULL;
}else{
// Judge your father
if (new_root->parent->left == root)
{
new_root->parent->left = new_root;
}else{
new_root->parent->right= new_root;
}
}
new_root->right = root;
root->parent = new_root;
return new_root;
}
Copy the code2.5 insert
The difference between AVL tree and AVL tree is that the height of AVL tree is passed recursively from bottom to top after insertion, and then the balance is restored by checking from top to bottom after insertion. However, after a node is inserted into a red-black tree, it is impossible to judge the balance only by the root node of the original tree before it is balanced. Of course, the node to be balanced can also be found by traversing from top to bottom, but this is very inefficient. Therefore, a global variable is used to store the newly inserted node, and only this node can be balanced when balancing.
RBTreeNode *getNode(int data, RBTreeNode *parent)
{
struct RBTreeNode *node;
node = (struct RBTreeNode *)malloc(sizeof(struct RBTreeNode));
node->data = data;
node->parent= parent;
node->color = 1;
node->right = NULL;
node->left = NULL;
LastRBTreeNode = node;
return node;
}
RBTreeNode *insert(RBTreeNode *root, int data, RBTreeNode *parent)
{
if (NULL == root)
{
return getNode(data, parent);
}
int need_fix = 0;
if (data >= root->data)
{
root->right = insert(root->right, data, root);
}else{
root->left = insert(root->left, data, root);
}
return root;
}
RBTreeNode *inserRB(RBTreeNode *root, int data, RBTreeNode *parent)
{
root = insert(root,data,parent);
root = rebalance(root,LastRBTreeNode);
return root;
}
Copy the code2.6 the balance
RBTreeNode *rebalance(RBTreeNode *head, RBTreeNode *root)
{
if (root->parent == NULL)
{
root->color = 0;
return root;
}
// The father is not NULL
// If the father is black, the insertion does not break the balance
if (root->parent->color == 0)
{
return head;
}
// A red father must have a black grandfather
RBTreeNode *parent, *gparent, *uncle;
parent = root->parent;
gparent = root->parent->parent;
if (parent == gparent->left)
{
uncle = gparent->right;
// If uncle is red, it must be red if it is not NULL
if(uncle ! =NULL) {// Set black for father and uncle, red for grandfather, recursive self-balance for grandfather
gparent->color = 1;
parent->color = 0;
uncle->color = 0;
return rebalance(head, gparent);
}else{
// If uncle is black, Nil is black
// Grandfather is red, father is black, and grandfather is right-handed
gparent->color = 1;
parent->color = 0;
if (root == parent->right)
{
//1. Root switches with the parent node and sets the parent node to the left node of the new root, that is, to 1.1
gparent->left = root;
root->parent = gparent;
root->left = parent;
parent->parent = root;
parent->right = NULL;
}
returngparent == head ? right_rotation(gparent) : head; }}else{
uncle = gparent->left;
// If uncle is red, it must be red if it is not NULL
if(uncle ! =NULL) {// Set black for father and uncle, red for grandfather, recursive self-balance for grandfather
gparent->color = 1;
parent->color = 0;
uncle->color = 0;
return rebalance(head, gparent);
}else{
// If uncle is black, Nil is black
// Grandfather is red, father is black, and grandfather is right-handed
gparent->color = 1;
parent->color = 0;
if (root == parent->left)
{
//1. Root switches with the parent node and sets the parent node to the left node of the new root, that is, to 2.1
gparent->right = root;
root->parent = gparent;
root->right = parent;
parent->parent = root;
parent->left = NULL;
}
returngparent == head ? left_rotation(gparent) : head; }}}Copy the code3 Deleting a Node
3.1 Node Deletion Analysis
The deleted node has no left and right nodes (1). In special cases, the deleted node is the root node (2). (3). If the deleted node is black, there must be sibling nodes depending on whether the deleted node is in the parent's left or right tree, as well as sibling nodes [1]. The deleted node in the parent's left tree 4 is the deleted node.1. The sibling node is black. By 8,4,12,20, then delete 20 structure) 8 (black) brothers buy red (black) / \ = > \ 4 (black) 12 (black) 12 (red) 1.1.2 father Parent node is red the Parent buy black | | father 8 (red) brothers buy red (black) / \ = > \ 4(black) 12(black) 12(red) 1.2 Sibling nodes have only one right node, Right node will be red Parent the Parent the Parent | | | 8 color (red to black) father brother fu right 8 (red to black) 12 (black) / \ = > sinistral / \ \ to 8 4 (black) 12 (black) 12 (black) = > 8 (red to black) 20 \ (red to black) \ 20(red) 20(red or black) 1.3 Sibling nodes have only one left node, Left node will be red into the scene 1.2 Parent the Parent the Parent | | | 8 (red to black) into a scene of 1.2 8 (red to black) 10 (black) color / \ father brother, brother left rear black \ to 8 sinistral / \ 4 (black) 12 (black) = > 10 (black) => 8(red or black) 12(red or black) / 10(red) 12(red or black) Inevitably are red into the scene 1.2 Parent the Parent the Parent | | | 8 (red to black) 8 (red to black) 12 (black)/color fu brother right \ \ father of eight sinistral / \ 4 (black) 12 (black) = > 12 (black) = > 8 (red to black) 12 (red to black) / \ \ \ 10 (red) 20 (red) 10 (red) 20 (red to black) 10 (red) 2. Brother nodes is red Is father than for black, there will be two black brothers node (this kind of situation can through 8,4,12,10,20,30 delete 30 structure) Parent the Parent the Parent buy black | | brother | 8 (black) brother left buy red (black) (black) / \ Are set to 1.4 \ to 8 sinistral / \ 4 (black) 12 (red) = > 12 (black) = > 8 (black) 20 (black) / \ \ \ 10 (black) (black) to 10 (red) 20 (black) to 10 (red) [2]. The deleted node in the parent's right tree 12 is the mirror image of the deleted node and [1]. The sibling node is black.1.1 The sibling node has no left and right nodes. 1.1.1 The parent node is black and the direct sibling node is red. By 8,4,12,20, then delete 20 structure) 8 (black) brothers buy red (black) / \ = > / 4 (black) 12 (black) 4 (red) 1.1.2 father Parent node is red the Parent buy black | | father 8 (red) brothers buy red (black) / \ = > / 4(black) 12(black) 4(red) 1.2 Sibling nodes have only one left node, Left node will be red Parent the Parent the Parent | | | 8 color (red to black) father brother fu left 8 (red to black) 4 (black) / \ = > / to 8 right / \ 4 (black) 12 (black) 4 (black) = > 2 (red to black) 8 (red to black) / / 2(red) 2(red or black) 1.3 The sibling node has only one right node, Node for red right into the scene 1.2 Parent the Parent the Parent | | | 8 (red to black) into a scene of 1.2 8 (red to black) 6 (black) color / \ father brother fu right/to 8 right / \ 4 (black) 12 (black) 6 (black) = = > > 4(Red or black) 8(red or black) \ / 6(red) 4(red or black) 1.4 Sibling nodes have left and right nodes, Inevitably are red into the scene 1.2 Parent the Parent the Parent | | | 8 (red to black) 8 (red to black) 4 (black) color / \ father brother fu 8 dextral left/to / \ 4 (black) 12 (black) = > 4 (black) = > 2 (red to black) / \ / \ / 2(red) 6(red) 2(red) 6(red) 6(red) 6(red) 2. Brother nodes is red Is father than for black, there will be two black brothers node (this kind of situation can through 8,4,12,2,6,1 then delete 1 structure) Parent the Parent the Parent buy black | | brother | 8 (black) brother right red (black) 4 (black) / \ to 1.4 for setting / to 8 right / \ 4 (red) 12 (black) = > 4 (black) = > 2 (black) 8 (black) / \ \ / 2 (black) 6 (black) 2 (black) 6 (red) (red). The deleted node has only one left node, so according to the red-black tree characteristics, the deleted node must be black, and the left node is red (I). Deleted node in the left tree 4 is for removing the Parent the Parent the Parent | | | 8 (red to black) left rear black 8 (red to black) delete 4, On 8 (red to black) / 2 \ = > / = > / \ 4 (black) 12 (black) 4 (black) 12 (black) 2 (black) 12 (black) / / 2 (red) 2 (black) (a). Be deleted nodes in the right tree 12 is the Parent node is to be deleted the Parent the Parent | | | 8 (red to black) left rear black 8 (red to black) delete 12, On October 8 (red to black) / \ = > / = > / \ 4 (black) 12 (black) 4 (black) 12 (black) 2 (black) to 10 (black) / / 10 10 (black) 3 (red). The deleted node has only one right node, which is the mirror relationship with the second node. If the node to be deleted exists on both the left and right nodes, delete the node and replace it with its predecessor and successor nodesCopy the code3.2 Finding precursor/successor nodes
RBTreeNode *FindMin(RBTreeNode *root)
{
if (NULL == root)
{
return NULL;
}
if (root->left == NULL)
{
return root;
}else{
returnFindMin(root->left); }}RBTreeNode *FindMax(RBTreeNode *root)
{
if (NULL == root)
{
return NULL;
}
if (root->right == NULL)
{
return root;
}else{
returnFindMax(root->right); }}Copy the code3.3 Delete node code implementation
RBTreeNode *Delete(RBTreeNode *head, RBTreeNode *root, int target)
{
if (NULL == root)
{
return NULL;
}
if (target > root->data){
return Delete(head, root->right, target);
}else if (target < root->data)
{
return Delete(head, root->left, target);
}else{
// It is the same case
RBTreeNode *parent, *brother;
parent = root->parent;
int head_flag = parent == head;
int red_flag = root->color == 1;
// There are no left or right nodes
if (root->left == NULL && root->right == NULL)
{
// Delete the root node in special cases
if (parent == NULL)
{
return NULL;// Delete itself
}
// The deleted node is in the left tree
if (root == parent->left)
{
parent->left = NULL;
free(parent->left);
root = NULL;
free(root);
// The node to be deleted is in red
if (red_flag) return head;
// If the node to be deleted is black, sibling nodes must exist. Sibling nodes may be black or red
brother = parent->right;
//1. Sibling nodes have no left and right nodes
if (brother->left == NULL && brother->right == NULL)
{
brother->color = 1;
return head;
}else if(brother->left == NULL&& brother->right ! =NULL)
//2. The sibling node must be black and the right node must be red
{
brother->right->color = parent->color;
parent = left_rotation(parent);
return head_flag ? parent : head;
}else if(brother->left ! =NULL && brother->right == NULL)
//3. Sibling nodes have only one left node. Sibling nodes must be black and red
{
// Convert to Scenario 2
parent->right = brother->left;
/ / for brother - > left
brother->left->right = brother;
brother->left->color = 0;
brother->left->parent= parent;
/ / for brother
brother->parent = brother->left;
brother->color = parent->color;
brother->left = NULL;
parent = left_rotation(parent);
return head_flag ? parent : head;
}else
//4. The sibling node has left and right nodes
{
// Brother black, there must be two red
if (brother->color == 0)
{
brother->right->color = parent->color;
}else{
If a brother is red, two must be black, and the father must be black
brother->color = 0;
brother->left->color = 1;
}
parent = left_rotation(parent);
returnhead_flag ? parent : head; }}else
// The deleted node is mirrored in the right tree and the left tree
{
parent->right = NULL;
free(parent->right);
root = NULL;
free(root);
// The node to be deleted is in red
if (red_flag) return head;
// If the node to be deleted is black, there must be black sibling nodes
brother = parent->left;
//1. Sibling nodes have no left and right nodes
if (brother->left == NULL && brother->right == NULL)
{
brother->color = 1;
return head;
}else if(brother->left ! =NULL && brother->right == NULL)
//2. Sibling nodes have only one left node
{
brother->left->color = parent->color;
parent = right_rotation(parent);
return head_flag ? parent : head;
}else if(brother->left == NULL&& brother->right ! =NULL)
//3. Sibling nodes have only one right node
{
// Convert to Scenario 2
parent->left = brother->right;
/ / for brother - > right
brother->right->left = brother;
brother->right->color = 0;
brother->right->parent= parent;
/ / for brother
brother->parent = brother->right;
brother->color = parent->color;
brother->right = NULL;
parent = right_rotation(parent);
return head_flag ? parent : head;
}else
//4. The sibling node has left and right nodes
{
// Brother black, there must be two red
if (brother->color == 0)
{
brother->left->color = parent->color;
}else{
If a brother is red, two must be black, and the father must be black
brother->color = 0;
brother->right->color = 1;
}
parent = right_rotation(parent);
returnhead_flag ? parent : head; }}}else if(root->left ! =NULL && root->right == NULL)
// If there is only one left node, root must be black and the left node must be red
{
root->left->color = 0;
// The deleted node is in the left tree
if (root == parent->left)
{
parent->left = root->left;
root->left->parent = parent;
}else
// The deleted node is in the right subtree
{
parent->right = root->left;
root->left->parent = parent;
}
root = NULL;
free(root);
return head;
}else if (root->left == NULL&& root->right ! =NULL)
// If there is only one right node, root must be black and the right node must be red
{
printf("root null:\n");
root->right->color = 0;
// The deleted node is in the left tree
if (root == parent->left)
{
parent->left = root->right;
root->right->parent= parent;
}else
// The deleted node is in the right subtree
{
parent->right = root->right;
root->right->parent= parent;
}
root = NULL;
free(root);
return head;
}else
// Select a precursor or successor
// Successor node: deletes the smallest node in the right subtree of the node, that is, the leftmost node in the right subtree.
// Precursor node: Delete the largest node in the left subtree of the node, that is, the rightmost node in the left subtree.
// Use the successor node as a substitute node
{
RBTreeNode *min = FindMin(root->right);
root->data = min->data;
returnDelete(head, min, min->data); }}return head;
}
Copy the code4 Test code
4.1 Preorder traversal is used for verification
// preorder traversal
void preOrderTraverse(RBTreeNode *root)
{
if(root ! =NULL)
{
if(root->parent ! =NULL)
{
printf("%d color: %d parent:%d\n", root->data, root->color, root->parent->data);
}else{
printf("%d color: %d\n", root->data, root->color); } preOrderTraverse(root->left); preOrderTraverse(root->right); }}Copy the code4.2 Test Code
There are many scenarios and only one example is given here
int main(int argc, char const *argv[])
{
struct RBTreeNode *node;
//1.1 Test cases
node = NULL;
node = inserRB(node, 8.NULL);
node = inserRB(node, 4.NULL);
node = inserRB(node, 12.NULL);
node = inserRB(node, 2.NULL);
//node = inserRB(node, 20, NULL);
//node = inserRB(node, 30, NULL);
//node = inserRB(node, 14, NULL);
//node = inser(node, 4, NULL);
printf("***1 Test Case foreword ***: \n");
preOrderTraverse(node);
//node = Delete(node,node,30);
node = Delete(node,node,8);
printf("*** Test Case prefixes ***: \n");
preOrderTraverse(node);
return 0;
}
Copy the codeDone!