手撕左倾红黑树(left-learning R-B BST)与自平衡二叉检索树(AVL)
面试意难平，怒撕红黑树
参考视频：普林斯顿Sedgewick教授的算法课程视频
https://www.coursera.org/learn/algorithms-part1
左倾红黑树 LLRB BST
2-3 Tree
2-3树节点：允许每个节点有1或2个键值
- 2-node: 有一个键值，两个子节点
- 3-node: 有两个键值，三个子节点
对于2节点[a]其两个子节点分别代表范围<a和>a，对于3节点[a b]其三个子节点分别代表范围<a，>a && <b，>b。
[15]
/ \
[6 10] [18]
/ \ \ / \
[1 4] [7] [14] [17] [20 25]
/ \ \ / \ / \ / \ / \ \
其中[6 10]和[1 4]都是3-node
如果要向其中插入值13，则最终会落在[14]节点上并且变为3-node
[ 15 ]
/ \
[6 10] [ 18 ]
/ \ \ / \
[1 4] [7] [13 14] [17] [20 25]
/ \ \ / \ / \ \ / \ / \ \
如果要向原2-3树插入值22，则其最终会落在节点[20 25]上，并且临时生成4节点后分解，4节点的中间键值会向上合并，剩下两个变成新的叶子
[ 15 ]
/ \
[6 10] [ 18 ]
/ \ \ / \
[1 4] [7] [14] [17] [20 22 25]
/ \ \ / \ / \ / \ / \ \ \
|
V
[ 15 ]
/ \
[6 10] [18 22]
/ \ \ / \ \
[1 4] [7] [14] [17] [20] [25]
/ \ \ / \ / \ / \ / \ / \
由于2-3树的分裂是向上的(底部形成临时4节点后分裂为两个节点并且中间键值向上合并，若向上合并导致父节点变为4节点会继续向上合并，若根节点变为4节点就会分裂形成新的根节点)因此能够保证其插入值后高度的平衡。
完整代码
2-3树的Java代码实现：
package structure;
public class MyTree23<K extends Comparable<K>, V> {
/* Main Part of Two-Three-Tree with INSERT & FIND & DELETE function */
private Node23<K, V> root;
public MyTree23() {
root = null;
}
/* Helper Function */
private int insertItem(Node23<K, V> node, Item<K, V> item) { // Return Index of Insertion
assert (!node.isFull());
node.itemsCnt++;
for (int i = Node23.ITEMS-1; i >= 0; i--) { // Swap Items
if (node.items[i] == null) continue;
if (item.key.compareTo(node.items[i].key) < 0)
node.items[i+1] = node.items[i];
else {
node.items[i+1] = item;
return i+1;
}
}
node.items[0] = item;
return 0;
}
private Item<K, V> removeItem(Node23<K, V> node) { // Remove And Return the last Item of Current-Node
assert (node.itemsCnt > 0);
Item<K, V> item = node.items[node.itemsCnt-1];
node.items[node.itemsCnt-1] = null;
node.itemsCnt--;
return item;
}
private void splitLeaf(Node23<K, V> node, Item<K, V> item) {
assert (node.isFull());
Node23<K, V> parent = node.parent;
Node23<K, V> maxNode = new Node23<>(); // new Node Contains One Item which is max (curr Node is left, max Node is right)
Node23<K, V> newRoot = new Node23<>(parent); // new Parent, Contains One Item which is middle
if (item.key.compareTo(node.items[0].key) < 0) { // IF newItem < first item of node
insertItem(maxNode, removeItem(node));
insertItem(newRoot, removeItem(node));
insertItem(node, item);
}
else if (item.key.compareTo(node.items[1].key) < 0) { // IF newItem < second item of node
insertItem(maxNode, removeItem(node));
insertItem(newRoot, item);
}
else { // IF newItem is biggest
insertItem(maxNode, item);
insertItem(newRoot, removeItem(node));
}
newRoot.children[0] = node;
node.parent = newRoot;
newRoot.children[1] = maxNode;
maxNode.parent = newRoot;
if (root == node)
root = newRoot;
else
splitUp(parent, newRoot);
}
private void splitUp(Node23<K, V> parent, Node23<K, V> node) { /* 2-3 TREE SPILT UP */
assert (node.itemsCnt == 1);
Item<K, V> nodeItem = node.items[0];
if (parent.isFull()) { // parent is 3-node, need to recursion
if (nodeItem.key.compareTo(parent.items[0].key) < 0) { // insert into LEFT
Node23<K, V> newRight = new Node23<>(parent); // new Right parent
insertItem(newRight, removeItem(parent)); // move Item to new Right parent
newRight.children[0] = parent.children[1];
newRight.children[1] = parent.children[2];
parent.children[1].parent = newRight;
parent.children[2].parent = newRight;
parent.children[0] = node;
parent.children[1] = newRight;
//node.parent = parent;
}
else if (nodeItem.key.compareTo(parent.items[1].key) < 0) { // bad condition, split middle
Node23<K, V> newLeft = new Node23<>(parent), newRight = new Node23<>(parent);
insertItem(newRight, removeItem(parent)); // move Item to new Right parent
Item<K, V> tempItem = removeItem(node);
insertItem(newLeft, removeItem(parent)); // move Item to new Right parent
insertItem(parent, tempItem);
// reconnect Children
newLeft.children[0] = parent.children[0]; // reconnect Left Parent
newLeft.children[1] = node.children[0];
parent.children[0].parent = node.children[0].parent = newLeft;
newRight.children[0] = node.children[1]; // reconnect Right Parent
newRight.children[1] = parent.children[2];
node.children[1].parent = parent.children[2].parent = newRight;
parent.children[0] = newLeft; // reconnect Parent Node
parent.children[1] = newRight;
parent.children[2] = null;
}
else { // insert into RIGHT
Node23<K, V> newLeft = new Node23<>(parent); // new Left parent
Item<K, V> tempItem = removeItem(parent); // move Item to new Left parent
insertItem(newLeft, removeItem(parent));
insertItem(parent, tempItem);
newLeft.children[0] = parent.children[0]; // reconnect Children
newLeft.children[1] = parent.children[1];
parent.children[0].parent = parent.children[1].parent = newLeft;
parent.children[0] = newLeft;
parent.children[1] = node;
}
Node23<K, V> grandPa = parent.parent;
if (grandPa == null) // parent is root
return;
splitUp(grandPa, parent);
}
else { // parent is 2-node
if (nodeItem.key.compareTo(parent.items[0].key) < 0) { // insert into LEFT
parent.children[2] = parent.children[1];
parent.children[1] = node.children[1];
parent.children[0] = node.children[0];
node.children[0].parent = node.children[1].parent = parent;
}
else {
parent.children[1] = node.children[0];
parent.children[2] = node.children[1];
}
}
}
/* Insert Function */
public void insert(K key, V val) {
if (null == root) {
root = new Node23<>();
root.items[0] = new Item<>(key, val);
root.itemsCnt = 1;
}
else {
Item<K, V> item = new Item<>(key, val);
Node23<K, V> node = root;
while (!node.isLeaf()) { // BST Search
boolean findChild = false;
for (int i = 0; i < node.itemsCnt; i++) {
if (key.compareTo(node.items[i].key) < 0) { // If key smaller, return left Child of currItem
node = node.children[i];
findChild = true;
break;
}
if (key.compareTo(node.items[i].key) == 0) {
node.items[i].val = val;
return;
}
}
if (!findChild) // Key Bigger than All Items
node = node.children[node.itemsCnt];
}
/* Insert Action */
if (node.isFull()) {
splitLeaf(node, item);
}
else {
insertItem(node, item);
}
}
}
/* Find Function */
private V find(K key) {
if (null == root)
return null;
Node23<K, V> node = root;
while (!node.isLeaf()) { // BST Search
boolean findChild = false;
for (int i = 0; i < node.itemsCnt; i++) {
if (key.compareTo(node.items[i].key) < 0) { // If key smaller, return left Child of currItem
node = node.children[i];
findChild = true;
break;
}
if (key.compareTo(node.items[i].key) == 0) // Find Key, Return Value
return node.items[i].val;
}
if (!findChild) // Key Bigger than All Items
node = node.children[node.itemsCnt];
}
for (int i = 0; i < node.itemsCnt; i++) // Search Leaf Node
if (key.compareTo(node.items[i].key) == 0) // Find Key, Return Value
return node.items[i].val;
return null;
}
}
/* class Item store Key and Value */
class Item<K extends Comparable<K>, V> {
K key;
V val;
public Item(K k, V v) { key = k; val = v; }
}
/* Tree Node */
class Node23<K extends Comparable<K>, V>{
public static final int CHILDREN = 3;
public static final int ITEMS = 2;
Node23<K, V> parent;
Item<K, V>[] items; //
Node23<K, V>[] children; // left child, middle child, right child
int itemsCnt;
/* No Arg Constructor */
public Node23() {
parent = null;
items = (Item<K, V>[]) new Item[ITEMS];
children = (Node23<K, V>[]) new Node23[CHILDREN];
itemsCnt = 0;
}
/* Constructor with parent node */
public Node23(Node23<K, V> p) {
parent = p;
items = (Item<K, V>[]) new Item[ITEMS];
children = (Node23<K, V>[]) new Node23[CHILDREN];
itemsCnt = 0;
}
public boolean isLeaf() {
return children[0] == null;
}
public boolean isFull() {
return itemsCnt == ITEMS;
}
}
2-3检索树的原理很简单，但是很繁琐，因为它有很多种情况，而在红黑树中，用巧妙的方法使用了2个结点解决了3-Node的问题
2-3树到红黑树
将2-3树中的每个3-node分解为红黑节点就可以得到一棵红黑树，具体操作为：[a b]=>(a)-[b]其中()代表红节点，[]代表黑节点，则上面的2-3树对应的红黑树就为(左倾就为左红右黑)：
[ 15 ]
/ \
(6)-[10] [ 18 ]
/ \ \ / \
(1)-[4] [7] [14] [17] (20)-[25]
/ \ \ / \ / \ / \ / \ \
|
V
[ 15 ]
/ \
[ 10 ] [ 18 ]
/ \ / \
(6) [14] [17] [25]
/ \ / \ / \ / \
[4] [7] (20)
/ \ / \ / \
(1)
/ \
因此：
- 没有两个红色节点是直接相连的(因为红节点只在3-node内部)
- 从根节点到每一个叶子(null节点)所经历的黑节点数量是相同的(因为2-3数的平衡性)
- 红节点是左倾的
红黑树的检索
红黑树的搜索算法与二叉检索树相同：
public V search(K key) {
Node root = LLRBTree.root;
while(root != null) {
int cmp = key.compareTo(root.key);
if (cmp < 0) root = root.left;
else if (cmp > 0) root = root.right;
else return root.val; // cmp == 0
}
return null;
}
红黑树以及节点类：
public class MyLLRBTree {
private static final boolean RED = true;
private static final boolean BLACK = false;
class Node<K extends Comparable<K>, V> {
K key;
V val;
Node left, right;
boolean color; // true: red, false: black
public Node(K k, V v, boolean isRed) {
key = k;
val = v;
color = isRed;
}
}
private boolean isRed(Node x) {
if (x == null) return false; // null Nodes are black
return x.color == RED;
}
}
红黑树的几种旋转场景：
右倾改左倾——左旋
[3]x [9]y
/ \ / \
[<3] (9)y => (3)x [>9]
/ \ / \
[3,9] [>9] [<3] [3,9]
private Node rotateLeft(Node x) {
assert isRed(x.right);
Node y = x.right;
x.right = y.left;
y.left = x;
y.color = x.color;
x.color = RED;
return y;
}
左倾改右倾——右旋(就是左旋的逆向操作)
private Node rotateRight(Node x) {
assert isRed(x.left);
Node y = x.left;
x.left = y.right;
y.right = x;
y.color = x.color;
x.color = RED;
return y;
}
颜色翻转——对应2-3树中临时4-node的拆分：
[ 5 ]x ( 5 )x
/ \ / \
( 3 )y ( 9 )z => [ 3 ]x [ 9 ]z
/ \ / \ / \ / \
[<3] [3,5] [5,9] [>9] [<3] [3,5] [5,9] [>9]
private void flipColor(Node x) {
assert !isRed(x);
assert isRed(x.left);
assert isRed(x.right);
x.color = RED;
x.left.color = x.right.color = BLACK;
}
红黑树的插入
红黑树的插入过程：
- 当仅有一个根节点的新树插入一个新节点(红色)，如果比root小则直接插入其左边，如果比root大则插入其右边后左旋，其过程对应2-3树的2-node到3-node的过程。
- 对于2-leaf(底部的2-node)的插入，先执行标准的BST插入过程，新节点为RED，若新节点是right(大于底部的2-leaf)，则对其进行左旋，其过程同样对应2-3树的2-node到3-node的过程。
- 对于3-leaf(底部的RED节点)的插入，其有两种情况，如下：
[b] [b] (b)
/ larger=> / \ flipColor=> / \
(a) (a) (c) [a] [c]
[c] [c] [b] (b)
/ smaller=> / rightRt=> / \ flipColor=> / \
(b) (b) (a) (c) [a] [c]
/
(a)
[c] [c] [c] (b)
/ between=> / leftRt=> / operation => / \
(b) (a) (b) like smaller [a] [c]
\ /
(b) (a)
因此3-leaf(底部3-node的插入过程如下)：
- 执行标准的BST插入过程，新的Node为红色
- 左旋或右旋使其达到标准的4-node(larger的情况不需要)
- 执行flipColor将红色传递至上一层
- 执行左旋保持左倾(如果出现右倾节点)
- 重复上述步骤直到root(if needed)
因此可以用上述三个函数处理LLBRBST的所有情况：
- 右子树红，左子树黑：rotateLeft
- 左子树红，左子树的左子树也红：rotateRight
- 左子树和右子树都红：flipColor
插入节点的函数：
private Node put(Node target, K key, V val) { // target: target Node of insert action
if (target == null) // Add new Node to bottom (RED color)
return new Node(key, val, RED);
int cmp = key.compareTo(target.key);
if (cmp < 0) target.left = put(target.left, key, val);
else if (cmp > 0) target.right = put(target.right, key, val);
else target.val = val; // cmp == 0, target.key == key
if (isRed(target.right) && !isRed(target.left)) target = rotateLeft(target); // Maintain left-leaning
if (isRed(target.left) && isRed(target.left.left)) target = rotateRight(target); // Balance 4-node, if target.left is RED, it won't be null
if (isRed(target.left) && isRed(target.right)) flipColor(target); // split 4-node
return target;
}
红黑树的删除
删除最小值
删除最小值操作的实现是从根节点开始递归，通过将父节点拉下来，或者是向邻居节点借一个，形成一个3-node或者4-node，再进行删除
root:
[2]
/ \ => [1 2 3]
[1] [3]
[2] [3]
/ \ => / \
[1] [3 4] [1 2] [4]
middle way:
[2 5 (6)] [3 5 (6)]
/ \ => / \
[1] [3 4] [1 2] [4]
[2 4 (5)] [4 (5)]
/ \ \ => / \
[1] [3] [1 2 3]
bottom:
[1 2 (3)] => [2 (3)]
删除最大值的逻辑与删除最小值类似。
而实际根据Key删除元素的实现只用到了删除最小值delMin
完整代码
红黑树的完整代码如下：
package structure;
public class MyLLBRTree<K extends Comparable<K>, V> {
private static final boolean RED = true;
private static final boolean BLACK = false;
class Node {
K key;
V val;
Node left, right;
boolean color; // true: red, false: black
public Node(K k, V v, boolean isRed) {
key = k;
val = v;
color = isRed;
}
}
private Node root;
public MyLLBRTree() {
root = null;
}
/* Helper Function */
private boolean isRed(Node x) {
if (x == null) return false; // null Nodes are black
return x.color == RED;
}
private Node rotateLeft(Node x) {
assert isRed(x.right);
Node y = x.right;
x.right = y.left;
y.left = x;
y.color = x.color;
x.color = RED;
return y;
}
private Node rotateRight(Node x) {
assert isRed(x.left);
Node y = x.left;
x.left = y.right;
y.right = x;
y.color = x.color;
x.color = RED;
return y;
}
private void flipColor(Node x) {
assert !isRed(x);
assert isRed(x.left);
assert isRed(x.right);
x.color = RED;
x.left.color = x.right.color = BLACK;
}
private Node balance(Node h){
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)) flipColor(h);
return h;
}
private Node put(Node target, K key, V val) { // target: target Node of insert action
if (target == null) // Add new Node to bottom (RED color)
return new Node(key, val, RED);
int cmp = key.compareTo(target.key);
if (cmp < 0) target.left = put(target.left, key, val);
else if (cmp > 0) target.right = put(target.right, key, val);
else target.val = val; // cmp == 0, target.key == key
/*
if (isRed(target.right) && !isRed(target.left)) target = rotateLeft(target); // Maintain left-leaning
if (isRed(target.left) && isRed(target.left.left)) target = rotateRight(target); // Balance 4-node, if target.left is RED, it won't be null
if (isRed(target.left) && isRed(target.right)) flipColor(target); // split 4-node
return target;
*/
return balance(target);
}
public void put(K key, V val) {
root = put(root, key, val);
root.color = BLACK;
}
public V search(K key) {
Node root = this.root;
while(root != null) {
int cmp = key.compareTo(root.key);
if (cmp < 0) root = root.left;
else if (cmp > 0) root = root.right;
else return root.val; // cmp == 0
}
return null;
}
private void reFlipColor(Node h) {
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}
private Node moveRedLeft(Node h){ // IF current Node is 2-node, need to get one from right sibling
reFlipColor(h); // get node from parent
if (isRed(h.right.left)){ // if right sibling is not RED, borrow from right sibling
h.right = rotateRight(h.right);
h = rotateLeft(h);
reFlipColor(h); // if borrow from right sibling, return node to parent
}
return h;
}
private Node delMin(Node x) {
if (x.left == null) return null; // delete current leaf node MIN
if (!isRed(x.left) && !isRed(x.left.left)) // IF x's left Child is 2-node
x= moveRedLeft(x);
x.left= delMin(x.left);
return balance(x);
}
public void delMin(){
if (!isRed(root.left) && !isRed(root.right))
root.color = RED;
root = delMin(root);
if (null != root) root.color = BLACK;
}
private Node moveRedRight(Node h){
reFlipColor(h);
if (isRed(h.left.left)){ // if left sibling is not RED, borrow from left sibling
h = rotateRight(h);
reFlipColor(h);
}
return h;
}
private Node delMax(Node h){
if (isRed(h.left))
h = rotateRight(h);
if (h.right == null)
return null; // find right leaf, delete Node
if (!isRed(h.right) && !isRed(h.right.left))
h= moveRedRight(h);
h.right = delMax(h.right);
return balance(h);
}
public void delMax(){
if (!isRed(root.right) && !isRed(root.left))
root.color = RED;
root = delMax(root);
if (null != root) root.color = BLACK;
}
private Node min(Node node) { // find min
while(node.left != null)
node = node.left;
return node;
}
private V get(Node node, K key){
if(node == null)
return null;
int cmp = key.compareTo(node.key);
if(cmp < 0)
return get(node.left, key);
else if(cmp > 0)
return get(node.right, key);
else
return node.val;
}
public void delete(K key){
if(!isRed(root.left)&& !isRed(root.right)){
root.color = RED;
}
root = delete(root, key);
if (null != root) root.color = BLACK;
}
private Node delete(Node h, K key){
if(key.compareTo(h.key) < 0) { // move left
if(isRed(h.left) && !isRed(h.left.left)){
h = moveRedLeft(h);
}
h.left = delete(h.left, key);
}
else { // >=, move right and find
if(isRed(h.left)) {
h = rotateRight(h);
}
if(key.compareTo(h.key) == 0 && h.right == null){ // key is leaf Node, delete
return null;
}
if(!isRed(h.right) && isRed(h.right.left)) { // need to borrow from parent or left sibling
h = moveRedRight(h);
}
if(key.compareTo(h.key) == 0) { // find Key but not Leaf node
Node m = min(h.right); // Swap right subTree's min Node to h
h.val = get(h.right, m.key);
h.key = m.key;
h.right = delMin(h.right); // delete min Node
}
else
h.right = delete(h.right, key);
}
return balance(h);
}
}
自平衡检索树 AVL Tree
AVL的节点类：
class Node<K extends Comparable<K>, V> {
K key;
V val;
Node left, right;
int height;
int size; // sum of all Node in current subtree
public Node(K key, V val, int height, int size) {
this.key = key;
this.val = val;
this.height = height;
this.size = size;
}
}
AVL的具体实现重点在于其旋转保持平衡，由于其具有严格的平衡性，即任一节点的左右子树高度相差不超过1，因此使用平衡因子来辅助判断其平衡性
private int balanceFactor(Node x) { // get Balance Factor, left height - right height
return height(x.left) - height(x.right);
}
左旋：
[3]x [8]y
/ \ / \
[1] [8]y => [3]x [9]
/ \ / \
[6] [9] [1] [6]
private Node rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
y.size = x.size;
x.size = size(x.left) + size(x.right) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
右旋的实现与左旋类似，不再画图赘述：
private Node rotateRight(Node x) {
Node y = x.left;
x.left = y.right;
y.right = x;
y.size = x.size;
x.size = size(x.left) + size(x.right) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
其插入可以分为四种情况
- 在左子树的左边插入导致左倾时，当前节点单次旋转，右炫
- 在左子树的右边插入导致左倾时，两次旋转，左子树左旋后，当前节点右炫
- 在右子树的右边插入导致左倾时，当前节点单次旋转，左炫
- 在右子树的左边插入导致左倾时，两次旋转，右子树右炫后，当前节点左旋
private Node put(Node x, K key, V val) {
if (x == null) {
return new Node(key, val, 0, 1);
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, val);
} else if (cmp > 0) {
x.right = put(x.right, key, val);
} else { // cmp == 0
x.val = val;
}
// after put action, rotate to keep balance
x.size = size(x.left) + size(x.right) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
int balance = balanceFactor(x);
if (balance > 1 && key.compareTo(x.left. key) < 0) { // left leaning, and insertion is at left side of left child
x = rotateRight(x);
}
if (balance < -1 && key.compareTo(x.right.key) > 0) { // right leaning, and insertion is at right side of right child
x = rotateLeft(x);
}
if (balance > 1 && key.compareTo(x.left.key) > 0) { // left leaning, and insertion is at right side of left child
x.left = rotateLeft(x.left);
x = rotateRight(x);
}
if (balance < -1 && key.compareTo(x.right.key) < 0) { // right leaning, and insertion is at left side of right child
x.right = rotateRight(x.right);
x = rotateLeft(x);
}
return x;
}
其删除操作与红黑树是类似的逻辑，若在叶子节点查找到需要删除的Key，就直接删除后keep balance，若在中间节点找到，则将右子树的最小值置换至当前节点后删除右子树的最小值，因此同样需要一个deleteMin函数来辅助完成。
具体流程为：
- 在树中查找要删除的节点。
- 如果要删除的节点有两个子节点，则找到右子树的最小节点，将其替换为要删除的节点。
- 如果要删除的节点只有一个子节点或没有子节点，则直接删除。
- 进行平衡操作，以保持树的平衡性。
Java代码实现
最后放上完整的代码
package structure;
public class MyAVLTree<K extends Comparable<K>, V> {
private class Node {
K key;
V val;
Node left, right;
int height;
int size; // sum of all Node in current subtree
public Node(K key, V val, int height, int size) {
this.key = key;
this.val = val;
this.height = height;
this.size = size;
}
}
private Node root;
public MyAVLTree() {root = null;}
private int height(Node x) { // get Height of current SubTree
if (x == null) {
return -1;
}
return x.height;
}
private int size(Node x) { // get Sum of node of current SubTree
if (x == null) {
return 0;
}
return x.size;
}
private int balanceFactor(Node x) { // get Balance Factor, left height - right height
return height(x.left) - height(x.right);
}
private Node rotateRight(Node x) {
Node y = x.left;
x.left = y.right;
y.right = x;
y.size = x.size;
x.size = size(x.left) + size(x.right) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
private Node rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
y.size = x.size;
x.size = size(x.left) + size(x.right) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
/* PUT FUNCTION */
public void put(K key, V val) { // put Key-Value
root = put(root, key, val);
}
private Node put(Node x, K key, V val) {
if (x == null) {
return new Node(key, val, 0, 1);
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, val);
} else if (cmp > 0) {
x.right = put(x.right, key, val);
} else { // cmp == 0
x.val = val;
}
// after put action, rotate to keep balance
x.size = size(x.left) + size(x.right) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
int balance = balanceFactor(x);
if (balance > 1 && key.compareTo(x.left. key) < 0) { // left leaning, and insertion is at left side of left child
x = rotateRight(x);
}
if (balance < -1 && key.compareTo(x.right.key) > 0) { // right leaning, and insertion is at right side of right child
x = rotateLeft(x);
}
if (balance > 1 && key.compareTo(x.left.key) > 0) { // left leaning, and insertion is at right side of left child
x.left = rotateLeft(x.left);
x = rotateRight(x);
}
if (balance < -1 && key.compareTo(x.right.key) < 0) { // right leaning, and insertion is at left side of right child
x.right = rotateRight(x.right);
x = rotateLeft(x);
}
return x;
}
/* GET FUNCTION */
public V get(K key) { // get or search
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 x.val;
}
}
return null;
}
private Node balance(Node x) {
x.size = size(x.left) + size(x.right) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
int balance = balanceFactor(x);
if (balance > 1 && balanceFactor(x.left) >= 0) {
x = rotateRight(x);
}
if (balance < -1 && balanceFactor(x.right) <= 0) {
x = rotateLeft(x);
}
if (balance > 1 && balanceFactor(x.left) < 0) {
x.left = rotateLeft(x.left);
x = rotateRight(x);
}
if (balance < -1 && balanceFactor(x.right) > 0) {
x.right = rotateRight(x.right);
x = rotateLeft(x);
}
return x;
}
/* DELETE FUNCTION */
public void delete(K key) {
root = delete(root, key);
}
private Node delete(Node x, K key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = delete(x.left, key);
} else if (cmp > 0) {
x.right = delete(x.right, key);
} else {
if (x.left == null) {
return x.right;
}
if (x.right == null) {
return x.left;
}
Node t = x; // Swap min Node
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
return balance(x);
}
public void deleteMin() { /* delete min element, like BRTree */
root = deleteMin(root);
}
private Node deleteMin(Node x) { /* used in delete function */
if (x.left == null) {
return x.right; // IF right == null, x is leaf Node, just delete, if right != null, return right(x is min, delete x)
}
x.left = deleteMin(x.left);
return balance(x);
}
private Node min(Node x) {
if (x.left == null) {
return x;
}
return min(x.left);
}
}
为什么HashMap在哈希冲突大于8时选用红黑树而非AVL
从上述两个实现过程就可以看出：
红黑树适用于大量插入和删除；因为它是非严格的平衡树；只要从根节点到叶子节点的最长路径不超过最短路径的2倍，就不用进行平衡调节
AVL 树是严格的平衡树，上述的最短路径与最长路径的差不能超过 1，AVL 允许的差值小；在进行大量插入和删除操作时，会频繁地进行平衡调整，严重降低效率；
红黑树虽然不是严格的平衡树，但是其依旧是平衡树；查找效率是 O(logn)；而AVL也是 O(logn)；
红黑树舍去了严格的平衡，使其插入，删除，查找的效率稳定在 O(logn)，红黑树的自平衡操作一定会在3次旋转之内解决，而 AVL 往往要比红黑树多；反观 AVL 树，查找没问题 O(logn)，但是为了保证高度平衡，动态插入和删除的代价也随之增加，综合效率肯定达不到 O(logn)
