AVL的基本概念和特征都是了解的吗铐，但真正動(dòng)手coding的時(shí)候，發(fā)現(xiàn)很多細(xì)節(jié)問(wèn)題是之前了解不深或沒(méi)注意到的杏节，總結(jié)一下吧唬渗。
0. 說(shuō)明
這過(guò)程中找了一些文章和博客典阵，其中對(duì)我?guī)椭畲蟮囊黄恼戮褪恰緟⒖嘉臋n】中列的“平衡二叉樹(shù)的實(shí)現(xiàn)原理”。
因?yàn)榛驹砟魇牛瑘D例在這篇文章中都有很好的解釋壮啊，我指寫我的一些理解和誤區(qū)，詳細(xì)內(nèi)容我就不做搬運(yùn)工了撑蒜，感興趣的可以移步：【平衡二叉樹(shù)的實(shí)現(xiàn)原理】
1. 了解概念
了解以下幾個(gè)概念：樹(shù)歹啼，二叉樹(shù)，排序二叉樹(shù)座菠，平衡二叉樹(shù)狸眼。
平衡二叉樹(shù)旨在解決排序二叉樹(shù)查詢復(fù)雜度不可控的問(wèn)題，即排序二叉樹(shù)可能退化為鏈表的問(wèn)題浴滴，因此平衡二叉樹(shù)也叫自平衡二叉查找樹(shù)拓萌。
平衡二叉樹(shù)的遞歸定義：平衡二叉樹(shù)是一棵二叉樹(shù)，其可以為空升略，或滿足如下2個(gè)性質(zhì)：①左右子樹(shù)深度之差的絕對(duì)值不大于1司志。②左右子樹(shù)都是平衡二叉樹(shù)。
平衡因子的概念：結(jié)點(diǎn)的平衡因子 = 結(jié)點(diǎn)的左子樹(shù)深度 — 結(jié)點(diǎn)的右子樹(shù)深度降宅。
最低不平衡結(jié)點(diǎn)的概念：用A表示最低不平衡結(jié)點(diǎn)，則A的祖先結(jié)點(diǎn)可能有不平衡的囚霸，但其所有后代結(jié)點(diǎn)都是平衡的腰根。 【1】
2. 自平衡實(shí)現(xiàn)
我們知道只在兩種情況下需要對(duì)排序二叉樹(shù)進(jìn)行平衡化:
- 插入節(jié)點(diǎn)；
- 刪除節(jié)點(diǎn)拓型；
但本質(zhì)上额嘿，都是在樹(shù)發(fā)生變化時(shí)，找到最低不平衡節(jié)點(diǎn)劣挫，然后對(duì)以最低不平衡節(jié)點(diǎn)為根的子樹(shù)進(jìn)行適當(dāng)?shù)牟僮鞑嵫蛊淦胶猓瑥亩鴮?shí)現(xiàn)整棵樹(shù)的平衡压固。
這里有個(gè)問(wèn)題球拦，如果以最低不平衡節(jié)點(diǎn)為根的子樹(shù)轉(zhuǎn)為平衡樹(shù)，那么整棵樹(shù)是否就是平衡的帐我？
這其實(shí)很好想明白的坎炼，因?yàn)槲覀兊牟僮髑疤崾牵?strong>節(jié)點(diǎn)插入/刪除，即每次只有一個(gè)節(jié)點(diǎn)發(fā)生改變（很重要的前提）拦键，那么平衡因子最大只能是2或者-2谣光。當(dāng)最低不平衡節(jié)點(diǎn)再平衡時(shí)，其平衡因子會(huì)變?yōu)?或者-1芬为，那對(duì)于最低不平衡節(jié)點(diǎn)的父親節(jié)點(diǎn)萄金，也可以如此推演蟀悦。
3. 部分代碼
- 節(jié)點(diǎn)定義
public class BNode{
public int value;
public BNode left;
public BNode right;
public BNode parent;
// 省略構(gòu)造函數(shù)
// 屬性設(shè)置為public只是為了方便
}
- 插入節(jié)點(diǎn)
public void insert(int value){
BNode tNode = root;
if(tNode == null){
root = new BNode(value);
size = 1;
return;
}
BNode parent = null;
while(tNode!= null){
parent = tNode;
if(value > tNode.value){
tNode = tNode.right;
}else if(value < tNode.value){
tNode = tNode.left;
}else{
return;
}
}
// 通過(guò)簡(jiǎn)單的判斷，可以過(guò)濾掉一部分不必要的平衡因子計(jì)算
// 判斷依據(jù)就是氧敢，插入節(jié)點(diǎn)不影響樹(shù)高
boolean needReblance = true;
BNode newNode = new BNode(value,parent);
//
if(value > parent.value){
parent.right = newNode;
if(parent.left != null){
needReblance = false;
}
}else{
parent.left = newNode;
if(parent.right != null){
needReblance = false;
}
}
// 對(duì)二叉樹(shù)進(jìn)行平衡操作
if(needReblance){
reblance(newNode);
}
size++;
}
- 平衡判斷
private void reblance(BNode node){
BNode t = node;
while(t != null){
int factor = balanceFactor(t); // 計(jì)算平衡因子
if(Math.abs(factor) > 1){
// 細(xì)節(jié)：旋轉(zhuǎn)操作會(huì)改變樹(shù)的根日戈，因此需要重新設(shè)置樹(shù)的根節(jié)點(diǎn)
boolean resetRoot = t.value == root.value;
if(node.value < t.value && node.value < t.left.value){
// LL
roateRight(t);
}else if(node.value > t.value && node.value > t.right.value){
// RR
roateLeft(t);
}else if(node.value < t.value && node.value > t.left.value){
// LR
roateLeft(t.left);
roateRight(t);
}else{
// RL
roateRight(t.right);
roateLeft(t);
}
// 重新設(shè)置root節(jié)點(diǎn)
if(resetRoot) {
while (t.parent != null) {
t = t.parent;
}
root = t;
}
break;
}
t = t.parent;
}
}
- 中序遍歷
// 中序遍歷輸出的即為有序元素
public List<BNode> midOrder(){
BNode node = root;
if(node == null){
return new ArrayList<>(0);
}
List<BNode> list = new ArrayList<>(size);
Stack<BNode> stack = new Stack<>();
stack.push(node);
while(stack.size()>0){
while(node != null){
if(node.left != null){
stack.push(node.left);
}
node = node.left;
}
// 寫的時(shí)候?qū)懥藘煞N，覺(jué)得下面的更好福稳，就把這種寫法注掉了涎拉。
// a: while (stack.size() > 0) {
// BNode t = stack.pop();
// list.add(t);
// if(t.right != null){
// node = t.right;
// stack.push(t.right);
// break a;
// }
// }
////
if(stack.size()!=0){
BNode t = stack.pop();
list.add(t);
if(t.right != null){
node = t.right;
stack.push(t.right);
}
}
}
return list ;
}
- 簡(jiǎn)單測(cè)試
public void test() {
BalanceTree bt = new BalanceTree();
// 這組數(shù)據(jù)，覆蓋了LL,RR,RL,LR等四種case
int[] arr = new int[]{4, 3, 2, 0, 1, 5, 6, 7, 8, 11, 10, 9};
for (int i : arr) {
bt.insert(i);
}
System.out.println("finish init ..............");
List<BalanceTree.BNode> list = bt.midOrder();
for(BalanceTree.BNode n: list){
System.out.println(n.value);
}
}
4. 總結(jié)
以前常犯眼高手低的病的圆，覺(jué)得原理清楚了就算掌握了鼓拧。其實(shí)coding是一項(xiàng)工程性很強(qiáng)的事情，會(huì)有很多細(xì)節(jié)需要處理和考慮越妈。
最近嘗試把數(shù)據(jù)庫(kù)/數(shù)倉(cāng)相關(guān)的數(shù)據(jù)結(jié)構(gòu)知識(shí)補(bǔ)上季俩，后續(xù)會(huì)繼續(xù)寫B(tài)樹(shù)，紅黑樹(shù)梅掠，LSM等酌住。
【參考】
