百科定義
平衡二叉樹（Balanced Binary Tree）具有以下性質(zhì)：它是一 棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過(guò)1单芜，并且左右兩個(gè)子樹都是一棵平衡二叉樹壶硅。
平衡因子
二叉樹上節(jié)點(diǎn)的左子樹深度減去右子樹深度的值稱為平衡因子BF（Balance Factor）
平衡二叉樹的實(shí)現(xiàn)
調(diào)整平衡的基本思想：
當(dāng)在二叉排序樹中插入一個(gè)節(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了平衡募逞，若破壞鬼譬，則找出其中的最小不平衡二叉樹焚鹊，在保持二叉排序樹特性的情況下刃宵，調(diào)整最小不平衡子樹中節(jié)點(diǎn)之間的關(guān)系衡瓶，以達(dá)到新的平衡。
所謂最小不平衡子樹牲证，指離插入節(jié)點(diǎn)最近且以平衡因子的絕對(duì)值大于1的節(jié)點(diǎn)作為根的子樹哮针。
實(shí)現(xiàn)平衡的方法：
. 左旋
image.png
上圖中，最小不平衡子樹為結(jié)點(diǎn)3下面的樹坦袍，結(jié)點(diǎn)3 的平衡因子BF為-2十厢。
平衡方法為：以結(jié)點(diǎn)3進(jìn)行左旋，旋轉(zhuǎn)結(jié)果為圖8捂齐。旋轉(zhuǎn)后變?yōu)槠胶舛鏄?/p>
旋轉(zhuǎn)方法
左旋.png
如上圖蛮放，我們對(duì)X進(jìn)行左旋，為了方便表達(dá)辛燥，做如下初始定義筛武，保存左旋前節(jié)點(diǎn)的數(shù)據(jù)：
- X為node
- X的父結(jié)點(diǎn)為nodeP
- X的左結(jié)點(diǎn)為nodeL
- X的右節(jié)點(diǎn)為NodeR
- X的右子樹的左節(jié)點(diǎn)為nodeRL
- X的右子樹的右節(jié)點(diǎn)位nodeRR
變換步驟：
- node的右節(jié)點(diǎn)改為nodeRL缝其，nodeRL的父結(jié)點(diǎn)改為node
- 判斷node屬于nodeP的左孩子還是右孩子挎塌，nodeP指向nodeR，nodeR的父親結(jié)點(diǎn)改為nodeP
- nodeR指向node内边，node的父結(jié)點(diǎn)變?yōu)閚odeR
public void left_rotate(Node<E> x) {
if (x != null) {
Node<E> y = x.right;
// step 1
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
// step2
y.parent = x.parent;
if (x.parent == null) {
root = y;
} else {
if (x.parent.left == x) {
x.parent.left = y;
} else if(x.parent.right == x){
x.parent.right = y;
}
}
//step 3
y.left = x;
x.parent = y;
}
}
. 右旋
image.png
上圖中榴都，節(jié)點(diǎn)3的平衡因子為2，左邊的多于右邊漠其，需要進(jìn)行右旋嘴高，把內(nèi)容分配到右邊一部分。
右旋.jpg
同左旋和屎，定義保存右旋前一些使用到節(jié)點(diǎn)的數(shù)據(jù)
- Y 保存為node
- Y的父結(jié)點(diǎn)保存為nodeP
- Y的左節(jié)點(diǎn)保存為nodeL
- Y的右節(jié)點(diǎn)保存為nodeR
- Y的左節(jié)點(diǎn)的右孩子保存為nodeLR
- Y的左節(jié)點(diǎn)的左孩子保存為nodeLL
步驟：
- node的右孩子變?yōu)閚odeLR拴驮，nodeLR父結(jié)點(diǎn)變?yōu)閚ode
- 判斷node屬于nodeP的左孩子還是右孩子，nodeP指向nodeL柴信，nodeL的父結(jié)點(diǎn)改為nodeP
- nodeL的右孩子變?yōu)閚ode套啤，node的父結(jié)點(diǎn)變?yōu)閚odeL
public void right_rotate(Node<E> y) {
if (y != null) {
Node<E> yl = y.left;
//step1
y.left= yl.right;
if (yl.right != null) {
yl.right.parent = y;
}
// step2
yl.parent = y.parent;
if (y.parent == null) {
root = yl;
} else {
if (y.parent.left == y) {
y.parent.left = yl;
} else if (y.parent.right == y) {
y.parent.right = yl;
}
}
// step3
yl.right = y;
y.parent = yl;
}
}
插入結(jié)點(diǎn)時(shí)候，導(dǎo)致平衡樹失衡的情況分析随常，處理步驟
結(jié)點(diǎn)t的不平衡是因?yàn)樽笞訕溥^(guò)深
/**
* 左平衡操作潜沦，即結(jié)點(diǎn)t的不平衡是因?yàn)樽笞訕溥^(guò)深
*
* 1萄涯、如果新的結(jié)點(diǎn)插入到t的左孩子的左子樹中，則直接進(jìn)行右旋操作即可
* t tl
* / \ 右旋操作 / \
* tl tr -------------> tll t
* / \ / \ / \
* tll tlr lcll lclr tlr tr
* / \
* lcll lclr
*
* 2唆鸡、如果新的結(jié)點(diǎn)插入到t的左孩子的右子樹中涝影，則需要進(jìn)行分情況討論
*
* 情況a：當(dāng)t的左孩子的右子樹根節(jié)點(diǎn)的balance = RIGHT_HIGH
* t t tlr
* / \ / \ / \
* tl 6 左旋 tlr 6 右旋 tl t
* / \ -------> / \ --------> / / \
* 3 tlr tl 5 3 5 6
* \ /
* 5 3
* 情況b：當(dāng)p的左孩子的右子樹根節(jié)點(diǎn)的balance = LEFT_HIGH
*
* t t tlr
* / \ / \ / \
* tl 6 左旋 tlr 6 右旋 tl t
* / \ -------> / --------> / \ \
* 3 tlr tl 3 5 6
* / / \
* 5 3 5
*
* 情況c：當(dāng)p的左孩子的右子樹根節(jié)點(diǎn)的balance = EQUAL_HIGH
*
* t t tlr
* / \ / \ / \
* tl 7 左旋 tlr 7 右旋 tl t
* / \ -------> / \ --------> / \ / \
* 3 tlr tl 6 3 5 6 7
* / \ / \
* 5 6 3 5
* */
結(jié)點(diǎn)t的不平衡是因?yàn)樽笞訕溥^(guò)深調(diào)整代碼
private static final int LH = 1;
private static final int RH = -1;
private static final int EH = 0;
private void leftBalance(AVL<E>.Node<E> t) {
Node<E> tl = t.left;
switch (tl.balance) {
case LH: // t 的左子樹的左邊有問題，直接右旋
right_rotate(t);
tl.balance = EH;
t.balance = EH;
break;
case RH:
Node<E> tlr = tl.right;
switch (tlr.balance) {
case RH:
t.balance = EH;
tlr.balance = EH;
tl.balance = LH;
break;
case LH:
t.balance = RH;
tl.balance =EH;
tlr.balance = EH;
break;
case EH:
t.balance = EH;
tl.balance = EH;
tlr.balance =EH;
break;
//統(tǒng)一旋轉(zhuǎn)
default:
break;
}
left_rotate(t.left);
right_rotate(t);
break;
default:
break;
}
}
結(jié)點(diǎn)t的不平衡是因?yàn)橛易訕溥^(guò)深
/**
* 右平衡操作争占，即結(jié)點(diǎn)t的不平衡是因?yàn)橛易訕溥^(guò)深
*
* 1燃逻、如果新的結(jié)點(diǎn)插入到t的右孩子的右子樹中，則直接進(jìn)行左旋操作即可
*
* t tr
* / \ / \
* l tr 左旋操作 t rr
* / \ -----------> / \ / \
* rl rr l rl rrl rrr
* / \
* rrl rrr
* 2燃乍、如果新的結(jié)點(diǎn)插入到p的右孩子的左子樹中唆樊，則需要進(jìn)行分情況討論
* 情況a：當(dāng)p的右孩子的左子樹根節(jié)點(diǎn)的balance = LEFT_HIGH
*
* t t trl
* / \ / \ / \
* 2 tr 右旋 2 trl 左旋 t tr
* / \ -------> / \ -------> / \ \
* trl 5 6 tr 2 6 5
* / \
* 6 5
* 情況b：當(dāng)p的右孩子的左子樹根節(jié)點(diǎn)的balance = RIGHT_HIGH
*
* t t trl
* / \ / \ / \
* 2 tr 右旋 2 trl 左旋 t tr
* / \ -------> \ -------> / / \
* trl 5 tr 2 6 5
* \ / \
* 6 6 5
* 情況C：當(dāng)p的右孩子的左子樹根節(jié)點(diǎn)的balance = EQUAL_HIGH
* t t trl
* / \ / \ / \
* 2 tr 右旋 2 trl 左旋 t tr
* / \ -------> / \ -------> / \ / \
* trl 5 6 tr 2 6 7 5
* / \ / \
* 6 7 7 5
* */
結(jié)點(diǎn)t的不平衡是因?yàn)橛易訕溥^(guò)深調(diào)整代碼
private static final int LH = 1;
private static final int RH = -1;
private static final int EH = 0;
private void rightBalance(AVL<E>.Node<E> t) {
Node<E> tr = t.right;
switch (tr.balance) {
case RH:
left_rotate(t);
t.balance = EH;
tr.balance = EH;
break;
case LH:
Node<E> trl = tr.left;
switch (trl.balance) {
case LH:
t.balance = EH;
tr.balance = RH;
break;
case RH:
t.balance = LH;
tr.balance = EH;
break;
case EH:
t.balance = EH;
tr.balance = EH;
break;
}
trl.balance = EH;
right_rotate(t.right);
left_rotate(t);
break;
default:
break;
}
}
插入操作
public boolean inserElement(E element) {
Node<E> t = root;
if (t == null) {
root = new Node<E>(element, null);
size = 1;
root.balance = 0;
return true;
} else {
int cmp = 0;
Node<E> parent;
Comparable<? super E> e = (Comparable<? super E>)element;
do {
parent = t;
cmp = e.compareTo(t.element);
if (cmp < 0) {
t= t.left;
} else if (cmp > 0) {
t= t.right;
} else {
return false;
}
} while (t != null);
Node<E> child = new Node<E>(element, parent);
if (cmp < 0) {
parent.left = child;
} else {
parent.right = child;
}
//節(jié)點(diǎn)已經(jīng)插入，
// 檢查平衡刻蟹，回溯查找
while (parent != null) {
cmp = e.compareTo(parent.element);
//元素在左邊插入
if (cmp < 0) {
parent.balance++;
} else{ //元素在右邊插入
parent.balance --;
}
if (parent.balance == 0) {
break;
}
if (Math.abs(parent.balance) == 2) {
//出現(xiàn)平衡問題
fixAfterInsertion(parent);
break;
} else {
parent = parent.parent;
}
}
size++;
return true;
}
}
private void fixAfterInsertion(AVL<E>.Node<E> parent) {
if (parent.balance == 2) {
leftBalance(parent);
}
if (parent.balance == -2) {
rightBalance(parent);
}
}
全部代碼
import java.util.LinkedList;
public class AVL<E extends Comparable<E>> {
private Node<E> root;
private int size = 0;
private static final int LH = 1;
private static final int RH = -1;
private static final int EH = 0;
public void midOrderDisplay(Node root) {
if (root == null) {
return;
} else {
midOrderDisplay(root.left);
System.out.println("midOrder: " + root.element);
midOrderDisplay(root.right);
}
}
/**
* node insert,check balance and keep balance
* @author LK
*
* @param <E>
*/
public boolean inserElement(E element) {
Node<E> t = root;
if (t == null) {
root = new Node<E>(element, null);
size = 1;
root.balance = 0;
return true;
} else {
int cmp = 0;
Node<E> parent;
Comparable<? super E> e = (Comparable<? super E>)element;
do {
parent = t;
cmp = e.compareTo(t.element);
if (cmp < 0) {
t= t.left;
} else if (cmp > 0) {
t= t.right;
} else {
return false;
}
} while (t != null);
Node<E> child = new Node<E>(element, parent);
if (cmp < 0) {
parent.left = child;
} else {
parent.right = child;
}
//節(jié)點(diǎn)已經(jīng)插入逗旁，
// 檢查平衡，回溯查找
while (parent != null) {
cmp = e.compareTo(parent.element);
//元素在左邊插入
if (cmp < 0) {
parent.balance++;
} else{ //元素在右邊插入
parent.balance --;
}
if (parent.balance == 0) {
break;
}
if (Math.abs(parent.balance) == 2) {
//出現(xiàn)平衡問題
fixAfterInsertion(parent);
break;
} else {
parent = parent.parent;
}
}
size++;
return true;
}
}
private void fixAfterInsertion(AVL<E>.Node<E> parent) {
if (parent.balance == 2) {
leftBalance(parent);
}
if (parent.balance == -2) {
rightBalance(parent);
}
}
private void rightBalance(AVL<E>.Node<E> t) {
Node<E> tr = t.right;
switch (tr.balance) {
case RH:
left_rotate(t);
t.balance = EH;
tr.balance = EH;
break;
case LH:
Node<E> trl = tr.left;
switch (trl.balance) {
case LH:
t.balance = EH;
tr.balance = RH;
break;
case RH:
t.balance = LH;
tr.balance = EH;
break;
case EH:
t.balance = EH;
tr.balance = EH;
break;
}
trl.balance = EH;
right_rotate(t.right);
left_rotate(t);
break;
default:
break;
}
}
private void left_rotate(AVL<E>.Node<E> t) {
if (t != null) {
Node tr = t.right;
t.right = tr.left;
if (tr.left != null) {
tr.left.parent = t;
}
tr.parent = t.parent;
if (t.parent == null) {
root = tr;
} else {
if (t.parent.left == t) {
t.parent.left = tr;
} else if (t.parent.right == t) {
t.parent.right = tr;
}
}
tr.left = t;
t.parent = tr;
}
}
private void right_rotate(AVL<E>.Node<E> t) {
if (t != null) {
Node<E> tl = t.left;
t.left =tl.right;
if (tl.right != null) {
tl.right.parent = t;
}
tl.parent = t.parent;
if (t.parent == null) {
root = tl;
} else {
if (t.parent.left == t) {
t.parent.left = tl;
} else if (t.parent.right == t) {
t.parent.right = tl;
}
}
tl.right = t;
t.parent = tl;
}
}
public Node<E> searchNode(E element) {
if (root == null) {
return null;
} else {
Node<E> cur = root;
while(cur != null) {
if (element.compareTo(cur.element) > 0) {
cur = cur.right;
} else if (element.compareTo(cur.element) < 0) {
cur = cur.left;
} else {
return cur;
}
}
}
return null;
}
private void leftBalance(AVL<E>.Node<E> t) {
Node<E> tl = t.left;
switch (tl.balance) {
case LH: // t 的左子樹的左邊有問題舆瘪，直接右旋
right_rotate(t);
tl.balance = EH;
t.balance = EH;
break;
case RH:
Node<E> tlr = tl.right;
switch (tlr.balance) {
case RH:
t.balance = EH;
tlr.balance = EH;
tl.balance = LH;
break;
case LH:
t.balance = RH;
tl.balance =EH;
tlr.balance = EH;
break;
case EH:
t.balance = EH;
tl.balance = EH;
tlr.balance =EH;
break;
//統(tǒng)一旋轉(zhuǎn)
default:
break;
}
left_rotate(t.left);
right_rotate(t);
break;
default:
break;
}
}
class NodeBF {
int level;
Node<E> node;
public NodeBF(Node node, int lev) {
this.node = node;
level = lev;
}
}
class Node<E extends Comparable<E>>{
E element; // data
int balance = 0; // balance value
Node<E> left;
Node<E> right;
Node<E> parent;
public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return element + "BF: " + balance;
}
public E getElement() {
return element;
}
public void setElement(E element) {
this.element = element;
}
public int getBalance() {
return balance;
}
public void setBalance(int balance) {
this.balance = balance;
}
public Node<E> getLeft() {
return left;
}
public void setLeft(Node<E> left) {
this.left = left;
}
public Node<E> getRight() {
return right;
}
public void setRight(Node<E> right) {
this.right = right;
}
public Node<E> getParent() {
return parent;
}
public void setParent(Node<E> parent) {
this.parent = parent;
}
}
public Node<E> getRoot() {
return root;
}
public void levelDisplay(Node root) {
LinkedList<NodeBF> list = new LinkedList<>();
NodeBF nodeBF = new NodeBF(root, 0);
list.offer(nodeBF);
while (!list.isEmpty()) {
NodeBF node = list.pop();
System.out.println(node.node.element + " level: " + node.level);
if (node.node.left != null) {
NodeBF nodel = new NodeBF(node.node.left, node.level + 1);
list.offer(nodel);
}
if (node.node.right != null) {
NodeBF noder = new NodeBF(node.node.right, node.level + 1);
list.offer(noder);
}
}
}
public static void main(String[] args) {
// Integer[] nums = {5, 8, 2, 0, 1, -2, -9, 100};
Integer[] nums = {5, 8, 2, 0, 1, -2};
AVL<Integer> vAvlTree = new AVL();
for (int i = 0; i < nums.length; i++) {
vAvlTree.inserElement(nums[i]);
}
// vAvlTree.midOrderDisplay(vAvlTree.root);
vAvlTree.levelDisplay(vAvlTree.root);
System.out.println(vAvlTree.root.element);
}
}
