1. 2-3 search trees
-
每个Node有1或2个key
- 2-node:one key,two children
- 3-node:two keys,three children
-
Perfect balance:
- 每一条path,从root到null-link都是相同长度
-
Symmetric order
- 横向从左到右升序
-
Search
- search key与各个Node的key比较
- 沿着对应的link(recursively),直到找到相同的key
-
Insertion
-
若每个key都已经有2个key,将新key加入这个3-node形成临时的4-node
-
将这个4-node中间值的key晋升为parent
-
重复直到结束
-
当这条search path从root起的每一个node都是2-node,那么再加入一个key,length+1
-
2. Red-Black BSTs
Represent 2-3 tree as a BST
-
Definition:
- 每一个Node最多只有一个red-link
- 每一条path从root到null-link都有相同数量的black-links
- Red-link只在左侧
- 当将red-link平方,red-black BST就是2-3 tree
-
Insertion
-
找到的null-link的parent node只有black-link
- 若key小于parent node,带着red-link加在左边就完成
- 若key大于parent node,带着red-link加在右边,再rotate left即可
-
找到的null-link的parent node已经有red-link(相当于在2-3tree中,3-node要临时变4-node)
- case 1(larger:已有a,b(parent),插入c):找到null-link,加入新的node(key=c, red-link),然后flip color
- case 2(smaller:已有b,c(parent),插入a):找到null-link,加入新的node(key=a, red-link)。现在b有两个red-links,不符合规定。c进行rotate right操作,回归case 1,然后flip color
- case 3(middle:已有a,c(parent),插入b):找到null-link,加入新的node(key=b, red-link)。此时red-link在a的右侧,不符合规定。b进行rotate left,回归case2,然后c进行rotate right操作,最后flip color
-
-
Java implementation
public class RBtree<Key extends Comparable<Key>, Value>{ private static final boolean RED = true; private static final boolean BLACK = false; private Node root; // root of BST private class Node{ Key key; Value val; Node left, right; boolean color; // color of parent link public Node(Key key, Value val, boolean color){ this.key = key; this.val = val; this.color = color; } } public void put(Key key, Value val){ root = put(root, key, val); } private Node put(Node h, Key key, Value val){ // find the null-link, insert at bottom (and color it red) if(h == null){ return new Node(key, val, RED); } int cmp = key.compareTo(x.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; } // Right child red, left child black: rotate left. if(isRed(h.right) && !isRed(h.left)){ h = rotateLeft(h); } // Left child, left-left grandchild red: rotate right. if(isRed(h.left) && isRed(h.left.left)){ h = rotateRight(h); } // Both children red: flip colors. if(isRed(h.left) && isRed(h.right)){ flipColor(h); } return h; } private boolean isRed(Node x){ if(x == null){ return false; } return x.color == RED; } // Orient a (temporarily) right-leaning red link to lean left. private Node rotateLeft(Node h){ // assert isRed(h.right); Node x = h.right; h.right = x.left; x.left = h; x.color = h.color; h.color = RED; return x } // Orient a left-leaning red link to (temporarily) lean right. private Node rotateRight(Node h){ // assert isRed(h.left); Node x = h.left; h.left = x.right; x.right = h; x.color = h.color; h.color = RED; return x; } // Recolor to split a (temporary) 4-node. private void flipColors(Node h){ // assert !isRed(h); // assert isRed(h.left); // assert isRed(h.right); h.color = RED; h.left.color = BLACK; h.right.color = BLACK; } public Value get(Key key){ Node x = root; while(x != null){ int cmp = key.compareTo(x.key); if(cmp < 0){ x = x.left; }else if(cmp > 0){ x = x.right; }else{ return null; } } } }
网友评论