一器钟、平衡二叉樹的定義
首先崇裁，平衡二叉樹是一棵二叉查找樹哀澈。此外滓窍，他的每一個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度之差都小于等于1l
因?yàn)槠胶舛鏄涞钠胶馓匦裕恳粋€(gè)結(jié)點(diǎn)的左子樹和右子樹的高度之差都小于等于1）与帆，它的搜索效率很高log(n)了赌。一顆n個(gè)結(jié)點(diǎn)的平衡二叉樹的高度最大是log(n) + 1。
平衡因子：我們將平衡二叉樹上結(jié)點(diǎn)的左子樹深度減去右子樹深度的值稱為平衡因子玄糟。平衡二叉樹上所有結(jié)點(diǎn)的平衡因子都只可能是0勿她， 1， -1阵翎。
最小不平衡子樹：當(dāng)往平衡二叉樹中插入一個(gè)結(jié)點(diǎn)逢并，造成這棵二叉樹不再平衡時(shí)，我們稱以距離插入結(jié)點(diǎn)最近的并且平衡因子絕對(duì)值大于1的結(jié)點(diǎn)為根的子樹叫做最小不平衡子樹郭卫。
請(qǐng)找出下圖中的最小不平衡子樹砍聊。
二、平衡二叉樹的實(shí)現(xiàn)原理
2.1 基本旋轉(zhuǎn)操作
平衡二叉樹是在二叉查找樹原理的基礎(chǔ)上贰军，每次增加或者刪除結(jié)點(diǎn)后玻蝌，都應(yīng)該重新維持樹的平衡。
維持樹的平衡的基本操作就是旋轉(zhuǎn)词疼。
首先我們看一下最基礎(chǔ)的右旋（左旋和右旋道理一樣）俯树。
我們假設(shè)cur為需要右旋的結(jié)點(diǎn)，parent = cur.parent寒跳，left = cur.left聘萨。
那么右旋的偽代碼就是
public void rightRotate(BiTNode cur) {
BiTNode parent = cur.parent;
BiTNode left = cur.left;
left.parent = parent; //連接左子結(jié)點(diǎn)和父節(jié)點(diǎn)
if (parent.left == cur) {
parent.left = left;
} else {
parent.right = left;
}
cur.left = left.right; //使left的右子結(jié)點(diǎn)稱為cur的左子結(jié)點(diǎn)
if (left.right != null) {
left.right.parent = cur;
}
left.right = cur; //使cur稱為left的右子結(jié)點(diǎn)
cur.parent = left;
}
2.2 兩次旋轉(zhuǎn)操作
有些情況下竹椒，不能用一次旋轉(zhuǎn)就完成樹的平衡童太。比如如下這種情況。
上圖中結(jié)點(diǎn)中黑色數(shù)字表示結(jié)點(diǎn)存儲(chǔ)的值胸完，紅色數(shù)字表示結(jié)點(diǎn)的平衡因子书释。結(jié)點(diǎn)5的平衡因子是2，因此結(jié)點(diǎn)5需要右旋赊窥。但是結(jié)點(diǎn)5的左子結(jié)點(diǎn)結(jié)點(diǎn)2的平衡因子是-1爆惧，直接右旋依然是不平衡的，如下圖所示锨能。
這時(shí)候扯再，我們應(yīng)該先將結(jié)點(diǎn)2左旋芍耘，使得他和結(jié)點(diǎn)5的平衡因子正負(fù)值一樣，然后再對(duì)結(jié)點(diǎn)5右旋熄阻。
2.3 插入一個(gè)結(jié)點(diǎn)
首先我們這樣定義平衡二叉樹的結(jié)點(diǎn)斋竞。他相比二叉查找樹結(jié)點(diǎn)多了一個(gè)平衡因子，用于存儲(chǔ)當(dāng)前結(jié)點(diǎn)的平衡狀態(tài)秃殉；還多了一個(gè)父節(jié)點(diǎn)坝初，因?yàn)閖ava不能傳指針，因此需要一個(gè)父節(jié)點(diǎn)引用來進(jìn)行刪除操作钾军。
//平衡二叉樹結(jié)點(diǎn)
public static class BiTNode {
int val = 0; //結(jié)點(diǎn)的值
int bf = 0; //平衡因子
BiTNode left = null; //左子樹
BiTNode right = null; //右子樹
BiTNode parent = null; //父結(jié)點(diǎn)
}
平衡二叉樹的插入可以分為兩個(gè)步驟：1.插入一個(gè)結(jié)點(diǎn)鳄袍，2.進(jìn)行平衡操作。
2.3.1 插入結(jié)點(diǎn)
首先我們按照二叉查找樹的操作插入一個(gè)結(jié)點(diǎn)（遞歸）吏恭。
偽代碼如下
if (cur == null) { //插入結(jié)點(diǎn)
cur = new BiTNode();
cur.val = key;
cur.bf = 0;
cur.parent = parent;
taller = true;
if (parent != null) {
if (parent.val < cur.val) {
parent.right = cur;
} else {
parent.left = cur;
}
} else {
root = cur;
cur.parent = null;
}
else if (cur.val == key) { //已有結(jié)點(diǎn)拗小，不需要插入
taller = false;
return false;
} else if (cur.val > key) { //插入到左子樹中
insert(cur.left, cur, key)
} else { //插入右子樹中
insert(cur.right, cur, key)
}
2.3.2 平衡操作
進(jìn)行回溯，不斷計(jì)算插入路徑中父節(jié)點(diǎn)的平衡因樱哼，出現(xiàn)不平衡狀況十籍，進(jìn)行旋轉(zhuǎn)使之重新平衡。
三唇礁、代碼
package AVLTree;
public class AVLTree {
private BiTNode root = null;
private boolean taller = false;
public void setRoot(int data) {
if (root == null) {
root = new BiTNode();
root.val = data;
} else {
root.val = data;
}
}
/**
* 插入前是平衡狀態(tài)勾栗，插入后可能會(huì)是不平衡狀態(tài)，旋轉(zhuǎn)后是平衡狀態(tài)
* @param key
* @return
*/
public boolean insert(int key) {
return insert(root, null, key);
}
private boolean insert(BiTNode cur, BiTNode parent, int key) {
if (cur == null) { //插入結(jié)點(diǎn)
cur = new BiTNode();
cur.val = key;
cur.bf = 0;
cur.parent = parent;
taller = true;
if (parent != null) {
if (parent.val < cur.val) {
parent.right = cur;
} else {
parent.left = cur;
}
} else {
root = cur;
cur.parent = null;
}
} else { //搜索盏筐，插入并平衡
if (cur.val == key) { //已有結(jié)點(diǎn)围俘，不需要插入
taller = false;
return false;
} else if (cur.val > key) { //插入到左子樹中
if (!insert(cur.left, cur, key)) { //插入，如果已存在琢融，不需要平衡
return false;
}
if (taller) { //如果有增長(zhǎng)界牡，需要平衡
if (cur.bf == 0) {
taller = true;
cur.bf = 1;
} else if (cur.bf == 1) {
leftBalance(cur);
taller = false;
} else {
cur.bf = 0;
taller = false;
}
}
} else { //插入右子樹中
if (!insert(cur.right, cur, key)) { //插入，如果已存在漾抬，不需要平衡
return false;
}
if (taller) { //如果有增長(zhǎng)宿亡，需要平衡
if (cur.bf == 0) {
taller = true;
cur.bf = -1;
} else if (cur.bf == 1) {
cur.bf = 0;
taller = false;
} else {
rightBalance(cur);
taller = false;
}
}
}
}
return true;
}
/**
* 5 5
* * * * *
* 2 6 3 6
* * * * *
* 1 3 2 4
* * *
* 4 1
* @param node
*/
public void leftBalance(BiTNode node) {
BiTNode leftSon = node.left;
BiTNode leftSonRight = leftSon.right;
switch (leftSon.bf) {
case 1:
node.bf = 0;
rightBalance(node);
break;
case -1:
switch(leftSonRight.bf) {
case 1:
node.bf = -1;
leftSon.bf = 0;
break;
case -1:
node.bf = 0;
leftSon.bf = 1;
break;
case 0:
node.bf = 0;
leftSon.bf = 0;
break;
}
leftSonRight.bf = 0;
leftRotate(leftSon);
rightRotate(node);
break;
}
}
/**
* 4 4 4 4
* * * * * * * * *
* 2 6 2 6 2 7 2 7
* * * * * * * * *
* 5 7 5 8 6 8 5 8
* * * * *
* 8 7 5 6
* @param node
*/
public void rightBalance(BiTNode node) {
BiTNode rightSon = node.left;
BiTNode rightSonLeft = null;
switch (rightSon.bf) {
case -1:
rightSon.bf = 0;
leftRotate(node);
break;
case 1:
switch (rightSonLeft.bf) {
case 0: //不可能存在這種情況
node.bf = 0;
rightSon.bf = 0;
break;
case 1:
node.bf = 0;
rightSon.bf = -1;
break;
case -1:
node.bf = 1;
rightSon.bf = 0;
break;
}
rightSonLeft.bf = 0;
rightRotate(rightSon);
leftRotate(node);
break;
}
}
/**
* 簡(jiǎn)單右旋
* @param node
*/
public void rightRotate(BiTNode node) {
BiTNode parent = node.parent;
BiTNode leftSon = node.left;
leftSon.parent = parent;
if (parent != null) {
if (parent.left == node) {
parent.left = leftSon;
} else {
parent.right = leftSon;
}
} else {
root = leftSon;
leftSon.parent = null;
}
node.left = leftSon.right;
if (leftSon.right != null) {
leftSon.right.parent = node;
}
leftSon.right = node;
node.parent = leftSon;
}
/**
* 簡(jiǎn)單左旋
* @param node
*/
public void leftRotate(BiTNode node) {
BiTNode parent = node.parent;
BiTNode rightSon = node.right;
rightSon.parent = parent;
if (parent != null) {
if (parent.left == node) {
parent.left = rightSon;
} else {
parent.right = rightSon;
}
} else {
root = rightSon;
rightSon.parent = null;
}
node.right = rightSon.left;
if (rightSon.left != null) {
rightSon.left.parent = node;
}
rightSon.left = node;
node.parent = rightSon;
}
//平衡二叉樹結(jié)點(diǎn)
public static class BiTNode {
int val = 0; //結(jié)點(diǎn)的值
int bf = 0; //平衡因子
BiTNode left = null; //左子樹
BiTNode right = null; //右子樹
BiTNode parent = null; //父結(jié)點(diǎn)
}
}
