關於AVL樹的介紹,其實與我共筆的作者已經介紹過基本的四種型態,本文將著重於各種旋轉的實作,關於基本介紹請參考:AVL高度平衡二元搜尋樹介紹。
基本上,AVL樹的加入先以BST(二元搜尋樹)的方式加入,關於BST的介紹與實作請參考:樹-二元搜尋樹之介紹與範例。加入之後,重新計算BF(平衡因子),當大於2時,則需要進行旋轉,共有四種旋轉方式:LL、RR、LR、RL。在介紹各種型態的旋轉方式之前,我們先來討論如何計算BF。
BF的計算方式是左子樹的高度 - 右子樹的高度,即是該節點的BF(備註:高度即是深度)。而高度的計算我是利用遞迴(堆疊)計算,由樹根開始堆疊至底部,再由底部向上計算高度。
public int height(node node) {
if (node != null) {
//當傳入的節點之左右子樹為空時
if (node.rlink == null && node.llink == null) {
return 1;
} else {
return 1 + (height(node.llink) > height(node.rlink) ? height(node.llink) : height(node.rlink));
}
//分別堆疊計算左右子樹高,回傳較大者
}
return 0;
}
BF的計算則是先計算左右子點高度,再相減即可。
public void bf(node node) {
if (node != null) {
//利用後序走訪計算BF
bf(node.llink);
bf(node.rlink);
System.out.printf("NODE LLINK HEI:%d NODE RLINK HEI:%d ", height(node.llink), height(node.rlink));
node.bf = height(node.llink) - height(node.rlink);
System.out.printf("BF %d\n", node.bf);
}
}
實作上如何確認哪個節點要調整,如下:
public node find_pivot() {
current = root;
pivot = null;
while (current != null) {
if (current.bf > 1 || current.bf < -1) {//當節點的BF絕對值大於1時,紀錄該點
pivot = current;
if (pivot != root) {
pivot_prev = prev;
}
//如果不是ROOT,需要追蹤前一個節點,為何需要追蹤請隨便舉例一種簡單的旋轉方式即可
System.out.printf("PIVOT FIND:%d\n", current.data);
}
if (current.bf > 0) {//BF=左-右,大於代表左邊要調整,小於代表左邊要調整
prev = current;
current = current.llink;
} else if (current.bf < 0) {
prev = current;
current = current.rlink;
} else {//當上面情況都不是,代表平衡,讓current隨意向下直到為null結束迴圈
current = current.llink;
}
}
return pivot;
}
尋找的方式是從樹根開始找,若BF的值為正數,代表左子點的BF較大,就向左找。若為負數,則向右找。
當該節點的BF絕對值大於1時,則紀錄該節點,並記錄該節點的父節點。如果pivot為null,代表平衡。
若有一加入的新節點為N,若一距離N最近且平衡因子為+-2的父節點P存在,則四種調整方式的適用時機如下 :
1. LL:當加入的節點N在節點P的左邊的左邊
2.RR:當加入的節點N在節點P的右邊的右邊
3.LR:當加入的節點N在節點P的左邊的右邊
4.RL:當加入的節點N在節點P的右邊的左邊
調整只需找鄰近的2節點即可。
LL代表左子樹過重,以下圖為例:
明顯看到在加入20之後,節點50的BF為2,且節點20加入在左方,符合LL型態,其旋轉方式如下:
pivot是與加入節點最近且BF為+-2的節點,pivot_next是要調整的鄰近節點,temp則是要放到右邊的節點
經由下列步驟旋轉
pivot_next.rlink=pivot
pivot.llink=temp
就能調整完成,如下圖所示:
public void LL() {
node pivot_next, temp;
pivot_next = pivot.llink;
temp = pivot_next.rlink;
pivot_next.rlink = pivot;
pivot.llink = temp;
if (pivot == root) {
root = pivot_next;
} else {//判斷pivot是父節點的左還是右子點
if (pivot_prev.llink == pivot) {
pivot_prev.llink = pivot_next;
} else {
pivot_prev.rlink = pivot_next;
}
}
}
RR剛好對稱於LL,右子樹過重
加入80之後,50節點的BF為-2,右子樹明顯過重,經過旋轉過後:
關於RR的演算法,就是將LL的演算法左右顛倒即可,不再贅述,請參考程式碼
public void RR() {
node temp, pivot_next;
pivot_next = pivot.rlink;
temp = pivot_next.llink;
pivot_next.llink = pivot;
pivot.rlink = temp;
if (pivot == root) {
root = pivot;
} else {
if (pivot_prev.llink == pivot) {
pivot_prev.llink = pivot_next;
} else {
pivot_prev.rlink = pivot_next;
}
}
}
如下圖:
加入42之後,節點50的BF為2,不符合AVL樹定義,調整方式是將45往上提,再將小於45的節點40放在45的左邊,50放在右邊。演算法如下:
pivot.llink=temp.rlink ( 將TEMP的右節點放到右邊)
pivot_next.rlink=temp.llink (將TEMP的左節點放到左邊)
temp.llink=pivot_next
temp.rlink=pivot
public void LR() {
node temp, pivot_next;
pivot_next = pivot.llink;
temp = pivot_next.rlink;
pivot.llink = temp.rlink;//將TEMP的右節點放到右邊(就是PIVOT的左鏈結)
pivot_next.rlink = temp.llink;//將TEMP的左節點放到左邊(就是PIVOTNEXY的右連結)
temp.rlink = pivot; //PIVOT_NEXT一定小於PIVOT
temp.llink = pivot_next;
if (pivot == root) {
root = temp;
} else {
if (pivot_prev.llink == pivot) {
pivot_prev.llink = temp;
} else {
pivot_prev.rlink = temp;
}
}
}
RL型與LR型對稱,演算法方面直接左右顛倒即可,直接舉例:
明顯看出50節點的BF為-2,故需旋轉,方法是將55向上提,左邊放較小的50,右邊放較大的60
旋轉後
public void RL() {
node temp, pivot_next;
pivot_next = pivot.rlink;
temp = pivot_next.llink;
pivot.rlink = temp.llink;
pivot_next.llink = temp.rlink;
temp.rlink = pivot_next;//PIVOT_NEXT一定大於PIVOT
temp.llink = pivot;
if (pivot == root) {
root = temp;
} else {
if (pivot_prev.llink == pivot) {
pivot_prev.llink = temp;
} else {
pivot_prev.rlink = temp;
}
}
}
介紹完上述四種型態後,實作上如何判別型態呢,如下:
public int find_type() {
int op = 0;
current = pivot;
for (int i = 0; i < 2; i++) {
if (current.bf > 0) { //左子樹較高
current = current.llink;
if (op == 0) {
op += 10;
} else {
op++;
}
} else if (current.bf < 0) { //右子樹較高
current = current.rlink;
if (op == 0) {
op += 20;
} else {
op += 2;
}
//11:LL,22:RR,12:LR、22:RR
}
}
return op;
}
當發現pivot時,代表需要調整。我們從要調整的節點向下尋找鄰近的兩個節點就好,就能判斷型別。
先判斷左子點還是右子點較高,哪邊高就向哪邊尋找,當取完兩個節點後,就可以得知其型別。回傳部分,十位數代表第一個是左還右,個位數則紀錄第二個是左還右。
AVL樹的刪除與BST相同,不再贅述,請參考該篇文章。依照BST的規則刪除完成後,只要重新計算BF,再判斷是否符合AVL樹的規則並調整即可。請直接參考程式碼
public void del() {
int del = input.nextInt();
node rel=null, rer = null, parent = null;
node delnode = search(del);
if (delnode == null) {
System.out.println("Data not find.");
} else {
if (delnode.rlink == null && delnode.llink == null)//刪除樹葉節點
{
if (delnode == root) {
root = null;
} else {
current = root;
while (current != null && current.data != delnode.data) {
if (current.rlink.data == delnode.data) {
parent = current;
}
else if (current.llink.data == delnode.data) {
parent = current;
}
if (current.data > delnode.data) {
current = current.llink;
}
else if (current.data < delnode.data) {
current = current.rlink;
}
}
if (parent.llink.data == delnode.data) {
parent.llink = null;
} else {
parent.rlink = null;
}
delnode = null;
System.out.println("DEL");
}
} else {
//找尋替代節點-右最小
current = delnode.rlink;
while (current != null && current.llink != null) {
current = current.llink;
}
rer = current;
//尋找右節點
if (rer == null) {
current = delnode.llink;
while (current != null && current.rlink != null) {
current = current.rlink;
}
rel = current;
}
//尋找RE父節點
current = root;
if (rer != null) {
System.out.println(rer.data);
int i=0;
while (current != null && current.data != rer.data) {
i++;
if (current.rlink.data == rer.data) {
System.out.print("parent Find");
parent = current;
}else if (current.llink.data == rer.data) {
parent = current;
}
if (current.data > rer.data) {
System.out.printf("L %d \n",i);
current = current.llink;
}else if (current.data < rer.data) {
System.out.printf("R %d\n",i);
current = current.rlink;
}
}
if(rer.data>parent.data)
parent.rlink = rer.rlink;
else
parent.llink=rer.rlink;
delnode.data = rer.data;
rer = null;
} else if (rel != null) {
while (current != null && current.data != rel.data) {
if (current.llink.data == rel.data) {
parent = current;
}
else if (current.rlink.data == rel.data) {
parent = current;
}
if (current.data > rel.data) {
current = current.llink;
}
else if (current.data < rel.data) {
current = current.rlink;
}
}
if(parent.data>rel.data)
parent.llink = rel.llink;
else
parent.rlink=rel.llink;
delnode.data = rel.data;
rel = null;
}
System.out.println("DEL");
}
bf(root);
int op = 0;
pivot = find_pivot();
if (pivot != null) {
op = find_type();
switch (op) {
case 11: //LL
LL();
break;
case 12://LR
LR();
break;
case 21://RL
RL();
break;
case 22://RR
RR();
break;
}
}
}
}
AVL樹的走訪與搜尋都與BST相同,這裡就不再贅述。
import java.util.Scanner;
class node {
int data;
int bf;
node llink, rlink;
}
public class avl {
node ptr, root, current, prev, pivot, pivot_prev;
Scanner input = new Scanner(System.in);
public void insert() {
System.out.println("Input data:");
int data = input.nextInt();
if (search(data) == null) {
node ptr = new node();
ptr.data = data;
if (root == null) {
root = ptr;
root.bf = 0;
System.out.println("Data Insert!!!(ROOT)");
} else if (root != null) {
current = root;
while (current != null) {
prev = current;
if (ptr.data > current.data) {
current = current.rlink;
} else if (ptr.data < current.data) {
current = current.llink;
}
}
if (ptr.data > prev.data) {
prev.rlink = ptr;
} else if (ptr.data < prev.data) {
prev.llink = ptr;
}
System.out.println("Data Insert!!!");
bf(root);//每次插入都重新計算BF
pivot = find_pivot();//尋找不平衡
System.out.printf("RETURN PIVOT %d\n", pivot != null ? pivot.data : 0);
if (pivot != null) {
int op = find_type();
switch (op) {
case 11: //LL
LL();
break;
case 12://LR
LR();
break;
case 21://RL
RL();
break;
case 22://RR
RR();
break;
}
}
}
} else if (search(data) != null) {
System.out.println("Data 重複");
}
}
public void del() {
int del = input.nextInt();
node rel=null, rer = null, parent = null;
node delnode = search(del);
if (delnode == null) {
System.out.println("Data not find.");
} else {
if (delnode.rlink == null && delnode.llink == null)//刪除樹葉節點
{
if (delnode == root) {
root = null;
} else {
current = root;
while (current != null && current.data != delnode.data) {
if (current.rlink.data == delnode.data) {
parent = current;
}
else if (current.llink.data == delnode.data) {
parent = current;
}
if (current.data > delnode.data) {
current = current.llink;
}
else if (current.data < delnode.data) {
current = current.rlink;
}
}
if (parent.llink.data == delnode.data) {
parent.llink = null;
} else {
parent.rlink = null;
}
delnode = null;
System.out.println("DEL");
}
} else {
//找尋替代節點-右最小
current = delnode.rlink;
while (current != null && current.llink != null) {
current = current.llink;
}
rer = current;
//尋找右節點
if (rer == null) {
current = delnode.llink;
while (current != null && current.rlink != null) {
current = current.rlink;
}
rel = current;
}
//尋找RE父節點
current = root;
if (rer != null) {
System.out.println(rer.data);
int i=0;
while (current != null && current.data != rer.data) {
i++;
if (current.rlink.data == rer.data) {
System.out.print("parent Find");
parent = current;
}else if (current.llink.data == rer.data) {
parent = current;
}
if (current.data > rer.data) {
System.out.printf("L %d \n",i);
current = current.llink;
}else if (current.data < rer.data) {
System.out.printf("R %d\n",i);
current = current.rlink;
}
}
if(rer.data>parent.data)
parent.rlink = rer.rlink;
else
parent.llink=rer.rlink;
delnode.data = rer.data;
rer = null;
} else if (rel != null) {
while (current != null && current.data != rel.data) {
if (current.llink.data == rel.data) {
parent = current;
}
else if (current.rlink.data == rel.data) {
parent = current;
}
if (current.data > rel.data) {
current = current.llink;
}
else if (current.data < rel.data) {
current = current.rlink;
}
}
if(parent.data>rel.data)
parent.llink = rel.llink;
else
parent.rlink=rel.llink;
delnode.data = rel.data;
rel = null;
}
System.out.println("DEL");
}
bf(root);
int op = 0;
pivot = find_pivot();
if (pivot != null) {
op = find_type();
switch (op) {
case 11: //LL
LL();
break;
case 12://LR
LR();
break;
case 21://RL
RL();
break;
case 22://RR
RR();
break;
}
}
}
}
public void LL() {
node pivot_next, temp;
pivot_next = pivot.llink;
temp = pivot_next.rlink;
pivot_next.rlink = pivot;
pivot.llink = temp;
if (pivot == root) {
root = pivot_next;
} else {//判斷pivot是父節點的左還是右子點
if (pivot_prev.llink == pivot) {
pivot_prev.llink = pivot_next;
} else {
pivot_prev.rlink = pivot_next;
}
}
}
public void RR() {
node temp, pivot_next;
pivot_next = pivot.rlink;
temp = pivot_next.llink;
pivot_next.llink = pivot;
pivot.rlink = temp;
if (pivot == root) {
root = pivot;
} else {
if (pivot_prev.llink == pivot) {
pivot_prev.llink = pivot_next;
} else {
pivot_prev.rlink = pivot_next;
}
}
}
public void LR() {
node temp, pivot_next;
pivot_next = pivot.llink;
temp = pivot_next.rlink;
pivot.llink = temp.rlink;//將TEMP的右節點放到右邊(就是PIVOT的左鏈結)
pivot_next.rlink = temp.llink;//將TEMP的左節點放到左邊(就是PIVOTNEXY的右連結)
temp.rlink = pivot; //PIVOT_NEXT一定小於PIVOT
temp.llink = pivot_next;
if (pivot == root) {
root = temp;
} else {
if (pivot_prev.llink == pivot) {
pivot_prev.llink = temp;
} else {
pivot_prev.rlink = temp;
}
}
}
public void RL() {
node temp, pivot_next;
pivot_next = pivot.rlink;
temp = pivot_next.llink;
pivot.rlink = temp.llink;
pivot_next.llink = temp.rlink;
temp.rlink = pivot_next;//PIVOT_NEXT一定大於PIVOT
temp.llink = pivot;
if (pivot == root) {
root = temp;
} else {
if (pivot_prev.llink == pivot) {
pivot_prev.llink = temp;
} else {
pivot_prev.rlink = temp;
}
}
}
public int find_type() {
int op = 0;
current = pivot;
for (int i = 0; i < 2; i++) {
if (current.bf > 0) { //左子樹較高
current = current.llink;
if (op == 0) {
op += 10;
} else {
op++;
}
} else if (current.bf < 0) { //右子樹較高
current = current.rlink;
if (op == 0) {
op += 20;
} else {
op += 2;
}
//11:LL,22:RR,12:LR、22:RR
}
}
return op;
}
public node find_pivot() {
current = root;
pivot = null;
while (current != null) {
if (current.bf > 1 || current.bf < -1) {//當節點的BF絕對值大於1時,紀錄該點
pivot = current;
if (pivot != root) {
pivot_prev = prev;
}
//如果不是ROOT,需要追蹤前一個節點,為何需要追蹤請隨便舉例一種簡單的旋轉方式即可
System.out.printf("PIVOT FIND:%d\n", current.data);
}
if (current.bf > 0) {//BF=左-右,大於代表左邊要調整,小於代表左邊要調整
prev = current;
current = current.llink;
} else if (current.bf < 0) {
prev = current;
current = current.rlink;
} else {//當上面情況都不是,代表平衡,讓current隨意向下直到為null結束迴圈
current = current.llink;
}
}
return pivot;
}
public node search(int set) {//搜尋方式與BST相同
current = root;
while (current != null) {
prev = current;
if (set > current.data) {
current = current.rlink;
} else if (set < current.data) {
current = current.llink;
} else if (set == current.data) {
break;
}
}
return current;
}
public void bf(node node) {
if (node != null) {
//利用後序走訪計算BF
bf(node.llink);
bf(node.rlink);
System.out.printf("NODE LLINK HEI:%d NODE RLINK HEI:%d ", height(node.llink), height(node.rlink));
node.bf = height(node.llink) - height(node.rlink);
System.out.printf("BF %d\n", node.bf);
}
}
public int height(node node) {
if (node != null) {
//當傳入的節點之左右子樹為空時
if (node.rlink == null && node.llink == null) {
return 1;
} else {
return 1 + (height(node.llink) > height(node.rlink) ? height(node.llink) : height(node.rlink));
}
//分別堆疊計算左右子樹高,回傳較大者
}
return 0;
}
public void list() {
if (root != null) {
inorder(root);
} else {
System.out.println("Tree is null!");
}
}
public void inorder(node node) {
if (node != null) {
inorder(node.llink);
System.out.printf("%d ", node.data);
inorder(node.rlink);
}
}
public static void main(String[] args) {
avl obj = new avl();
Scanner input = new Scanner(System.in);
System.out.println("<1>插入 <2>刪除 <3>印出");
while (true) {
int doing = input.nextInt();
switch (doing) {
case 1:
obj.insert();
break;
case 2:
obj.del();
break;
case 3:
obj.list();
break;
}
}
}
}
關於作者
粉絲專頁
文章分類