Red black tree is evolved from fourth-order B tree. Understanding the left-rotation and right-rotation of AVL tree and the up-overflow and down-overflow of fourth-order B tree will help us learn red black tree twice with half the effort
Multi – path balanced search tree – B tree
-
Each node, all subtrees are the same height
-
M-order B-tree means that the number of child nodes of a node is at most M. 2-3 trees are third-order B-trees, 2-3-4 trees are fourth-order B-trees, and so on
-
Limit the number of elements in a node:
- Root node: 1 <= x <= m-1
- Non-root node :(⌈m/2⌉ -1) <= x <= (m-1);
-
Limit on the number of children of a node:
- 2 <= x <= m
- ⌈m/2⌉ <= x <= m
-
Add element: The new element must be added to the leaf node
-
Overflow: When adding elements to a node causes the number of elements on that node to exceed the limit. In this case, the middle element (the MTH from left to right) of the node is moved up along the parent pointer, and the elements on the left and right are used as the left and right child nodes of the element
This is the only case where a B-tree can grow taller, where overflows propagate to the root node when elements are added
-
Remove elements
- When deleting an element from a leaf node, simply remove it
- When an element in a non-leaf node is deleted, its precursor/successor element is overwritten and then its precursor/successor element is deleted
- The precursor or successor of an element must be in the leaf node
- The actual deletion must occur in the leaf node
-
Underflow:
-
Overflow: After an element is deleted, the number of elements on the node where the element resides changes to (⌊m/2⌋ -2).
-
If the underflow node has a neighboring node of the same layer with the number of elements (⌊m/2⌋) or more, you can “borrow” an element from this node
-
Add A copy of the parent node element between the underflow node A and the adjacent node B that meets the conditions to A
-
Overrides the parent element with either the largest (if B is to the left of A) or the smallest (if B is to the right of A) element in B
-
Delete the maximum/minimum element in B
-
-
If the neighboring node elements of the same layer of the underflow node are less than or equal to (⌊m/2⌋-1), then it cannot borrow, merge the underflow node and any neighboring node, and pull down the parent node element between them
- After merging, the number of node elements is (⌊m/2⌋ + ⌊m/2⌋ -2), not more than (M-1).
- This operation may cause underflow on the parent node, which may propagate up the parent node
If a downflow adjustment pulls off a parent node element so that the parent node has no elements, the height of the tree is reduced by one
-
-
Add the 22 elements 1~22 to the fourth-order B tree (2-3-4 tree) in sequence:
-
Delete 22 to 1 in order
Red and black tree
Properties of red-black trees
The tree in the figure above is not a red-black tree because the green path has only two black nodes while the other red path has three black nodes, which does not comply with property 5
Red-black versus two-three-four
When the leaf node elements of tree B are red black red, black red, red black and black respectively. (See red-black tree as a two-three-four tree, only the black node can become a B-tree node independently, and its left and right red child nodes can be integrated into the B-tree node)
Add elements
Dye it red and add it to the leaf nodes
The positioning logic of the new element is the same as that of the BST, but note the adjustment logic after the addition.
Case by case discussion
1. Add the first element
Dye the knobs black
2. The added node is the child node of the black node
Dye it red and add without adjustment
3. The added node is the child of the red node, but does not need to be overflowed
LL/RR, single screw
RL/LR, twin twist
4. The added node is used as the red child node and must be overflowed
LL overflow
The RR overflow
LR overflow
RL overflow
Code implementation
Making: github.com/zanwen/algo…
Binary search tree
package top.zhenganwen.learn.algorithm.datastructure.tree;
import top.zhenganwen.learn.algorithm.commons.printer.BinaryTreeInfo;
import top.zhenganwen.learn.algorithm.commons.printer.BinaryTrees;
import java.util.*;
import static java.util.Objects.isNull;
/ * * *@author zhenganwen
* @datePass 2019/11/6 when * /
public class BinarySearchTree<E> implements BinaryTreeInfo {
protected Node<E> root;
private int size;
protected Comparator<E> comparator;
public BinarySearchTree(a) {}public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}
public void add(E element) {
nonNullCheck(element);
if (root == null) {
root = createNode(element, null);
size++;
afterAdd(root);
return;
}
Node<E> parent = root, cur = root;
int compare = 0;
while(cur ! =null) {
parent = cur;
compare = compare(element, cur.element);
cur = compare > 0 ? cur.right : compare < 0 ? cur.left : cur;
if (cur == parent) {
cur.element = element;
return;
}
}
Node<E> node = createNode(element, parent);
if (compare > 0) {
parent.right = node;
} else {
parent.left = node;
}
size++;
afterAdd(node);
}
protected void afterAdd(Node<E> node) {}protected Node<E> createNode(E element, Node<E> parent) {
return new Node<>(element, parent);
}
public void remove(E element) {
remove(node(element));
}
private void remove(Node<E> node) {
if (node == null)
return;
size--;
if (hasTwoChild(node)) {
// the node's degree is 2, use node's predecessor/successor's element
// cover the node, and then delete the predecessor/successor
Node<E> successor = Objects.requireNonNull(successor(node));
node.element = successor.element;
node = successor;
}
// reach here, the degree of the node is possible only 0 or 1
// that is to say, the node only has one child
Node replacement = node.left == null ? node.right : node.left;
if(replacement ! =null) {
// the node's degree is 1
replacement.parent = node.parent;
if (isRoot(node)) {
root = replacement;
} else if (compare(node.element, node.parent.element) >= 0) {
node.parent.right = replacement;
} else{ node.parent.left = replacement; }}else {
// the node is leaf node
if (isRoot(node)) {
root = null;
} else if (compare(node.element, node.parent.element) >= 0) {
node.parent.right = null;
} else {
node.parent.left = null;
}
}
afterRemove(node);
}
protected void afterRemove(Node<E> node) {
// let auto-balance bst overwrite the method to balance the tree
}
private boolean isRoot(Node<E> node) {
return node.parent == null;
}
public boolean contains(E element) {
returnnode(element) ! =null;
}
public void clear(a) {
root = null;
size = 0;
}
public Node node(E element) {
Node<E> node = root;
while(node ! =null) {
int compare = compare(element, node.element);
if (compare == 0)
return node;
else if (compare > 0) {
node = node.right;
} else{ node = node.left; }}return null;
}
private Node predecessor(Node<E> node) {
if(node.left ! =null) {
node = node.left;
while(node.right ! =null) {
node = node.right;
}
return node;
} else {
Node parent = node.parent;
while(parent ! =null) {
if (node == parent.right) {
return parent;
} else{ node = parent; parent = node.parent; }}return null; }}private Node successor(Node<E> node) {
if(node.right ! =null) {
node = node.right;
while(node.left ! =null) {
node = node.left;
}
return node;
} else {
Node parent = node.parent;
while(parent ! =null) {
if (node == parent.left) {
return parent;
} else{ node = parent; parent = node.parent; }}return null; }}private int compare(E insert, E current) {
if(comparator ! =null) {
return Objects.compare(insert, current, comparator);
}
return ((Comparable<E>) insert).compareTo(current);
}
private void nonNullCheck(E element) {
if (isNull(element)) {
throw new IllegalArgumentException("element must not be null"); }}@Override
public Object root(a) {
return root;
}
@Override
public Object left(Object node) {
return ((Node<E>) node).left;
}
@Override
public Object right(Object node) {
return ((Node<E>) node).right;
}
@Override
public Object string(Object node) {
return node;
}
protected static class Node<E> {
E element;
Node<E> left;
Node<E> right;
Node<E> parent;
Node(E element, Node<E> parent) {
this(element);
this.parent = parent;
}
Node(E element) {
this.element = element;
}
boolean isLeftChildOf(Node node) {
return this == node.left;
}
@Override
public String toString(a) {
return "Node{" +
"element=" + element +
'} '; }}private static boolean oneIsChildOfAnother(Node one, Node another) {
returnone ! =null && (one == another.left || one == another.right);
}
private static boolean isLeaf(Node node) {
return node.left == null && node.right == null; }}Copy the codeSelf-balanced binary search tree
package top.zhenganwen.learn.algorithm.datastructure.tree;
import java.util.Comparator;
/ * * *@author zhenganwen
* @date2019/11/28/028 for * /
public class BBST<E> extends BinarySearchTree<E> {
public BBST(a) {}public BBST(Comparator<E> comparator) {
this.comparator = comparator;
}
protected void rotateLeft(Node<E> node) {
Node<E> child = node.right;
// rotate left
node.right = child.left;
child.left = node;
afterRotate(node, child);
}
protected void afterRotate(Node<E> node, Node<E> child) {
// link parent
child.parent = node.parent;
if (node.parent == null)
root = child;
else if (node.isLeftChildOf(node.parent))
node.parent.left = child;
else
node.parent.right = child;
node.parent = child;
if(node == child.right && node.left ! =null)
node.left.parent = node;
if(node == child.left && node.right ! =null)
node.right.parent = node;
}
protected void rotateRight(Node<E> node) {
Node<E> child = node.left;
// rotate right
node.left = child.right;
child.right = node;
afterRotate(node, child);
}
/** * * LL * * inorder traversal: a b c d e f g * | * _______f______ * | | * ____d____ g ____d____ * | | ===> | | * _b_ e _b_ _f_ * | | | | | | * a c a c e g * * * RR * * inorder traversal: a b c d e f g * | * ____b____ * | | * a ____d____ ____d____ * | | ===> | | * c _f_ _b_ _f_ * | | | | | | * e g a c e g * * LR * * inorder traversal: a b c d e f g * | * ______f_____ * | | * ___b___ g ____d____ * | | ===> | | * a _d_ _b_ _f_ * | | | | | | * c e a c e g * * * RL * * inorder traversal: a b c d e f g * | * ______b______ * | | * a ___f___ ____d____ * | | ===> | | * _d_ g _b_ _f_ * | | | | | | * c e a c e g * * *@param r the root node of the child tree
* @param a
* @param b
* @param c
* @param d
* @param e
* @param f
* @param g
*/
protected void rotate( Node
r, Node
a, Node
b, Node
c, Node
d, Node
e, Node
f, Node
g )
{
// d -> new root of the child tree
d.parent = r.parent;
if (r.parent == null)
root = d;
else if (r.isLeftChildOf(r.parent))
r.parent.left = d;
else
r.parent.right = d;
// a-b-c
b.left = a;
b.right = c;
if(a ! =null)
a.parent = b;
if(c ! =null)
c.parent = b;
// e-f-g
f.left = e;
f.right = g;
if(e ! =null)
e.parent = f;
if(g ! =null)
g.parent = f;
// b-d-fd.left = b; d.right = f; b.parent = d; f.parent = d; }}Copy the codeRed and black tree
package top.zhenganwen.learn.algorithm.datastructure.tree;
import top.zhenganwen.learn.algorithm.commons.printer.BinaryTrees;
import java.util.Comparator;
/ * * *@author zhenganwen
* @date2019/11/28/028 15:52 * /
public class RBTree<E> extends BBST<E> {
private static boolean RED = false;
private static boolean BLACK = true;
public RBTree(a) {}public RBTree(Comparator<E> comparator) {
this.comparator = comparator;
}
@Override
protected void afterAdd(Node<E> node) {
// the insert node is root node or node overflows to top
if (node.parent == null) {
darken(node);
return;
}
// the node is leaf node
RBNode<E> parent = (RBNode<E>) node.parent;
// 1. black parent
if (parent.color == BLACK) {
// redden it -> default red color
return;
}
// 2. red parent, and grand must exist
RBNode<E> uncle = sibling(parent);
RBNode<E> grand = (RBNode<E>) parent.parent;
if (isRed(uncle)) {
/ / 2.1 overflow
darken(parent);
darken(uncle);
redden(grand);
afterAdd(grand);
return;
}
// 2.2 uncle is null or black
if (parent.isLeftChildOf(grand)) {
if (node.isLeftChildOf(parent)) {
// LL
darken(parent);
redden(grand);
rotateRight(grand);
} else {
// LRdarken(node); redden(grand); rotateLeft(parent); rotateRight(grand); }}else {
if (node.isLeftChildOf(parent)) {
// RL
darken(node);
redden(grand);
rotateRight(parent);
rotateLeft(grand);
} else {
// RRredden(grand); darken(parent); rotateLeft(grand); }}}private RBNode<E> color(Node<E> node, boolean color) {
RBNode<E> n = (RBNode<E>) node;
n.color = color;
return n;
}
private RBNode redden(Node<E> node) {
return color(node, RED);
}
private RBNode darken(Node<E> node) {
return color(node, BLACK);
}
private boolean isRed(Node<E> node) {
returnnode ! =null && ((RBNode<E>) node).color == RED;
}
private RBNode<E> sibling(Node<E> node) {
if (node.parent == null) {
return null;
}
if (node.isLeftChildOf(node.parent)) {
return (RBNode<E>) node.parent.right;
} else {
return(RBNode<E>) node.parent.left; }}@Override
protected Node<E> createNode(E element, Node<E> parent) {
return new RBNode<>(element, parent);
}
private class RBNode<E> extends Node<E> {
boolean color = RED;
RBNode(E element, Node<E> parent) {
super(element, parent);
}
@Override
public String toString(a) {
String s = "";
if (color == RED) {
s += "R_";
}
return s + element + "(" + (parent == null ? "null" : parent.element) + ")"; }}public static void main(String[] args) {
Integer[] arr = new Integer[]{
89.90.40.21.81.58.79.85.98.12.15.91.96.69.18.66.47.43.82
};
RBTree<Integer> rbt = new RBTree<>();
for (Integer i : arr) {
System.out.println("【" + i + "】");
rbt.add(i);
BinaryTrees.println(rbt);
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ="); }}}Copy the codeRemove elements
The premise
1. Delete the red node
2. Delete the black node
2.1. Delete the black node with a red child
Delete the black node with no red child
2.2.1 The sibling node of the deleted node is black
2.2.2 The sibling node of the deleted node is red
Code implementation
BST
package top.zhenganwen.learn.algorithm.datastructure.tree;
import top.zhenganwen.learn.algorithm.commons.printer.BinaryTreeInfo;
import top.zhenganwen.learn.algorithm.commons.printer.BinaryTrees;
import java.util.*;
import static java.util.Objects.isNull;
/ * * *@author zhenganwen
* @datePass 2019/11/6 when * /
public class BinarySearchTree<E> implements BinaryTreeInfo {
protected Node<E> root;
private int size;
protected Comparator<E> comparator;
public BinarySearchTree(a) {}public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}
public void add(E element) {
nonNullCheck(element);
if (root == null) {
root = createNode(element, null);
size++;
afterAdd(root);
return;
}
Node<E> parent = root, cur = root;
int compare = 0;
while(cur ! =null) {
parent = cur;
compare = compare(element, cur.element);
cur = compare > 0 ? cur.right : compare < 0 ? cur.left : cur;
if (cur == parent) {
cur.element = element;
return;
}
}
Node<E> node = createNode(element, parent);
if (compare > 0) {
parent.right = node;
} else {
parent.left = node;
}
size++;
afterAdd(node);
}
protected void afterAdd(Node<E> node) {}protected Node<E> createNode(E element, Node<E> parent) {
return new Node<>(element, parent);
}
public void remove(E element) {
remove(node(element));
}
private void remove(Node<E> node) {
if (node == null)
return;
size--;
if (hasTwoChild(node)) {
// the node's degree is 2, use node's predecessor/successor's element
// cover the node, and then delete the predecessor/successor
Node<E> successor = Objects.requireNonNull(successor(node));
node.element = successor.element;
node = successor;
}
// reach here, the degree of the node is only possible 0 or 1
// that is to say, the node has no more than one child
Node replacement = node.left == null ? node.right : node.left;
if(replacement ! =null) {
// the node's degree is 1
replacement.parent = node.parent;
if (isRoot(node)) {
root = replacement;
} else if (compare(node.element, node.parent.element) >= 0) {
node.parent.right = replacement;
} else {
node.parent.left = replacement;
}
afterRemove(node, replacement);
} else {
// the node is leaf node
if (isRoot(node)) {
root = null;
} else if (compare(node.element, node.parent.element) >= 0) {
node.parent.right = null;
} else {
node.parent.left = null;
}
afterRemove(node, null); }}protected void afterRemove(Node<E> node, Node<E> replacement) {
// let auto-balance bst overwrite the method to rebalance the tree
}
private boolean isRoot(Node<E> node) {
return node.parent == null;
}
public boolean contains(E element) {
returnnode(element) ! =null;
}
public void clear(a) {
root = null;
size = 0;
}
public Node node(E element) {
Node<E> node = root;
while(node ! =null) {
int compare = compare(element, node.element);
if (compare == 0)
return node;
else if (compare > 0) {
node = node.right;
} else{ node = node.left; }}return null;
}
private Node predecessor(Node<E> node) {
if(node.left ! =null) {
node = node.left;
while(node.right ! =null) {
node = node.right;
}
return node;
} else {
Node parent = node.parent;
while(parent ! =null) {
if (node == parent.right) {
return parent;
} else{ node = parent; parent = node.parent; }}return null; }}private Node successor(Node<E> node) {
if(node.right ! =null) {
node = node.right;
while(node.left ! =null) {
node = node.left;
}
return node;
} else {
Node parent = node.parent;
while(parent ! =null) {
if (node == parent.left) {
return parent;
} else{ node = parent; parent = node.parent; }}return null; }}private int compare(E insert, E current) {
if(comparator ! =null) {
return Objects.compare(insert, current, comparator);
}
return ((Comparable<E>) insert).compareTo(current);
}
private void nonNullCheck(E element) {
if (isNull(element)) {
throw new IllegalArgumentException("element must not be null"); }}@Override
public Object root(a) {
return root;
}
@Override
public Object left(Object node) {
return ((Node<E>) node).left;
}
@Override
public Object right(Object node) {
return ((Node<E>) node).right;
}
@Override
public Object string(Object node) {
return node;
}
protected static class Node<E> {
E element;
Node<E> left;
Node<E> right;
Node<E> parent;
Node(E element, Node<E> parent) {
this(element);
this.parent = parent;
}
Node(E element) {
this.element = element;
}
boolean isLeftChildOf(Node node) {
return this == node.left;
}
@Override
public String toString(a) {
return "Node{" +
"element=" + element +
'} '; }}public static void preOrderUnRecur(Node root) {
emptyTreeCheck(root);
Stack<Node> stack = new Stack<>();
StringBuilder stringBuilder = new StringBuilder();
stack.push(root);
while(! stack.isEmpty()) { Node node = stack.pop(); stringBuilder.append(node.element).append("");
if(node.right ! =null) {
stack.push(node.right);
}
if(node.left ! =null) {
stack.push(node.left);
}
}
System.out.println(stringBuilder.toString());
}
private static void emptyTreeCheck(Node root) {
if (root == null) {
throw new IllegalArgumentException("empty tree"); }}public static void inOrderUnRecur(Node root) {
emptyTreeCheck(root);
StringBuilder sb = new StringBuilder();
Stack<Node> stack = new Stack<>();
while(root ! =null) {
stack.push(root);
root = root.left;
while (root == null) {
if (stack.isEmpty()) {
break;
} else {
Node node = stack.pop();
sb.append(node.element).append("");
root = node.right;
}
}
}
System.out.println(sb.toString());
}
private static void postOrderUnRecur(Node root) {
emptyTreeCheck(root);
StringBuilder stringBuilder = new StringBuilder();
Stack<Node> stack = new Stack<>();
stack.push(root);
Node lastAccess = null;
while(! stack.isEmpty()) { Node node = stack.peek();// Access is required when the incoming node is a leaf node or the last accessed node is a child node
if (isLeaf(node) || oneIsChildOfAnother(lastAccess, node)) {
stack.pop();
stringBuilder.append(node.element).append("");
lastAccess = node;
} else {
if(node.right ! =null) {
stack.push(node.right);
}
if(node.left ! =null) {
stack.push(node.left);
}
}
}
System.out.println(stringBuilder.toString());
}
public static void levelOrder(Node root) {
emptyTreeCheck(root);
StringBuilder stringBuilder = new StringBuilder();
LinkedList<Node> queue = new LinkedList<>();
queue.offer(root);
while(! queue.isEmpty()) { Node node = queue.poll(); stringBuilder.append(node.element).append("");
if(node.left ! =null) {
queue.offer(node.left);
}
if(node.right ! =null) {
queue.offer(node.right);
}
}
System.out.println(stringBuilder.toString());
}
private static boolean oneIsChildOfAnother(Node one, Node another) {
returnone ! =null && (one == another.left || one == another.right);
}
private static boolean isLeaf(Node node) {
return node.left == null && node.right == null;
}
public static int height(Node root) {
if (root == null) {
return 0;
}
return Math.max(height(root.left), height(root.right)) + 1;
}
public static int heightUnRecur(Node root) {
if (root == null) {
return 0;
}
Stack<Node> s1 = new Stack<>(), s2 = new Stack<>();
int height = 0;
s1.push(root);
while(! s1.isEmpty()) {while(! s1.isEmpty()) { Node node = s1.pop();if(node.left ! =null) {
s2.push(node.left);
}
if(node.right ! =null) {
s2.push(node.right);
}
}
height++;
Stack tmp = s1;
s1 = s2;
s2 = tmp;
}
return height;
}
public static boolean isCompleteBinaryTreeUnRecur(Node root) {
if (root == null) {
return true;
}
boolean leafMode = false;
LinkedList<Node> queue = new LinkedList<>();
queue.add(root);
while(! queue.isEmpty()) { Node node = queue.pollFirst();if (leafMode) {
if(! isLeaf(node)) {return false;
}
continue;
}
if (hasTwoChild(node)) {
queue.addLast(node.left);
queue.addLast(node.right);
} else if (node.left == null&& node.right ! =null) {
return false;
} else {
leafMode = true;
if(node.left ! =null) { queue.addLast(node.left); }}}return true;
}
private static boolean hasTwoChild(Node node) {
returnnode ! =null&& node.left ! =null&& node.right ! =null;
}
public static void main(String[] args) {
int[] arr = { 7.4.9.2.5.8.11.3.12.1 };
BinarySearchTree<Integer> bst = new BinarySearchTree<>(Integer::compareTo);
for (int i : arr) {
bst.add(i);
}
BinaryTrees.println(bst);
// remove node that degree is 0
// bst.remove(1);
// bst.remove(3);
// bst.remove(12);
// BinaryTrees.println(bst);
// remove node that degree is 1
// bst.remove(11);
// BinaryTrees.println(bst);
// remove node that degree is 2
// bst.remove(4);
// bst.remove(9);
// BinaryTrees.println(bst);
// remove root
bst.remove(7);
BinaryTrees.println(bst);
// Node root = new Node(1);
// root.left = new Node(2);
// root.right = new Node(3);
// root.left.left = new Node(4);
// root.left.right = new Node(5);
// root.right.left = new Node(6);
// root.right.right = new Node(7);
// root.left.left.left = new Node(8);
// root.left.right.left = new Node(9);
// root.left.right.left.left = new Node(10);
// preOrderUnRecur(root);
// inOrderUnRecur(root);
// postOrderUnRecur(root);
// System.out.println(height(root));
// System.out.println(heightUnRecur(root));
// System.out.println(isCompleteBinaryTreeUnRecur(root));
// levelOrder(root);}}Copy the codeBBST
package top.zhenganwen.learn.algorithm.datastructure.tree;
import java.util.Comparator;
/ * * *@author zhenganwen
* @date2019/11/28/028 for * /
public class BBST<E> extends BinarySearchTree<E> {
public BBST(a) {}public BBST(Comparator<E> comparator) {
this.comparator = comparator;
}
protected void rotateLeft(Node<E> node) {
Node<E> child = node.right;
// rotate left
node.right = child.left;
child.left = node;
afterRotate(node, child);
}
protected void afterRotate(Node<E> node, Node<E> child) {
// link parent
child.parent = node.parent;
if (node.parent == null)
root = child;
else if (node.isLeftChildOf(node.parent))
node.parent.left = child;
else
node.parent.right = child;
node.parent = child;
if(node == child.right && node.left ! =null)
node.left.parent = node;
if(node == child.left && node.right ! =null)
node.right.parent = node;
}
protected void rotateRight(Node<E> node) {
Node<E> child = node.left;
// rotate right
node.left = child.right;
child.right = node;
afterRotate(node, child);
}
/** * * LL * * inorder traversal: a b c d e f g * | * _______f______ * | | * ____d____ g ____d____ * | | ===> | | * _b_ e _b_ _f_ * | | | | | | * a c a c e g * * * RR * * inorder traversal: a b c d e f g * | * ____b____ * | | * a ____d____ ____d____ * | | ===> | | * c _f_ _b_ _f_ * | | | | | | * e g a c e g * * LR * * inorder traversal: a b c d e f g * | * ______f_____ * | | * ___b___ g ____d____ * | | ===> | | * a _d_ _b_ _f_ * | | | | | | * c e a c e g * * * RL * * inorder traversal: a b c d e f g * | * ______b______ * | | * a ___f___ ____d____ * | | ===> | | * _d_ g _b_ _f_ * | | | | | | * c e a c e g * * *@param r the root node of the child tree
* @param a
* @param b
* @param c
* @param d
* @param e
* @param f
* @param g
*/
protected void rotate( Node
r, Node
a, Node
b, Node
c, Node
d, Node
e, Node
f, Node
g )
{
// d -> new root of the child tree
d.parent = r.parent;
if (r.parent == null)
root = d;
else if (r.isLeftChildOf(r.parent))
r.parent.left = d;
else
r.parent.right = d;
// a-b-c
b.left = a;
b.right = c;
if(a ! =null)
a.parent = b;
if(c ! =null)
c.parent = b;
// e-f-g
f.left = e;
f.right = g;
if(e ! =null)
e.parent = f;
if(g ! =null)
g.parent = f;
// b-d-fd.left = b; d.right = f; b.parent = d; f.parent = d; }}Copy the codeAVLTree
package top.zhenganwen.learn.algorithm.datastructure.tree;
import top.zhenganwen.learn.algorithm.commons.printer.BinaryTrees;
import java.util.Comparator;
/ * * *@author zhenganwen
* @date2019/11/25 13:46 * /
public class AVLTree<E> extends BBST<E> {
public AVLTree(a) {}public AVLTree(Comparator<E> comparator) {
this.comparator = comparator;
}
/**
* just need once rebalance
*
* @param node
*/
@Override
protected void afterAdd(Node<E> node) {
while((node = node.parent) ! =null) {
if (isBalanced(node)) {
updateHeight(node);
} else {
rebalance(node);
break; }}}/**
* remove the {@codenode}, maybe cause the LL or RR situation generating, * this depends on the height of right child's left height when remove left child's node * and the height of left child's right height when remove right child's node. * what's more, this time rebalance maybe cause the ancestor's unbalance. * <p> * maybe need O(logn) times rebalance. see red-black tree {@link RBTree}
*
* @param node
*/
@Override
protected void afterRemove(Node<E> node, Node<E> replacement) {
while((node = node.parent) ! =null) {
if (isBalanced(node)) {
updateHeight(node);
} else{ rebalance(node); }}}/**
* see {@linkThis# rebalance: split left and right rotation to do * *@param node
*/
private void rebalance2(Node<E> node) {
AVLNode grand = (AVLNode) node;
AVLNode parent = getTallerChild(grand);
AVLNode child = getTallerChild(parent);
if (parent == grand.left) {
if (child == parent.left) {
// LL rotate right
rotateRight(grand);
} else {
// LR rotate left first and then rotate rightrotateLeft(parent); rotateRight(grand); }}else {
if (child == parent.right) {
// RR rotate left
rotateLeft(grand);
} else {
// RL rotate right first and then rotate leftrotateRight(parent); rotateLeft(grand); }}}/**
* see {@linkThis# rebalance2} * balance plan 2: extract general logic from the four transformations * *@param node
*/
private void rebalance(Node<E> node) {
AVLNode grand = (AVLNode) node;
AVLNode parent = getTallerChild(grand);
AVLNode child = getTallerChild(parent);
if (parent == grand.left) {
if (child == parent.left) {
/* LL _______f______ | | ____d____ g | | _b_ e | | a c f -> grand, d -> parent, b -> child */
rotate(grand,
cast(child.left), child, cast(child.right),
parent,
cast(parent.right), grand, cast(grand.right));
} else {
/* LR ______f_____ | | ___b___ g | | a _d_ | | c e f -> grand, b -> parent, d -> child */rotate(grand, cast(parent.left), parent, cast(child.left), child, cast(child.right), grand, cast(grand.right)); }}else {
if (child == parent.right) {
/* RR ____b____ | | a ____d____ | | c _f_ | | e g b -> grand, d -> parent, f -> child */
rotate(grand,
cast(grand.left), grand, cast(parent.left),
parent,
cast(child.left), child, cast(child.right));
} else {
/* RL ______b______ | | a ___f___ | | _d_ g | | c e b -> grand, f -> parent, d -> child */rotate(grand, cast(grand.left), grand, cast(child.left), child, cast(child.right), parent, cast(parent.right)); }}}@Override
protected void afterRotate(Node<E> node, Node<E> child) {
super.afterRotate(node, child);
((AVLNode) node).updateHeight();
((AVLNode) child).updateHeight();
}
@Override
protected void rotate(Node<E> r, Node<E> a, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f, Node<E> g) {
super.rotate(r, a, b, c, d, e, f, g);
((AVLNode) b).updateHeight();
((AVLNode) f).updateHeight();
((AVLNode) d).updateHeight();
}
private AVLNode cast(Node node) {
return (AVLNode) node;
}
private AVLNode getTallerChild(AVLNode node) {
int r = node.getRightHeight();
int l = node.getLeftHeight();
return (AVLNode) (r > l ? node.right : node.left);
}
private void updateHeight(Node<E> node) {
((AVLNode) node).updateHeight();
}
protected boolean isBalanced(Node<E> node) {
return ((AVLNode) node).isBalanced();
}
@Override
protected Node<E> createNode(E element, Node<E> parent) {
return new AVLNode(element, parent);
}
protected static class AVLNode extends Node {
int height = 1;
AVLNode(Object element, Node parent) {
super(element, parent);
}
void updateHeight(a) {
int r = getRightHeight();
int l = getLeftHeight();
height = 1 + Math.max(r, l);
}
int getLeftHeight(a) {
return left == null ? 0 : ((AVLNode) left).height;
}
int getRightHeight(a) {
return right == null ? 0 : ((AVLNode) right).height;
}
int balanceFactor(a) {
int r = getRightHeight();
int l = getLeftHeight();
return Math.abs(r - l);
}
boolean isBalanced(a) {
return balanceFactor() <= 1;
}
@Override
public String toString(a) {
return element.toString() + "(" + (parent == null ? "null" : parent.element) + ")"; }}public static void main(String[] args) {
AVLTree tree = new AVLTree();
for (int i = 0; i < 50; i++) { tree.add(i); } BinaryTrees.println(tree); }}Copy the codeRBTree
package top.zhenganwen.learn.algorithm.datastructure.tree;
import top.zhenganwen.learn.algorithm.commons.printer.BinaryTrees;
import java.util.Comparator;
import java.util.Optional;
/ * * *@author zhenganwen
* @date2019/11/28/028 15:52 * /
public class RBTree<E> extends BBST<E> {
private static boolean RED = false;
private static boolean BLACK = true;
public RBTree(a) {}public RBTree(Comparator<E> comparator) {
this.comparator = comparator;
}
/** * adjustment after bst's insertion. * </hr> * the node must be leaf node, and we can regard it as insert a element into a 2-3-4 b-tree.</br> * the 2-3-4 b-tree's leaf node must but only have one black node. </br> * so the b-tree's leaf node can have four situations below: * <ul> * <li>one black node with two red children. R<-B->R </li> * <li>one black node with one red left child. R<-B- </li> * <li>one black node with one red right child. -B->R </li> * <li>one black node. -B- </li> * </ul> * * 1. the insert node is added into the left of right of the black node. * * B- => R<-B- / -B->R * <-B- => R<-B->R * B->R => R<-B->R * * insert into directly with bst's insertion logic * * 2. the insert node is added into the left of right of the red node. after insertion, the overflow not occurs * * R<-B- => R<-B R<-B * \ / * R R * * -B->R => -B->R -B->R * / \ * R R * * after insertion of bst, we need rotate to let the mid node become the black node * * 3. the insert node is added into the left of right of the red node. and then, the overflow occurs * * R<-B->R => R<-B->R R<-B->R R<-B->R R<-B->R * / \ \ / * R R R R * * let the left and right become two independent b-tree node(color it to black), and then * color itself to red to become a insertion node added its parent b-tree node *@param node
*/
@Override
protected void afterAdd(Node<E> node) {
// the insert node is root node or node overflows to top
if (node.parent == null) {
darken(node);
return;
}
// the node is leaf node
RBNode<E> parent = (RBNode<E>) node.parent;
// 1. black parent
if (parent.color == BLACK) {
// redden it -> default red color
return;
}
// 2. red parent, and grand must exist
RBNode<E> uncle = sibling(parent);
RBNode<E> grand = (RBNode<E>) parent.parent;
if (isRed(uncle)) {
/ / 2.1 overflow
darken(parent);
darken(uncle);
redden(grand);
afterAdd(grand);
return;
}
// 2.2 uncle is null or black
if (parent.isLeftChildOf(grand)) {
if (node.isLeftChildOf(parent)) {
// LL
darken(parent);
redden(grand);
} else {
// LR
darken(node);
redden(grand);
rotateLeft(parent);
}
rotateRight(grand);
} else {
if (node.isLeftChildOf(parent)) {
// RL
darken(node);
redden(grand);
rotateRight(parent);
} else {
// RRredden(grand); darken(parent); } rotateLeft(grand); }}/** * First, the actual deleted BST node must exist in the leaf node of the red-black tree equivalent of the 4th order B tree: * * a. R_1 <- B_2 -> R_3 * * b. R_1 <- B_2 * * c. B_2 -> R_3 * * d. B_2 * * 1. If the nodes to be removed are red nodes, such as R_1 and R_3 of A, B, and C, then no additional repair operation is required after the deletion logic of BST * * 2. If the node to be deleted is black, as in the example above, B_2 * * 2.1 in B and C first does not include B_2 in A, in which case we will delete the subsequent node R_3 * * 2.2 if B_2 in B and C is deleted, The deletion logic of BST is to replace it with its child node R_1/R_3. In this case, we need to dye the red child node black * * 3 to ensure the equivalence * (there must be only one black node in the B-tree node). If the deleted node has no red child node (i.e. the replacement node is null) * * 3.1 If the deleted node's sibling is black * * 3.1.1 If the sibling has red child node can be borrowed, * * Rotate the parent node to the right or left, * and color the parent node to black * * LLDB: Delete B_4 * * R_3 R_2 * / \ => / \ * R_1 < -b_2 B_4 R_1 B_3 * * If the relative orientation of the sibling and its red child node is LR or RL, LLDB = LLDB * * LLDB = LLDB * * LLDB The delete B_5 * * R_4 R_4 R_3 * / \ = > / = > / \ * B_2 - > R_3 B_5 B_2 - > R_3 B_5 B_2 B_4 * * 3.1.2 if siblings without red children can borrow, It is equivalent to repair the red-black tree * * [pull down the parent node] and merge it with the current node and its sibling nodes to form a new fourth-order B-tree node (the actual practice is to dye the parent node black and the sibling node red) * considering that [underflow] has upward propagation. * * LLDB: * * LLDB: delete B_8 * * B_5 B_5 * / \ / \ * B_3 B_7 => B_3 \ => B_3 <- B_5 * / \ / \ / \ \ / \ \ * B_2 B_4 B_6 B_8 B_2 B_4 R_6< -b_7 B_2 B_4 R_6< -b_7 * * B_8's sibling B_6 has no red child and B_7's sibling B_3 has no red child overflows to the root, terminating * * 3.2 If the sibling of the deleted node is a red node * * According to the red-black nature, Equivalent order 4 B tree, and brother be deleted node is not in the same layer of * (brothers and parent node in a tree node B, the deleted node in the tree node B) in the next layer of the tree node B * * so brother must have two black child nodes, and the removed node is located in the same layer, 3.1 * * * LLDB: Delete B_7 * * R_4 < -b_6 B_4 -> R_6 * / \ \ => / / \ * B_3 B_5 B_7 B_3 B_5 B_7 B_7 B_5 B_7 * * By right-rotation of R_6, the sibling of B_7 changes from red R_4 to black B_5, The logic of 3.1 can be reused thereafter * * * *@param node
* @param replacement
*/
@Override
protected void afterRemove(Node<E> node, Node<E> replacement) {
// 1. If the node to be deleted is a red node
if (isRed(node)) {
return;
}
// 2. If the node to be deleted is replaced by the red node
if (isRed(replacement)) {
darken(replacement);
return;
}
if (node.parent == null) { // The underflow in 3.1.2 propagates to the root node and terminates
return;
}
Node<E> parent = node.parent;
boolean left = parent.left == null || parent.left == node; // Whether the current deleted node is a left child or whether the node overflowed to is a left child
RBNode<E> sibling = (RBNode<E>) (left ? parent.right : parent.left);
// 3.2 If the sibling is a red node, rotate the parent to 3.1
if (isRed(sibling)) {
if (left) rotateRight(parent);
else rotateLeft(parent);
afterRemove(node, null);
// 3.1 sibling nodes are black nodes
} else if (hasRedChild(sibling)) {
3.1.1 If the sibling node has red children, it can be borrowed. The rotated middle node inherits the parent node's color, and the nodes on both sides are dyed black
darken(parent); // The parent node does not become an intermediate node
if (sibling.isLeftChildOf(parent)) {
if (isRed(sibling.left)) {
// LL sibling nodes will become intermediate nodes
if (isRed(parent)) {
redden(sibling);
}
darken(sibling.left);
} else {
// The children of LR siblings will become intermediate nodes
if (isRed(parent)) {
redden(sibling.right);
}
darken(sibling);
rotateLeft(sibling); // Set LR to LL
}
// It must be LL
rotateRight(parent);
} else {
// Symmetric with the above
if (isRed(sibling.left)) {
// RL
if (isRed(parent)) {
redden(sibling.left);
}
darken(sibling);
rotateRight(sibling);
} else {
// RR
if(isRed(parent)) { redden(sibling); } darken(sibling.right); } rotateLeft(parent); }}else {
// 3.1.2 Sibling nodes have no red children to borrow, parent nodes are dyed black, sibling nodes are dyed red, and underflow propagation (if the parent node is pulled down is black)
boolean parentColor = ((RBNode<E>) parent).color;
darken(parent);
redden(sibling);
if (parentColor == BLACK) {
afterRemove(parent, null); }}}private boolean hasRedChild(RBNode<E> rbNode) {
returnrbNode ! =null && (isRed(rbNode.left) || isRed(rbNode.right));
}
private RBNode<E> color(Node<E> node, boolean color) {
RBNode<E> n = (RBNode<E>) node;
n.color = color;
return n;
}
private RBNode redden(Node<E> node) {
return color(node, RED);
}
private RBNode darken(Node<E> node) {
return color(node, BLACK);
}
/**
* if the {@code node} is null or its color is black, it will return false
* @param node
* @return* /
private boolean isRed(Node<E> node) {
returnnode ! =null && ((RBNode<E>) node).color == RED;
}
private boolean isBlack(Node<E> node) {
// node is leaf's children or non-null black node
return node == null || ((RBNode<E>) node).color == BLACK;
}
private RBNode<E> sibling(Node<E> node) {
if (node.parent == null) {
return null;
}
if (node.isLeftChildOf(node.parent)) {
return (RBNode<E>) node.parent.right;
} else {
return(RBNode<E>) node.parent.left; }}@Override
protected Node<E> createNode(E element, Node<E> parent) {
return new RBNode<>(element, parent);
}
private class RBNode<E> extends Node<E> {
boolean color = RED;
RBNode(E element, Node<E> parent) {
super(element, parent);
}
@Override
public String toString(a) {
StringBuilder sb = new StringBuilder();
Optional.ofNullable(left).ifPresent(p -> sb.append(p.element).append("-"));
if (color == RED) {
sb.append("R_");
}
sb.append(element);
Optional.ofNullable(right).ifPresent(p -> sb.append("-").append(p.element));
Optional.ofNullable(parent).ifPresent(p -> sb.append("(").append(p.element).append(")"));
returnsb.toString(); }}public static void main(String[] args) {
Integer[] arr = new Integer[]{
89.90.40.21.81.58.79.85.98.12.15.91.96.69.18.66.47.43.82
};
RBTree<Integer> rbt = new RBTree<>();
for (Integer i : arr) {
rbt.add(i);
Println ("add [" + I + "] "); // system.out.println ("add [" + I + "] ");
// BinaryTrees.println(rbt);
// System.out.println("=================================================");
}
BinaryTrees.println(rbt);
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
for (Integer i : arr) {
rbt.remove(i);
System.out.println("remove 【" + i + "】");
BinaryTrees.println(rbt);
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ="); }}}Copy the codeWhy balance
The five properties of a red-black tree guarantee that it is equivalent to a fourth-order B-tree
The performance comparison
AVL tree
-
The balance criterion is strict: the height difference between the left and right subtrees is no more than 1
-
The maximum height is 1.44 ∗ log 2 N + 2 − 1.328 (100W nodes, maximum AVL tree height 28)
-
Search, add, and delete all require O(logn) complexity. Add requires O(1) rotation adjustments, and delete requires O(logn) rotation adjustments at most
Red and black tree
-
The balance criteria are loose: no path is twice as large as any other
-
The maximum height is 2 ∗ log 2 (n + 1) (100W nodes, maximum tree height of red-black tree is 40)
-
Search, add, and delete are all O(logn) complexity, where add and delete require only O(1) rotation adjustments
According to statistics, the number of overflow propagation occurring when deleting nodes in red-black tree is no more than 3 times, so the complexity of rotation adjustment can be considered as O(1).
Technology selection
-
Search times are much greater than insert and delete, select AVL tree; Search, insert, delete almost the same number of times, choose red black tree
-
Compared to AVL trees, red-black trees sacrifice some balance in exchange for a small amount of rotation during insert/delete operations, and perform better overall than AVL trees
-
The average statistical performance of red-black tree is better than that of AVL tree