Similar to AVL tree, red black tree is also a balanced binary search tree, but the definition of balance is different, red black tree each node has a color value, either red or black, balance also refers to black balance; The red-black tree that we’ve implemented is a left-leaning red-black tree, and the analogy is 2-3 trees;

First, let’s list five properties of red-black trees:

  1. Each node is either red or black;
  2. The root node must be black;
  3. The leaf node must be black, and the leaf node here refers to the empty node.
  4. The child of a red node must be a black node;
  5. The number of black nodes passing from any node to the leaf node is equal;

It can be seen from the fifth property that red-black tree is a black-balanced tree.

1. Basic properties of Node Node and red-black tree

To facilitate the use of red-black trees for mapping maps, generics are set to K and V, the same as AVL; The underlying implementation of TreeMap in the Java standard library is a red-black tree;

The Node class includes key, value, left and right child nodes, and a color attribute to maintain the color of the Node and ultimately maintain black balance. We use height to maintain balance in AVL;

The root attribute represents the root node of the red-black tree. Size represents the number of elements in the red-black tree;

GetSize returns the number of elements in the red-black tree. IsEmpty returns whether the red-black tree isEmpty;

IsRed Checks whether the node is a red node. The red node returns true, and the black node returns false.

public class RBTree<K extends Comparable<K>, V> { private static final boolean RED = true; private static final boolean BLACK = false; private class Node{ public K key; public V value; public Node left, right; public boolean color; public Node(K key, V value){ this.key = key; this.value = value; left = null; right = null; color = RED; } } private Node root; private int size; public RBTree(){ root = null; size = 0; } public int getSize(){ return size; } public boolean isEmpty(){ return size == 0; } private Boolean isRed(node node){if(node == null) return BLACK; return node.color; },,}Copy the code

2, left rotation, right rotation and color flipping

Left rotation, right rotation, and color flipping are the three subprocesses used to maintain the black balance of the red-black tree when adding elements;

// node x // / T1 x ---------> node T3 // / \ // T2 T3 T1 T2 private node leftRotate(node node){node x  = node.right; // Rotate node.right = x.left; x.left = node; x.color = node.color; node.color = RED; return x; } // node x // // T2 -------> y node // // // // y T1 T1 T2 private node rightRotate(node node){node x = node.left; // Rotate node.left = x.right; x.right = node; x.color = node.color; node.color = RED; return x; } private void flipColors(Node Node){node.color = RED; node.left.color = BLACK; node.right.color = BLACK; }Copy the code

3. Add elements to the red-black tree

Because the red-black tree is also a binary search tree, the first half of the added element is the same as the binary search tree, and is added recursively to the appropriate location;

After adding elements, maintain black balance by rotating left, rotating right, and color flipping;

// Add new element (key, value) public void add(K key, V value){root = add(root, key, value); root.color = BLACK; // Insert an element (key, value) into a red-black tree with node as the root. Private Node add(Node Node, K key, V value){if(Node == null){size ++; return new Node(key, value); } if(key.compareTo(node.key) < 0) node.left = add(node.left, key, value); else if(key.compareTo(node.key) > 0) node.right = add(node.right, key, value); else // key.compareTo(node.key) == 0 node.value = value; if (isRed(node.right) && ! isRed(node.left)) node = leftRotate(node); if (isRed(node.left) && isRed(node.left.left)) node = rightRotate(node); if (isRed(node.left) && isRed(node.right)) flipColors(node); return node; }Copy the code

Find and modify elements from the red-black tree

Searching and modifying elements does not involve the maintenance of node color, so no special process is required, so it is basically the same as the binary search tree in Data Structure part 05.

