As B Tree is verry difficult to implement, we introduce RED BLACK TREE.
Tree Rotation
通过树的旋转，我们可以使一颗不平衡的树，变成一颗平衡的树。
本操作将用于维护红黑树
The formal definition of rotation is:
rotateLeft(G): Let x be the right child of G. Make G the new left child of x.
rotateRight(G): Let x be the left child of G. Make G the new right child of x.
简而言之：
左旋 = 用 curr Node 的右孩子作为 root，将 curr Node 成功放置在左侧
右旋 = 用 curr Node 的左孩子作为 root，将 curr Node 成功放置在右侧
private Node rotateRight(Node h) {
// assert (h != null) && isRed(h.left);
Node x = h.left;
h.left = x.right;
x.right = h;
return x;
}
// make a right-leaning link lean to the left
private Node rotateLeft(Node h) {
// assert (h != null) && isRed(h.right);
Node x = h.right;
h.right = x.left;
x.left = h;
return x;
}
Introduction
BST - Binary Search Tree 是非常美妙的树，因为其搜索效率为 O(logN)，相当之高，但存在的问题就是由于插入顺序的不同，茂密性会降低。换言之 BST 简单、高效（在理想情况下），但可能不平衡。B Tree（本节以 2-3 Tree 为例）则相反，自平衡但实现复杂，不简洁。所以红黑树出现了———实际上用 BST 实现的，但结构上等同于 2-3 Tree.
观察 2-3 Tree 与 BST 的异同，发现 2-3 Tree 除了一个节点可能会有 2 values & 3 nodes 之外，其他情况与 BST 没有区别。所以我们只需要找到一种方式， 在 2-3 Tree 的某个 node 出现 2 values & 3 children 时，从逻辑上将其 mapping 成一个 BST，物理实现上 still working as a BST 就好了。
这个方法就是用 Red glue links.
One-to-One Correspondence
Left-Leaning Red-Black trees have a 1-1 correspondence with 2-3 trees. Every 2-3 tree has a unique LLRB red-black tree associated with it.
As for 2-3-4 trees, they maintain correspondence with standard Red-Black trees.
Definition
Below is a summary of the properties/invariants of LLRB Trees:
- 1-1 correspondence with 2-3 trees.
- No node has 2 red links. (Only 1 red link)
- There are no red right-links.
- Every path from root to leaf has the same number of black links (because 2-3 trees have the same number of links to every leaf).
- Height is no more than 2x height + 1 of the corresponding 2-3 tree.
- The height of a red-black tree is proportional to the log of the number of entries.
Inserting
We insert into the LLRB as we would with a normal BST. However, this could break its 1-1 mapping to a 2-3 tree, so we will use rotations to massage the tree back into a proper structure.
When inserting: Use a red link. Insert in the same way as inserting into a BST.
If there is a right-leaning “3-node”, we have a Left Leaning Violation. Rotate left the appropriate node to fix.
If there are two consecutive left links, we have an Incorrect 4 Node Violation. Rotate right the appropriate node to fix.
If there are any nodes with two red children, we have a Temporary 4 Node. Color flip the node to emulate the split operation.
private Node put(Node h, Key key, Value val) {
if (h == null) { return new Node(key, val, RED); }
int cmp = key.compareTo(h.key);
if (cmp < 0) { h.left = put(h.left, key, val); }
else if (cmp > 0) { h.right = put(h.right, key, val); }
else { h.val = val; }
if (isRed(h.right) && !isRed(h.left)) { h = rotateLeft(h); }
if (isRed(h.left) && isRed(h.left.left)) { h = rotateRight(h); }
if (isRed(h.left) && isRed(h.right)) { flipColors(h); }
return h;
}
Summary
BST - Binary Search Tree are simple, but they are subject to imbalance which leads to crappy runtime. 2-3 Trees (B Trees) are balanced, but painful to implement.
LLRB insertion is simple to implement (deletion is a bit harder to implement, we won’t go over the specifics in this course). Use three basic operations to maintain the balanced structure, namely rotateLeft, rotateRight, and color flip.
LLRBs maintain correspondence with 2-3 trees, Standard Red-Black trees maintain correspondence with 2-3-4 trees.
Java’s TreeMap is a red-black tree that corresponds to 2-3-4 trees. 2-3-4 trees allow glue links on either side (see Red-Black Tree).
Reference
https://cs61b-2.gitbook.io/cs61b-textbook/18.-red-black-trees