完整代碼在:https://github.com/nicktming/code/tree/master/data_structure
二叉平衡樹(shù)
因?yàn)槿绻B續(xù)插入已經(jīng)排好序的鍵到二叉查找樹(shù),二叉查找樹(shù)相當(dāng)于變成了一個(gè)鏈表,查找的時(shí)間會(huì)是
O(n),為了解決這個(gè)問(wèn)題,二叉平衡樹(shù)應(yīng)運(yùn)而生.
bst_1.png
它是一 棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)要拂。
為了達(dá)成這個(gè)目標(biāo),需要通過(guò)一些手段也就是旋轉(zhuǎn)來(lái)讓樹(shù)平衡.
四種情況
- 對(duì)當(dāng)前節(jié)點(diǎn)的左孩子的左子樹(shù)改變
右旋轉(zhuǎn)- 對(duì)當(dāng)前節(jié)點(diǎn)的左孩子的右子樹(shù)改變
左-右旋轉(zhuǎn)- 對(duì)當(dāng)前節(jié)點(diǎn)的右孩子的左子樹(shù)改變
右-左旋轉(zhuǎn)- 對(duì)當(dāng)前節(jié)點(diǎn)的右孩子的右子樹(shù)改變
右旋轉(zhuǎn)
接下來(lái)一個(gè)個(gè)來(lái)分析
定義一下樹(shù)結(jié)構(gòu)
public class BinaryBalancedTree<Key extends Comparable<Key>, Value> {
private Node root;
private class Node {
Key key;
Value value;
Node left, right;
int height;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
}
public String toString() {
return "[" + key + "," + value + "," + height + "]";
}
}
private int height(Node h) {
return h == null ? -1 : h.height;
}
private int updateHeight(Node h) {
return Math.max(height(h.left), height(h.right)) + 1;
}
}
情況1: 右旋轉(zhuǎn)
balancetree_6.jpeg
往平衡樹(shù)里面增加一個(gè)節(jié)點(diǎn),也就是在M的左孩子(G)的左子樹(shù)(以D為根節(jié)點(diǎn)的左子樹(shù))中插入一個(gè)節(jié)點(diǎn)A(或者E),此時(shí)M的高度差會(huì)從1變化為2,即出現(xiàn)了不平衡. 對(duì)M節(jié)點(diǎn)進(jìn)行右旋會(huì)使樹(shù)達(dá)到平衡.
balancetree_5.jpeg
/* 右旋 */
private Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
h.height = updateHeight(h);
x.height = updateHeight(x); //h,x順序不能變
return x;
}
情況4: 左旋
balancetree_7.jpeg
往T的左右子孩子加入一個(gè)節(jié)點(diǎn)Q(或者X)都會(huì)導(dǎo)致G為根節(jié)點(diǎn)的左右子樹(shù)高度差為2出現(xiàn)不平衡,因此需要對(duì)G進(jìn)行左旋轉(zhuǎn)達(dá)到平衡.
balancetree_8.jpeg
/* 左旋 */
private Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
h.height = updateHeight(h);
x.height = updateHeight(x); //h,x順序不能變
return x;
}
情況2: 左-右旋轉(zhuǎn)
往K的左孩子插入J或者右子樹(shù)插入L都會(huì)使以M為根節(jié)點(diǎn)的左右子樹(shù)高度差為2而出現(xiàn)不平衡,然后通過(guò)一次右旋轉(zhuǎn)還是沒(méi)有達(dá)到平衡的效果,左旋轉(zhuǎn)是更加不可能.
原因: 因?yàn)橛倚D(zhuǎn)后M的左孩子就是G的右孩子,本來(lái)就是因?yàn)镚的右孩子的高度增加了使得M的左子樹(shù)高度增加從而比M的右子樹(shù)高度高了2個(gè)長(zhǎng)度.因此我們需要把G的右子樹(shù)的高度轉(zhuǎn)移到G的左子樹(shù)上面后,這樣就相當(dāng)于G的右子樹(shù)沒(méi)有增加了節(jié)點(diǎn),對(duì)M進(jìn)行右旋轉(zhuǎn)的時(shí)候就可以了.
仔細(xì)體會(huì)一下原因
balancetree_9.jpeg
balancetree_10.jpeg
/*左-右旋轉(zhuǎn)*/
private Node rotateLeftRight(Node h) {
h.left = rotateLeft(h.left);
return rotateRight(h);
}
情況3: 右-左旋轉(zhuǎn)
思想與情況2類似,給出圖以供思考
balancetree_13.jpeg
balancetree_13.jpeg
/*右-左旋轉(zhuǎn)*/
private Node rotateRightLeft(Node h) {
h.right = rotateRight(h.right);
return rotateLeft(h);
}
插入
進(jìn)入正題, 如何向二叉平衡樹(shù)中插入一個(gè)節(jié)點(diǎn), 做法與二叉查找樹(shù)類似(對(duì)二叉查找樹(shù)不了解的可以看一下我的另外一篇博客二叉查找樹(shù) Java實(shí)現(xiàn)),只是額外增加了平衡的操作. 看代碼.
public void put(Key key, Value value) {
root = put(root, key, value);
}
private Node put(Node h, Key key, Value value) {
if (h == null) return new Node(key, value);
int cmp = key.compareTo(h.key);
if (cmp < 0) {
h.left = put(h.left, key, value);
if (height(h.left) - height(h.right) == 2) { //出現(xiàn)不平衡 只會(huì)是左子樹(shù)比右子樹(shù)高2
if (key.compareTo(h.left.key) < 0) { // h.左孩子的左子樹(shù)
h = rotateRight(h); //對(duì)h進(jìn)行右旋轉(zhuǎn)
} else {
h = rotateLeftRight(h); // 對(duì)h進(jìn)行左-右旋轉(zhuǎn)
}
}
} else if (cmp > 0) {
h.right = put(h.right, key, value);
if (height(h.right) - height(h.left) == 2) { //出現(xiàn)不平衡 只會(huì)是右子樹(shù)比左子樹(shù)高2
if (key.compareTo(h.right.key) > 0) { // h.右孩子的右子樹(shù)
h = rotateLeft(h); //對(duì)h進(jìn)行左旋轉(zhuǎn)
} else {
h = rotateRightLeft(h);
}
}
} else { // 更新value
h.value = value;
}
h.height = updateHeight(h);
return h;
}
balancetree_16.jpeg
對(duì)比：
balancetree_15.jpeg
刪除
刪除也是一樣的道理,如果你對(duì)二叉查找樹(shù)的刪除比較了解的話,其實(shí)理解這個(gè)刪除操作也會(huì)比較簡(jiǎn)單.
刪除最小鍵
作為預(yù)熱我們先看一下刪除最小鍵將如何刪除.
思路其實(shí)是一樣的,直接將被刪除的節(jié)點(diǎn)的右孩子返回給上一層即可.
public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node h) {
if (h == null) return null;
if (h.left == null) return h.right;
h.left = deleteMin(h.left);
if (height(h.right) - height(h.left) == 2) {
h = rotateLeft(h);
}
return h;
}
刪除任意鍵
有三種情況:
- 被刪除的鍵只有右孩子
思想與刪除最小值很類似- 被刪除的鍵只有左孩子
思想與刪除最大值很類似- 被刪除的鍵有左右孩子
把被刪除節(jié)點(diǎn)的右子樹(shù)的最小鍵換到當(dāng)前節(jié)點(diǎn),然后刪除它的右子樹(shù)的最小鍵即可
與二叉查找樹(shù)不同的是每一次都要檢查樹(shù)是否平衡
public Node min(Node h) {
if (h == null) return h;
while (h.left != null) h = h.left;
return h;
}
public void delete (Key key) {
root = delete(root, key);
}
private Node delete(Node h, Key key) {
if (h == null) return null;
int cmp = key.compareTo(h.key);
if (cmp < 0) {
h.left = delete(h.left, key);
if (height(h.right) - height(h.left) == 2) { //出現(xiàn)不平衡 只會(huì)是右子樹(shù)比左子樹(shù)高2
h = rotateLeft(h);
}
} else if (cmp > 0) {
h.right = delete(h.right, key);
if (height(h.left) - height(h.right) == 2) { //出現(xiàn)不平衡 只會(huì)是右子樹(shù)比左子樹(shù)高2
h = rotateRight(h);
}
} else {
if (h.left == null) return h.right;
if (h.right == null) return h.left;
Node min = min(h.right);
min.right = deleteMin(h.right);
min.left = h.left;
h = min;
if (height(h.left) - height(h.right) == 2) {
h = rotateRight(h);
}
}
h.height = updateHeight(h);
return h;
}
查找
與二叉查找樹(shù)一樣的算法就不多說(shuō)了
整體代碼
import java.util.LinkedList;
import java.util.Queue;
public class BinaryBalancedTree<Key extends Comparable<Key>, Value> {
private Node root;
private class Node {
Key key;
Value value;
Node left, right;
int height;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
}
public String toString() {
return "[" + key + "," + value + "," + height + "]";
}
}
private int height(Node h) {
return h == null ? -1 : h.height;
}
private int updateHeight(Node h) {
return Math.max(height(h.left), height(h.right)) + 1;
}
/* 右旋 */
private Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
h.height = updateHeight(h);
x.height = updateHeight(x); //h,x順序不能變
return x;
}
/* 左旋 */
private Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
h.height = updateHeight(h);
x.height = updateHeight(x); //h,x順序不能變
return x;
}
/*左-右旋轉(zhuǎn)*/
private Node rotateLeftRight(Node h) {
h.left = rotateLeft(h.left);
return rotateRight(h);
}
/*右-左旋轉(zhuǎn)*/
private Node rotateRightLeft(Node h) {
h.right = rotateRight(h.right);
return rotateLeft(h);
}
public void put(Key key, Value value) {
root = put(root, key, value);
}
private Node put(Node h, Key key, Value value) {
if (h == null) return new Node(key, value);
int cmp = key.compareTo(h.key);
if (cmp < 0) {
h.left = put(h.left, key, value);
if (height(h.left) - height(h.right) == 2) { //出現(xiàn)不平衡 只會(huì)是左子樹(shù)比右子樹(shù)高2
if (key.compareTo(h.left.key) < 0) { // h.左孩子的左子樹(shù)
h = rotateRight(h); //對(duì)h進(jìn)行右旋轉(zhuǎn)
} else {
h = rotateLeftRight(h); // 對(duì)h進(jìn)行左-右旋轉(zhuǎn)
}
}
} else if (cmp > 0) {
h.right = put(h.right, key, value);
if (height(h.right) - height(h.left) == 2) { //出現(xiàn)不平衡 只會(huì)是右子樹(shù)比左子樹(shù)高2
if (key.compareTo(h.right.key) > 0) { // h.右孩子的右子樹(shù)
h = rotateLeft(h); //對(duì)h進(jìn)行左旋轉(zhuǎn)
} else {
h = rotateRightLeft(h);
}
}
} else { // 更新value
h.value = value;
}
h.height = updateHeight(h);
return h;
}
public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node h) {
if (h == null) return null;
if (h.left == null) return h.right;
h.left = deleteMin(h.left);
if (height(h.right) - height(h.left) == 2) {
h = rotateLeft(h);
}
return h;
}
public Node min(Node h) {
if (h == null) return h;
while (h.left != null) h = h.left;
return h;
}
public void delete (Key key) {
root = delete(root, key);
}
private Node delete(Node h, Key key) {
if (h == null) return null;
int cmp = key.compareTo(h.key);
if (cmp < 0) {
h.left = delete(h.left, key);
if (height(h.right) - height(h.left) == 2) { //出現(xiàn)不平衡 只會(huì)是右子樹(shù)比左子樹(shù)高2
h = rotateLeft(h);
}
} else if (cmp > 0) {
h.right = delete(h.right, key);
if (height(h.left) - height(h.right) == 2) { //出現(xiàn)不平衡 只會(huì)是右子樹(shù)比左子樹(shù)高2
h = rotateRight(h);
}
} else {
if (h.left == null) return h.right;
if (h.right == null) return h.left;
Node min = min(h.right);
min.right = deleteMin(h.right);
min.left = h.left;
h = min;
if (height(h.left) - height(h.right) == 2) {
h = rotateRight(h);
}
}
h.height = updateHeight(h);
return h;
}
public Value get(Key key) {
return get(root, key);
}
private Value get(Node h, Key key) {
if (h == null) return null;
int cmp = key.compareTo(h.key);
if (cmp < 0) return get(h.left, key);
else if (cmp > 0) return get(h.right, key);
else return h.value;
}
public void layerTraverse() {
layerTraverse(root);
}
/*
* 橫向遍歷
*/
private void layerTraverse(Node h) {
if (h == null) return;
Queue<Node> queue = new LinkedList<Node>();
queue.add(h);
while (!queue.isEmpty()) {
Queue<Node> tmp = new LinkedList<Node>();
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.print(cur + " ");
if (cur != null) {
tmp.add(cur.left);
tmp.add(cur.right);
}
}
queue = tmp;
System.out.println();
}
}
public static void main(String[] args) {
BinaryBalancedTree<String, Integer> bst = new BinaryBalancedTree<String, Integer>();
bst.put("A", 0);
bst.put("B", 1);
bst.put("C", 2);
bst.put("D", 3);
bst.put("E", 4);
bst.put("F", 5);
bst.put("G", 6);
bst.layerTraverse();
bst.delete("D");
bst.layerTraverse();
bst.delete("E");
bst.layerTraverse();
bst.delete("F");
bst.layerTraverse();
}
}
balancetree_17.jpeg
