First, “Algorithm – Simple” N fork tree introduction

Two, “Algorithm – simple” red black tree rotation

Three, “Algorithm – Simple” red black tree insertion

4. Delete the red black tree of algorithm – Simple and Simple

One, foreword

Red-black Tree (R-B Tree), it is binary Tree, the most classical and the most complex data structure.


Red black tree application: \color{red}{red black tree application:}

  • STL is widely used in C++. Map and set are implemented by red-black tree.
  • The virtual memory space of the process is stored in a red-black tree. Each virtual memory space corresponds to a node of the red-black tree. The left pointer points to the adjacent virtual memory space, and the right pointer points to the adjacent high-address virtual memory space.
  • IO multiplexing epoll uses red-black tree organization to manage SOCKFD to support fast add, delete, change and query.
  • Nginx uses red-black tree management timer, because red-black tree is orderly, can quickly get the smallest distance from the current timer;
  • TreeMap and TreeSet in Java are also implemented by red-black tree. Starting with JDK8, HashMap also added a red-black tree.


Properties of red-black trees : \color{red}{red black tree features :}

  1. Each node is either black or red;
  2. The root node is black;
  3. Each leaf node (NIL) is black; Note: leaf nodes are NIL or NULL leaf nodes!
  4. If a node is red, its children must be black;
  5. All paths from a node to its descendants contain the same number of black nodes;

Its complexity lies in:

  • When inserting a node, it may violate the rules, thus requiring recursion.
  • When deleting a node, the adjustment is similar to that of inserting a node, but before the adjustment, a successor node needs to be found to replace it.

Therefore, we can see that the most complex adjustment is the operation after the node is deleted!

Rotation \color{red}{rotation} rotate! Whether you insert or delete, when you adjust, you rotate the subtree, and then you recurse up until you finally meet the characteristics of a red-black tree.

Second, the rotation

Left-handed rotation is based on a node where the whole node (along with its left and right subtrees) rotates to the left; Dextral rotation is based on a node that rotates to the right as a whole (along with its left and right subtrees);

2.1. Data structure

public class RBTree { private TreeNode root; public RBTree(TreeNode root) { this.root = root; } public static class TreeNode { public static final int BLACK = 0; public static final int RED = 1; public int value; public int color = BLACK; public TreeNode parent; public TreeNode left; public TreeNode right; public TreeNode(int value) { this.value = value; } public TreeNode(int value, TreeNode parent) { this.value = value; this.parent = parent; }}}Copy the code

2.2. Generate binary tree

{ private TreeNode getTree() { TreeNode head = new TreeNode(10); head.left = new TreeNode(5, head); head.left.left = new TreeNode(2, head.left); head.left.right = new TreeNode(8, head.left); head.right = new TreeNode(20, head); head.right.left = new TreeNode(16, head.right); head.right.right = new TreeNode(22, head.right); return head; } private void doPreTravel(TreeNode node) {if (node == null) {return; } System.out.println((node.parent == null ? "(root)" : "") + node.value); doPreTravel(node.left); doPreTravel(node.right); }} // doPreTravel(getTree()) // Print out (prior traversal: root -> left subtree -> right subtree) // 10, 5, 2, 8, 20, 16, 22Copy the code

As shown below (our subsequent rotations are based on the root node 10)

2.3 left rotation (the algorithm only considers rotation, regardless of whether the 5 rules are met)

public class RBTree { private TreeNode root; / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * (1)  | (2) * g(10) u(20) | g g * / \ / \ | / / * p(5) u(20) => g(10) z(22) | p => u * / \ / \ / \ | \ / * c(2) x(8) y(16) z(22) p(5) y(16) | u p * / \ | * c(2) x(8) | * | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / public void rotateLeft(TreeNode parent) { TreeNode right = parent.right; Parent. right = right. Left; // g. right node = y if (right.left! = null) { right.left.parent = parent; // parent = g} // parent.parent = parent.parent; // u. Parent = g. Parent if (parent. Parent! = null) { if (parent.parent.left == parent) { parent.parent.left = right; // Grandfather node. Left node = u} else {parent.parent.right = right; } } else { root = right; } // parent = parent.parent = right; G. Parent = u right. Left = parent; // u. Left node = g}}Copy the code

2.4. Dextral rotation (the algorithm only considers rotation, regardless of whether the 5 rules are met)

public class RBTree { private TreeNode root; / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * (1)  | (2) * g(10) p(5) | p g * / \ / \ | / / \ * p(5) u(20) => c(2) g(10) | g => x p * / \ / \ / \ | / * c(2) x(8) y(16) z(22) x(8) u(20) | x * / \ | * y(16) z(22) | * | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / private void rotateRight(TreeNode parent) { TreeNode left = parent.left; Parent. left = left. Right; // g. left node = x if (left. Right! = null) { left.right.parent = parent; // x. Parent = g} // left. Parent = parent; // parent = g. parent if (parent. Parent! = null) { if (parent.parent.left == parent) { parent.parent.left = left; } else { parent.parent.right = left; } } else { root = left; } // parent.parent = left; G. Parent = p left. Right = parent; P. Right node = g}}Copy the code

Github red black tree complete source code