手撕左傾紅黑樹(left-learning R-B BST)與自平衡二叉檢索樹(AVL)
面試意難平霹抛，怒撕紅黑樹
參考視頻：普林斯頓Sedgewick教授的算法課程視頻
https://www.coursera.org/learn/algorithms-part1
左傾紅黑樹 LLRB BST
2-3 Tree
2-3樹節(jié)點(diǎn)：允許每個(gè)節(jié)點(diǎn)有1或2個(gè)鍵值
- 2-node: 有一個(gè)鍵值，兩個(gè)子節(jié)點(diǎn)
- 3-node: 有兩個(gè)鍵值巍糯，三個(gè)子節(jié)點(diǎn)
對(duì)于2節(jié)點(diǎn)[a]其兩個(gè)子節(jié)點(diǎn)分別代表范圍<a和>a，對(duì)于3節(jié)點(diǎn)[a b]其三個(gè)子節(jié)點(diǎn)分別代表范圍<a婚苹，>a && <b低千，>b。
[15]
/ \
[6 10] [18]
/ \ \ / \
[1 4] [7] [14] [17] [20 25]
/ \ \ / \ / \ / \ / \ \
其中[6 10]和[1 4]都是3-node
如果要向其中插入值13烙肺，則最終會(huì)落在[14]節(jié)點(diǎn)上并且變?yōu)?-node
[ 15 ]
/ \
[6 10] [ 18 ]
/ \ \ / \
[1 4] [7] [13 14] [17] [20 25]
/ \ \ / \ / \ \ / \ / \ \
如果要向原2-3樹插入值22，則其最終會(huì)落在節(jié)點(diǎn)[20 25]上氧卧，并且臨時(shí)生成4節(jié)點(diǎn)后分解桃笙，4節(jié)點(diǎn)的中間鍵值會(huì)向上合并，剩下兩個(gè)變成新的葉子
[ 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樹的分裂是向上的(底部形成臨時(shí)4節(jié)點(diǎn)后分裂為兩個(gè)節(jié)點(diǎn)并且中間鍵值向上合并沙绝，若向上合并導(dǎo)致父節(jié)點(diǎn)變?yōu)?節(jié)點(diǎn)會(huì)繼續(xù)向上合并搏明，若根節(jié)點(diǎn)變?yōu)?節(jié)點(diǎn)就會(huì)分裂形成新的根節(jié)點(diǎn))因此能夠保證其插入值后高度的平衡鼠锈。
完整代碼
2-3樹的Java代碼實(shí)現(xiàn)：
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檢索樹的原理很簡單，但是很繁瑣星著，因?yàn)樗泻芏喾N情況购笆，而在紅黑樹中，用巧妙的方法使用了2個(gè)結(jié)點(diǎn)解決了3-Node的問題
2-3樹到紅黑樹
將2-3樹中的每個(gè)3-node分解為紅黑節(jié)點(diǎn)就可以得到一棵紅黑樹虚循，具體操作為：[a b]=>(a)-[b]其中()代表紅節(jié)點(diǎn)同欠，[]代表黑節(jié)點(diǎn)，則上面的2-3樹對(duì)應(yīng)的紅黑樹就為(左傾就為左紅右黑)：
[ 15 ]
/ \
(6)-[10] [ 18 ]
/ \ \ / \
(1)-[4] [7] [14] [17] (20)-[25]
/ \ \ / \ / \ / \ / \ \
|
V
[ 15 ]
/ \
[ 10 ] [ 18 ]
/ \ / \
(6) [14] [17] [25]
/ \ / \ / \ / \
[4] [7] (20)
/ \ / \ / \
(1)
/ \
因此：
- 沒有兩個(gè)紅色節(jié)點(diǎn)是直接相連的(因?yàn)榧t節(jié)點(diǎn)只在3-node內(nèi)部)
- 從根節(jié)點(diǎn)到每一個(gè)葉子(null節(jié)點(diǎn))所經(jīng)歷的黑節(jié)點(diǎn)數(shù)量是相同的(因?yàn)?-3數(shù)的平衡性)
- 紅節(jié)點(diǎn)是左傾的
紅黑樹的檢索
紅黑樹的搜索算法與二叉檢索樹相同：
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;
}
紅黑樹以及節(jié)點(diǎn)類：
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;
}
}
紅黑樹的幾種旋轉(zhuǎn)場景：
右傾改左傾——左旋
[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;
}
顏色翻轉(zhuǎn)——對(duì)應(yīng)2-3樹中臨時(shí)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;
}
紅黑樹的插入
紅黑樹的插入過程：
- 當(dāng)僅有一個(gè)根節(jié)點(diǎn)的新樹插入一個(gè)新節(jié)點(diǎn)(紅色)横缔，如果比root小則直接插入其左邊铺遂，如果比root大則插入其右邊后左旋，其過程對(duì)應(yīng)2-3樹的2-node到3-node的過程茎刚。
- 對(duì)于2-leaf(底部的2-node)的插入娃循，先執(zhí)行標(biāo)準(zhǔn)的BST插入過程，新節(jié)點(diǎn)為RED斗蒋，若新節(jié)點(diǎn)是right(大于底部的2-leaf)，則對(duì)其進(jìn)行左旋笛质，其過程同樣對(duì)應(yīng)2-3樹的2-node到3-node的過程泉沾。
- 對(duì)于3-leaf(底部的RED節(jié)點(diǎn))的插入，其有兩種情況妇押，如下：
[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的插入過程如下)：
- 執(zhí)行標(biāo)準(zhǔn)的BST插入過程跷究，新的Node為紅色
- 左旋或右旋使其達(dá)到標(biāo)準(zhǔn)的4-node(larger的情況不需要)
- 執(zhí)行flipColor將紅色傳遞至上一層
- 執(zhí)行左旋保持左傾(如果出現(xiàn)右傾節(jié)點(diǎn))
- 重復(fù)上述步驟直到root(if needed)
因此可以用上述三個(gè)函數(shù)處理LLBRBST的所有情況：
- 右子樹紅，左子樹黑：rotateLeft
- 左子樹紅敲霍，左子樹的左子樹也紅：rotateRight
- 左子樹和右子樹都紅：flipColor
插入節(jié)點(diǎn)的函數(shù)：
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;
}
紅黑樹的刪除
刪除最小值
刪除最小值操作的實(shí)現(xiàn)是從根節(jié)點(diǎn)開始遞歸俊马，通過將父節(jié)點(diǎn)拉下來，或者是向鄰居節(jié)點(diǎn)借一個(gè)肩杈，形成一個(gè)3-node或者4-node柴我，再進(jìn)行刪除
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)]
刪除最大值的邏輯與刪除最小值類似。
而實(shí)際根據(jù)Key刪除元素的實(shí)現(xiàn)只用到了刪除最小值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的節(jié)點(diǎn)類：
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的具體實(shí)現(xiàn)重點(diǎn)在于其旋轉(zhuǎn)保持平衡蒲凶，由于其具有嚴(yán)格的平衡性酸钦，即任一節(jié)點(diǎn)的左右子樹高度相差不超過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;
}
右旋的實(shí)現(xiàn)與左旋類似，不再畫圖贅述：
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;
}
其插入可以分為四種情況
- 在左子樹的左邊插入導(dǎo)致左傾時(shí)界睁，當(dāng)前節(jié)點(diǎn)單次旋轉(zhuǎn)，右炫
- 在左子樹的右邊插入導(dǎo)致左傾時(shí)兵拢，兩次旋轉(zhuǎn)翻斟，左子樹左旋后，當(dāng)前節(jié)點(diǎn)右炫
- 在右子樹的右邊插入導(dǎo)致左傾時(shí)说铃，當(dāng)前節(jié)點(diǎn)單次旋轉(zhuǎn)访惜，左炫
- 在右子樹的左邊插入導(dǎo)致左傾時(shí)嘹履，兩次旋轉(zhuǎn)，右子樹右炫后疾牲，當(dāng)前節(jié)點(diǎn)左旋
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;
}
其刪除操作與紅黑樹是類似的邏輯植捎，若在葉子節(jié)點(diǎn)查找到需要?jiǎng)h除的Key，就直接刪除后keep balance阳柔，若在中間節(jié)點(diǎn)找到焰枢，則將右子樹的最小值置換至當(dāng)前節(jié)點(diǎn)后刪除右子樹的最小值，因此同樣需要一個(gè)deleteMin函數(shù)來輔助完成舌剂。
具體流程為：
- 在樹中查找要?jiǎng)h除的節(jié)點(diǎn)济锄。
- 如果要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，則找到右子樹的最小節(jié)點(diǎn)霍转，將其替換為要?jiǎng)h除的節(jié)點(diǎn)荐绝。
- 如果要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)或沒有子節(jié)點(diǎn)，則直接刪除避消。
- 進(jìn)行平衡操作低滩，以保持樹的平衡性。
Java代碼實(shí)現(xiàn)
最后放上完整的代碼
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時(shí)選用紅黑樹而非AVL
從上述兩個(gè)實(shí)現(xiàn)過程就可以看出：
紅黑樹適用于大量插入和刪除岩喷；因?yàn)樗欠菄?yán)格的平衡樹恕沫；只要從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長路徑不超過最短路徑的2倍，就不用進(jìn)行平衡調(diào)節(jié)
AVL 樹是嚴(yán)格的平衡樹纱意，上述的最短路徑與最長路徑的差不能超過 1婶溯，AVL 允許的差值小偷霉；在進(jìn)行大量插入和刪除操作時(shí)迄委，會(huì)頻繁地進(jìn)行平衡調(diào)整，嚴(yán)重降低效率类少；
紅黑樹雖然不是嚴(yán)格的平衡樹叙身，但是其依舊是平衡樹；查找效率是 O(logn)硫狞；而AVL也是 O(logn)曲梗；
紅黑樹舍去了嚴(yán)格的平衡，使其插入妓忍，刪除虏两，查找的效率穩(wěn)定在 O(logn)，紅黑樹的自平衡操作一定會(huì)在3次旋轉(zhuǎn)之內(nèi)解決世剖，而 AVL 往往要比紅黑樹多定罢；反觀 AVL 樹，查找沒問題 O(logn)旁瘫，但是為了保證高度平衡祖凫，動(dòng)態(tài)插入和刪除的代價(jià)也隨之增加琼蚯，綜合效率肯定達(dá)不到 O(logn)
