定義
平衡二叉樹(shù)勃痴，是對(duì)二叉搜索樹(shù)的一種優(yōu)化季春。
向二叉搜索樹(shù)中插入元素時(shí)洗搂，不同的插入次序，將構(gòu)造出不同結(jié)構(gòu)的樹(shù)载弄。通俗來(lái)講耘拇，就是會(huì)導(dǎo)致樹(shù)的深度和平均查找長(zhǎng)度(ASL averge search length)不同；以下圖為例宇攻。
明顯可以看出惫叛，中間(b)這種結(jié)構(gòu)是比較好的。整個(gè)二叉搜索樹(shù)左右兩邊顯得比較平均逞刷，不像最后一種完全成了一顆右斜樹(shù)嘉涌，或者說(shuō)是單向鏈表，同時(shí)也可以看到其ASL=3.0 是這三種結(jié)構(gòu)中最小的夸浅。
總的來(lái)說(shuō)洛心，目的就是想讓整個(gè)二叉搜索樹(shù)變得比較矮胖，而不是高瘦题篷，或者是一邊倒的傾斜。因?yàn)樘浚忠馕吨鴺?shù)比較低番枚，使得查找某個(gè)元素的能更快速。
平衡因子：Balance Factor,簡(jiǎn)稱BF,BF(T)=hL-hR. 其中L和hR分別為二叉樹(shù)左右子樹(shù)的高度损敷。
平衡二叉樹(shù)：(AVL 樹(shù)）：空樹(shù)葫笼，或者任一結(jié)點(diǎn)左、右子樹(shù)高度差的絕對(duì)值不超過(guò)1. 即|BF(T)|<=1.
圖中結(jié)點(diǎn)3和5的平衡因子均為2拗馒，因此不是平衡二叉樹(shù)路星。最后一棵樹(shù)，根節(jié)點(diǎn)7平衡因子為2诱桂，同樣不是平衡二叉樹(shù)洋丐。
對(duì)于給定結(jié)點(diǎn)數(shù)為n的AVL樹(shù)，最大高度為O(log2n).
也就說(shuō)挥等，從n個(gè)數(shù)中友绝，查找一個(gè)特定值時(shí)，最多需要log2n次肝劲。因此迁客，AVL 是一種特別適合進(jìn)行查找操作的樹(shù)郭宝。
平衡二叉樹(shù)的調(diào)整
四種失衡的情況
在平衡二叉樹(shù)中，當(dāng)我們插入新的元素時(shí)掷漱，為了保證二叉搜索樹(shù)的特性粘室，很容易導(dǎo)致某些結(jié)點(diǎn)失衡，即該結(jié)點(diǎn)的平衡因子大于1卜范。
而在二叉樹(shù)中衔统，任意結(jié)點(diǎn)孩子最多只有左右兩個(gè)，而且導(dǎo)致失去平衡的必要條件就是當(dāng)前結(jié)點(diǎn)的兩顆子樹(shù)的高度差等于2先朦。因此缰冤，致使一個(gè)結(jié)點(diǎn)失衡的插入操作有以下4中。
- 在結(jié)點(diǎn)的左子樹(shù)的左子樹(shù)插入元素,LL 插入喳魏；
- 在結(jié)點(diǎn)的左子樹(shù)的右子樹(shù)插入元素,LR 插入棉浸；
- 在結(jié)點(diǎn)的右子樹(shù)的左子樹(shù)插入元素,RL 插入；
- 在結(jié)點(diǎn)的右子樹(shù)的右子樹(shù)插入元素,RR 插入刺彩。
- LL(一）中結(jié)點(diǎn)1的插入導(dǎo)致結(jié)點(diǎn)8失衡迷郑，而插入的位置是在其左子樹(shù)的左子樹(shù)上，同樣LL(二）中创倔，結(jié)點(diǎn)3插入同樣導(dǎo)致結(jié)點(diǎn)8失衡嗡害，這里需要注意子樹(shù)是從受影響的結(jié)點(diǎn)算起，雖然3插在了右邊畦攘，但他依舊是在8（失衡結(jié)點(diǎn)）左子樹(shù)的左子樹(shù)上霸妹，因此屬于LL 插入。
- LR(一）,結(jié)點(diǎn)5插入導(dǎo)致結(jié)點(diǎn)8失衡知押，插入位置是在其左子樹(shù)的右子樹(shù)上叹螟，同樣LR(二)結(jié)點(diǎn)7的插入也是同理，因此這二者都屬于LR 插入台盯。
后面兩種失衡現(xiàn)象可以當(dāng)做是前兩者的鏡像罢绽，原理都是一樣的。
對(duì)四種失衡情況的調(diào)整策略
面對(duì)以上4種失衡的情況静盅，在AVL 樹(shù)中將采用LL(左左)良价，LR(左右)，RR(右右)和RL(右左) 四種旋轉(zhuǎn)方式進(jìn)行調(diào)整蒿叠。
1. LL(左左）旋轉(zhuǎn)
如圖明垢，這種情況下BL結(jié)點(diǎn)插入元素導(dǎo)致結(jié)點(diǎn)A失衡，因此我們的操作就是圍繞失衡的結(jié)點(diǎn)（圖中A）和導(dǎo)致其失衡的結(jié)點(diǎn)（圖中B）進(jìn)行栈虚。具體來(lái)說(shuō)就是圍繞結(jié)點(diǎn)B 將樹(shù)順時(shí)針（左手）旋轉(zhuǎn)袖外，最終結(jié)果就是B成為了根節(jié)點(diǎn)（相對(duì)而言），A 變成了B的右子樹(shù)魂务，而B(niǎo)原來(lái)的右子樹(shù)（BR）變成了A 的左子樹(shù)曼验。
看一下代碼實(shí)現(xiàn)：
/**
* 左旋
*
* @param node 失衡結(jié)點(diǎn)
* @return 旋轉(zhuǎn)后根節(jié)點(diǎn)
*/
private TreeNode<T> leftRotate(TreeNode<T> node) {
// 將失衡結(jié)點(diǎn)的左子樹(shù)賦給一個(gè)臨時(shí)結(jié)點(diǎn)泌射，也就是將A的左子樹(shù)B 賦給新的結(jié)點(diǎn)
TreeNode<T> newRoot = node.leftChild;
// 將B 被右子樹(shù)BR 掛在A 的左子樹(shù)上
node.leftChild = newRoot.rightChild;
// B 的右子樹(shù)為失衡的結(jié)點(diǎn)即A
newRoot.rightChild = node;
// 結(jié)點(diǎn)A 的高度為左右子樹(shù)高度最大值加1
node.height = getMax(height(node.leftChild), height(node.rightChild)) + 1;
// 結(jié)點(diǎn)B 的高度為左右子樹(shù)高度最大值加1
newRoot.height = getMax(height(newRoot.leftChild), newRoot.height) + 1;
// 返回根節(jié)點(diǎn)
return newRoot;
}
結(jié)合注釋?xiě)?yīng)該很好理解。
2. RR(右右）旋轉(zhuǎn)
理解了LL鬓照，RR就是同理了熔酷，圍繞的同樣是導(dǎo)致失衡的結(jié)點(diǎn)B,只不過(guò)旋轉(zhuǎn)方向變成了逆時(shí)針（右手向內(nèi)）。
/**
* 右旋
*
* @param node
* @return
*/
private TreeNode<T> rightRotate(TreeNode<T> node) {
TreeNode<T> newRoot = node.rightChild;
node.rightChild = newRoot.leftChild;
newRoot.leftChild = node;
node.height = getMax(height(node.leftChild), height(node.rightChild)) + 1;
newRoot.height = getMax(height(newRoot.rightChild), node.height) + 1;
return newRoot;
}
3. LR(右左）旋轉(zhuǎn)
看上面的圖可能有點(diǎn)暈豺裆，這里看以具體的例子拒秘。
上圖中Jan結(jié)點(diǎn)的插入導(dǎo)致May結(jié)點(diǎn)失衡，而Jan結(jié)點(diǎn)又處在May結(jié)點(diǎn)左子樹(shù)的右子樹(shù)上臭猜，是LR 插入導(dǎo)致的失衡躺酒，面對(duì)這種情況我們可以進(jìn)行LR旋轉(zhuǎn)，需要關(guān)注的三個(gè)結(jié)點(diǎn)是May,Aug和Mar蔑歌。具體來(lái)說(shuō)羹应，LR 旋轉(zhuǎn)可以分解為RR旋轉(zhuǎn)和LL旋轉(zhuǎn)。首先圍繞Aug和Mar,進(jìn)行一次RR旋轉(zhuǎn)次屠，然后圍繞Mar和May在進(jìn)行一次LL旋轉(zhuǎn)园匹。這樣最終就完成了LR 旋轉(zhuǎn)，最終的結(jié)果是樹(shù)仍然為AVL樹(shù)劫灶。
/**
* LR 左右旋轉(zhuǎn)
*
* @param node
* @return
*/
private TreeNode<T> leftRightRotate(TreeNode<T> node) {
// 首先圍繞失衡結(jié)點(diǎn)的左子樹(shù)(圖中Aug) 和Mar進(jìn)行一次右旋裸违，這樣Mar 和 Aug 換了位置
node.leftChild = rightRotate(node.leftChild);
// 最后，圍繞May和Mar進(jìn)行一次左旋
return leftRotate(node);
}
4. RL(左右）旋轉(zhuǎn)
前面說(shuō)過(guò)了本昏，RL其實(shí)就是LR 的鏡像供汛，因此這里道理都是一樣的，只過(guò)順序顛倒而已涌穆。
/**
* RL 右左旋轉(zhuǎn)
*
* @param node
* @return
*/
private TreeNode<T> rightLeftRotate(TreeNode<T> node) {
node.rightChild = leftRotate(node.rightChild);
return rightRotate(node);
}
AVL 樹(shù)的實(shí)現(xiàn)
以上就是AVL 樹(shù)所有的理論基礎(chǔ)紊馏，下面看看如何去實(shí)現(xiàn)。
- 結(jié)點(diǎn)的定義
AVL 樹(shù)首先是二叉搜索樹(shù)蒲犬，因此它的結(jié)點(diǎn)也必須是可比較。同時(shí)為了方便岸啡，會(huì)加入一個(gè)表示當(dāng)前結(jié)點(diǎn)高度的height字段原叮。
/**
* Created by engineer on 2017/10/31.
*
* AVL 樹(shù)節(jié)點(diǎn)定義
*/
public class TreeNode<T extends Comparable<T>> {
// 數(shù)據(jù)域
private T data;
// 左子樹(shù)
public TreeNode<T> leftChild;
// 右子樹(shù)
public TreeNode<T> rightChild;
//當(dāng)前結(jié)點(diǎn)的高度
public int height;
public TreeNode(T data) {
this(null, data, null);
}
public TreeNode(TreeNode leftChild, T data, TreeNode rightChild) {
this(data, leftChild, rightChild, 0);
}
public TreeNode(T data, TreeNode<T> leftChild, TreeNode<T> rightChild, int height) {
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.height = height;
}
public T getData() {
return data;
}
public TreeNode<T> getLeftChild() {
return leftChild;
}
public TreeNode<T> getRightChild() {
return rightChild;
}
public void setData(T data) {
this.data = data;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
}
- 平衡二叉樹(shù)插入
/**
* 插入結(jié)點(diǎn)
*
* @param value
*/
public void insert(T value) {
root = insert(root, value);
}
private TreeNode<T> insert(TreeNode<T> node, T value) {
if (node == null) {
// 新建節(jié)點(diǎn)
node = new TreeNode<T>(value);
if (node == null) {
return null;
}
} else {
int cmp = value.compareTo(node.getData());
if (cmp < 0) { // 應(yīng)該將value插入到"node的左子樹(shù)"的情況
node.leftChild = insert(node.leftChild, value);
// 插入節(jié)點(diǎn)后，若AVL樹(shù)失去平衡巡蘸，則進(jìn)行相應(yīng)的調(diào)節(jié)奋隶。
if (height(node.leftChild) - height(node.rightChild) == 2) {
if (value.compareTo(node.leftChild.getData()) < 0)
node = leftRotate(node);
else
node = leftRightRotate(node);
}
} else if (cmp > 0) { // 應(yīng)該將value插入到"node的右子樹(shù)"的情況
node.rightChild = insert(node.rightChild, value);
// 插入節(jié)點(diǎn)后，若AVL樹(shù)失去平衡悦荒，則進(jìn)行相應(yīng)的調(diào)節(jié)唯欣。
if (height(node.rightChild) - height(node.leftChild) == 2) {
if (value.compareTo(node.rightChild.getData()) > 0)
node = rightRotate(node);
else
node = rightLeftRotate(node);
}
} else { // cmp==0
System.out.println("添加失敗：不允許添加相同的節(jié)點(diǎn)搬味！");
}
}
node.height = getMax(height(node.leftChild), height(node.rightChild)) + 1;
return node;
}
測(cè)試平衡二叉樹(shù)
public class AvlTreeTest {
private static Integer[] arrays = new Integer[]{10, 8, 3, 12, 9, 4, 5, 7, 1, 11, 17};
public static void main(String[] args) {
AvlTree<Integer> mAvlTree = new AvlTree<>();
for (int i = 0; i < arrays.length; i++) {
mAvlTree.insert(arrays[i]);
}
mAvlTree.printTree();
}
}
這里我們測(cè)試平衡二叉樹(shù)采用和上一節(jié)二叉搜索樹(shù)中同樣的數(shù)據(jù)境氢。首先看一下樹(shù)遍歷打印結(jié)果：
前序遍歷：8 4 3 1 5 7 10 9 12 11 17
中序遍歷：1 3 4 5 7 8 9 10 11 12 17
后序遍歷：1 3 7 5 4 9 11 17 12 10 8
這樣的遍歷的結(jié)構(gòu)蟀拷，相對(duì)應(yīng)的平衡二叉樹(shù)將是如下：
在和上一節(jié)構(gòu)造的二叉樹(shù)對(duì)比一下:
很明顯，平衡二叉樹(shù)是一種更加友好的搜索樹(shù)萍聊，在平衡二叉樹(shù)中查找7這個(gè)元素问芬，最大比較4次，而在普通的二叉搜索樹(shù)中需要找6次寿桨〈诵疲總體來(lái)說(shuō)，平衡二叉樹(shù)結(jié)合平衡因子構(gòu)造出了一顆十分便于查找的二叉搜索樹(shù)亭螟。
好了挡鞍，平衡二叉樹(shù)就到這里了。
參考文檔