Private node getNode(node node, K key){if(node == null) return null; if(key.equals(node.key)) return node; else if(key.compareTo(node.key) < 0) return getNode(node.left, key); else // if(key.compareTo(node.key) > 0) return getNode(node.right, key); } public boolean contains(K key){ return getNode(root, key) ! = null; } public V get(K key){ Node node = getNode(root, key); return node == null ? null : node.value; } public void set(K key, V newValue){ Node node = getNode(root, key); if(node == null) throw new IllegalArgumentException(key + " doesn't exist!" ); node.value = newValue; }Copy the code

5. Delete elements from the red-black tree

The principle of deleting elements from red-black trees is consistent with binary search trees, but the red-black nature of nodes needs to be maintained after deleting elements. This part is too complicated, and our deletion part does not realize the maintenance of nodes after deleting elements. The deletion method used here is the same as a normal binary search tree;

Private node minimum(node node){if(node. Left == null) return node; return minimum(node.left); Private node removeMin(node node){if(node. Left == null){node rightNode  = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } // Remove the key from the binary search tree public V remove(K key){Node Node = getNode(root, key); if(node ! = null){ root = remove(root, key); return node.value; } return null; } private Node remove(Node node, K key){ if( node == null ) return null; if( key.compareTo(node.key) < 0 ){ node.left = remove(node.left , key); return node; } else if(key.compareTo(node.key) > 0 ){ node.right = remove(node.right, key); return node; } else{// key.compareTo(node.key) == 0 // If (node.left == null){node rightNode = node.right; node.right = null; size --; return rightNode; } // If (node.right == null){node leftNode = node.left; node.left = null; size --; return leftNode; } // If the left and right subtrees of the Node to be deleted are not empty // Find the minimum Node that is bigger than the right subtree of the Node to be deleted // Use this Node to replace the location of the Node to be deleted. successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; }}Copy the code

6, red black tree all code

public class RBTree<K extends Comparable<K>, V> { private static final boolean RED = true; private static final boolean BLACK = false; private class Node{ public K key; public V value; public Node left, right; public boolean color; public Node(K key, V value){ this.key = key; this.value = value; left = null; right = null; color = RED; } } private Node root; private int size; public RBTree(){ root = null; size = 0; } public int getSize(){ return size; } public boolean isEmpty(){ return size == 0; } private Boolean isRed(node node){if(node == null) return BLACK; return node.color; } // node x // // T1 x ---------> node T3 // / \ // T2 T3 T1 T2 private node leftRotate(node node){node  x = node.right; // Rotate node.right = x.left; x.left = node; x.color = node.color; node.color = RED; return x; } // node x // // T2 -------> y node // // // // y T1 T1 T2 private node rightRotate(node node){node x = node.left; // Rotate node.left = x.right; x.right = node; x.color = node.color; node.color = RED; return x; } private void flipColors(Node Node){node.color = RED; node.left.color = BLACK; node.right.color = BLACK; } // Add a new element to the tree (key, value) public void add(K key, V value){root = add(root key, value); root.color = BLACK; // Insert an element (key, value) into a red-black tree with node as the root. Private Node add(Node Node, K key, V value){if(Node == null){size ++; return new Node(key, value); } if(key.compareTo(node.key) < 0) node.left = add(node.left, key, value); else if(key.compareTo(node.key) > 0) node.right = add(node.right, key, value); else // key.compareTo(node.key) == 0 node.value = value; if (isRed(node.right) && ! isRed(node.left)) node = leftRotate(node); if (isRed(node.left) && isRed(node.left.left)) node = rightRotate(node); if (isRed(node.left) && isRed(node.right)) flipColors(node); return node; } private node getNode(node node, K key){if(node == null) return null; if(key.equals(node.key)) return node; else if(key.compareTo(node.key) < 0) return getNode(node.left, key); else // if(key.compareTo(node.key) > 0) return getNode(node.right, key); } public boolean contains(K key){ return getNode(root, key) ! = null; } public V get(K key){ Node node = getNode(root, key); return node == null ? null : node.value; } public void set(K key, V newValue){ Node node = getNode(root, key); if(node == null) throw new IllegalArgumentException(key + " doesn't exist!" ); node.value = newValue; } private node minimum(node node){if(node. Left == null) return node; return minimum(node.left); Private node removeMin(node node){if(node. Left == null){node rightNode  = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } // Remove the key from the binary search tree public V remove(K key){Node Node = getNode(root, key); if(node ! = null){ root = remove(root, key); return node.value; } return null; } private Node remove(Node node, K key){ if( node == null ) return null; if( key.compareTo(node.key) < 0 ){ node.left = remove(node.left , key); return node; } else if(key.compareTo(node.key) > 0 ){ node.right = remove(node.right, key); return node; } else{// key.compareTo(node.key) == 0 // If (node.left == null){node rightNode = node.right; node.right = null; size --; return rightNode; } // If (node.right == null){node leftNode = node.left; node.left = null; size --; return leftNode; } // If the left and right subtrees of the Node to be deleted are not empty // Find the minimum Node that is bigger than the right subtree of the Node to be deleted // Use this Node to replace the location of the Node to be deleted. successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; }}}Copy the code