Java數(shù)據(jù)結(jié)構(gòu)中關(guān)于AVL樹的實(shí)現(xiàn)方法詳解
AVL樹的說明
AVL樹是一種自平衡二叉搜索樹，它的名稱來源于它的發(fā)明者 Adelson-Velsky 和 Landis 。在AVL樹中，任何節(jié)點(diǎn)的兩個(gè)子樹的高度最多相差 1，這使得AVL樹能夠保持相對(duì)平衡，從而保證了樹的查找、插入和刪除操作的時(shí)間復(fù)雜度都是 O(log n)。
AVL樹的平衡性是通過對(duì)節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)操作來實(shí)現(xiàn)的，包括左旋、右旋、左右旋和右左旋。當(dāng)插入或刪除節(jié)點(diǎn)后破壞了AVL樹的平衡性時(shí)，就會(huì)進(jìn)行相應(yīng)的旋轉(zhuǎn)操作來保持樹的平衡。
也就是說， AVL 樹是一種特殊的自平衡二叉搜索樹。
AVL樹的成員變量及其構(gòu)造方法
（1）構(gòu)造 AVLNode 內(nèi)部類變量 ：
- int key 關(guān)鍵字：通過關(guān)鍵字來比較每個(gè)節(jié)點(diǎn)的大小。
- Object value 值：通過該變量存放值。
- AVLNode left：引用左孩子節(jié)點(diǎn)。
- AVLNode right：引用右孩子節(jié)點(diǎn)。
- int height 高度：表示當(dāng)前節(jié)點(diǎn)的高度，默認(rèn)初始化為 1 。
（2）AVLNode 內(nèi)部類構(gòu)造方法：
- 重載兩個(gè)內(nèi)部類的構(gòu)造方法分別為：參數(shù)為 key，value 的構(gòu)造方法、參數(shù)為 key，value，left，right 的構(gòu)造方法。
（3）構(gòu)造 AVLTree 外部類 ：
- AVLNode root：表示該樹的頭節(jié)點(diǎn)。
代碼如下：
public class AVLTree {
AVLNode root = null;
static class AVLNode {
int key;
Object value;
AVLNode left;
AVLNode right;
int height = 1;
public AVLNode(int key, Object value) {
this.key = key;
this.value = value;
}
public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
}實(shí)現(xiàn)AVL樹的核心方法
AVL 樹的最核心的方法就是插入、更新、刪除操作，因?yàn)檫@些操作都有可能造成二叉搜索樹失去平衡。為了解決自平衡的特點(diǎn)，需要每一個(gè)插入或者更新、刪除操作之后，需要檢查是否失去平衡，若失去平衡需要通過左旋、右旋、左右旋、右左旋來重新達(dá)到平衡狀態(tài)；若沒有失去平衡，無需任何操作。
獲取當(dāng)前節(jié)點(diǎn)的高度
height(AVLNode node)
不能直接通過 node.height 得到當(dāng)前節(jié)點(diǎn)的高度，是因?yàn)槟J(rèn)高度為 1，若出現(xiàn)該節(jié)點(diǎn)為 null 時(shí)，就會(huì)出現(xiàn)矛盾，因此需要先判斷該節(jié)點(diǎn)是否為 null 節(jié)點(diǎn)，若為空節(jié)點(diǎn)，返回 0 ；若不為 空節(jié)點(diǎn)，則返回當(dāng)前節(jié)點(diǎn) node.height 即可。
代碼如下：
//獲取當(dāng)前節(jié)點(diǎn)的高度
private int height (AVLNode node) {
return node == null ? 0 : node.height;
}更新當(dāng)前節(jié)點(diǎn)的高度
updateHeight(AVLNode node)
由于通過刪除、插入、旋轉(zhuǎn)都有可能導(dǎo)致當(dāng)前節(jié)點(diǎn)的高度發(fā)生改變，所以需要更新高度。實(shí)現(xiàn)該方法也很簡(jiǎn)單，判斷當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)的高度，取最大的高度 + 1 就是為當(dāng)前節(jié)點(diǎn)的高度。
代碼如下：
//更新當(dāng)前的高度
private void updateHeight (AVLNode node) {
node.height = Integer.max(height(node.left),height(node.right)) + 1;
}平衡因子
bf(AVLNode node)
判斷當(dāng)前節(jié)點(diǎn)是否失去平衡，當(dāng)該節(jié)點(diǎn)的左子樹的高度 - 右子樹的高度 > 1或者 < -1 即失去平衡了。若差值為 1、0、-1，表示沒有失去平衡。
代碼如下：
//平衡因子
private int bf (AVLNode node) {
return height(node.left) - height(node.right);
}對(duì)失衡節(jié)點(diǎn)旋轉(zhuǎn)
rotate(AVLNode node)
有四種情況：左旋、右旋、左右旋、右左旋
左旋：需要先拿到失衡節(jié)點(diǎn) node 的右孩子節(jié)點(diǎn) node.right ,將 r = node.right 賦值給 r 。先將 r.left 賦值給 node.right ，即 node.right = r.left 進(jìn)行 "換爹" 操作，然后再 "上位" r.left = node 。最后，因?yàn)樾D(zhuǎn)會(huì)導(dǎo)致當(dāng)前 node 的節(jié)點(diǎn)與上位后的節(jié)點(diǎn) r 的高度都有可能會(huì)改變，所以需要及時(shí)更新高度，通過 updateHeight(node)，updateHeight(r)，需要注意的是，更新的順序不能改變。
右旋：跟左旋的原理是一樣的，需要先拿到失衡節(jié)點(diǎn) node 的左孩子節(jié)點(diǎn) node.left ,將 l= node.left賦值給 l。先將 l.right賦值給 node.left，即 node.left= l.right進(jìn)行 "換爹" 操作，然后再 "上位" l.right= node 。最后，因?yàn)樾D(zhuǎn)會(huì)導(dǎo)致當(dāng)前 node 的節(jié)點(diǎn)與上位后的節(jié)點(diǎn) r 的高度都有可能會(huì)改變，所以需要及時(shí)更新高度，通過 updateHeight(node)，updateHeight(l)，需要注意的是，更新的順序不能改變。
左右旋：通過結(jié)合左旋、右旋實(shí)現(xiàn)左右旋。先拿到當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn) l = node.left，對(duì)于 l 節(jié)點(diǎn)需要用到左旋的方法進(jìn)行旋轉(zhuǎn) leftRotate(l)，旋轉(zhuǎn)后需要重新賦值 node.left = leftRotate(l) 。接著對(duì)于 node 節(jié)點(diǎn)需用用到右旋方法進(jìn)行旋轉(zhuǎn) rightRotate(node) 。最后返回rightRotate(node) 節(jié)點(diǎn)即可。
右左旋：通過結(jié)合右旋、左旋實(shí)現(xiàn)右左旋。先拿到當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn) r = node.right，對(duì)于 r 節(jié)點(diǎn)需要用到右旋的方法進(jìn)行旋轉(zhuǎn) rightRotate(r) ，旋轉(zhuǎn)后需要重新賦值 node.right = rightRotate(r) 。接著對(duì)于 node 節(jié)點(diǎn)需要用到左旋方法 leftRotate(node) 。最后返回 leftRotate(node) 節(jié)點(diǎn)即可。
代碼如下：
//左旋
private AVLNode leftRotate (AVLNode node) {
AVLNode r = node.right;
node.right = r.left;
r.left = node;
updateHeight(node);
updateHeight(r);
return r;
}
//右旋
private AVLNode rightRotate (AVLNode node) {
AVLNode l = node.left;
node.left = l.right;
l.right = node;
updateHeight(node);
updateHeight(l);
return l;
}
//左右旋
private AVLNode leftRightRotate (AVLNode node) {
AVLNode l = node.left;
node.left = leftRotate(l);
return rightRotate(node);
}
//右左旋
private AVLNode rightLeftRotate (AVLNode node) {
AVLNode r = node.right;
node.right = rightRotate(r);
return leftRotate(node);
}檢查節(jié)點(diǎn)是否平衡與重新平衡
balance(AVLNode node)
介紹四種失衡狀態(tài)的樹
- LL : 當(dāng)前節(jié)點(diǎn) node 的左子樹的高度 - 右子樹的高度 > 1，且 node.left 的左子樹的高度 - node.left 的右子樹的高度 >= 0 。實(shí)現(xiàn)該情況重新平衡，只需要當(dāng)前節(jié)點(diǎn)進(jìn)行右旋操作即可。
- LR：當(dāng)前節(jié)點(diǎn) node 的左子樹的高度 - 右子樹的高度 > 1，且 node.left 的左子樹的高度 - node.left 的右子樹的高度 < 0 。實(shí)現(xiàn)該情況重新平衡，需要進(jìn)行先將 node.left 節(jié)點(diǎn)進(jìn)行左旋，重新 node.left = leftRotate(node.left)，接著對(duì)于 node 進(jìn)行右旋即可，也就是上面已經(jīng)實(shí)現(xiàn)的左右旋方法。
- RL：當(dāng)前節(jié)點(diǎn) node 的左子樹的高度 - 右子樹的高度 < -1 ，且 node.right 的左子樹的高度 - node.right的右子樹的高度 >0 。實(shí)現(xiàn)該情況重新平衡，需要用到上面實(shí)現(xiàn)了的右左旋方法。
- RR：當(dāng)前節(jié)點(diǎn) node 的左子樹的高度 - 右子樹的高度 < -1 ，且 node.right 的左子樹的高度 - node.right 的右子樹的高度 <= 0 。實(shí)現(xiàn)該情況重新平衡，只需要左旋一次操作即可。
四種失衡狀態(tài)圖：
代碼如下：
//檢查節(jié)點(diǎn)是否失衡，重新平衡代碼
private AVLNode balance (AVLNode node) {
if(node == null) {
return null;
}
if (bf(node) > 1 && bf(node.left) >= 0) {
return rightRotate(node);
} else if (bf(node) > 1 && bf(node.left) < 0) {
return leftRightRotate(node);
} else if (bf(node) < -1 && bf(node.right) <= 0) {
return leftRotate(node);
}else if (bf(node) < -1 && bf(node.right) > 0) {
return rightLeftRotate(node);
}
return node;
}當(dāng) node == null 時(shí)，返回 null 即可。
插入與更新節(jié)點(diǎn)
put(int key, Object value)
使用遞歸實(shí)現(xiàn)插入、更新節(jié)點(diǎn)。兩種情況，若沒有找到 key 關(guān)鍵字時(shí)，而找到空位的地方插入新節(jié)點(diǎn)；若找到 key 關(guān)鍵字時(shí)，更新該節(jié)點(diǎn)的值即可。區(qū)別于一般的二叉搜索樹，自平衡的二叉搜索樹，需要在插入節(jié)點(diǎn)后更新當(dāng)前節(jié)點(diǎn)的高度和通過旋轉(zhuǎn)來重新達(dá)到平衡。需要注意的是，更新節(jié)點(diǎn)的操作是不會(huì)改變高度還有破壞平衡。
代碼如下：
//更新
public AVLNode put (int key, Object value) {
return doPut(root,key,value);
}
private AVLNode doPut(AVLNode node, int key, Object value) {
if (node == null) {
return new AVLNode(key,value);
}
if (node.key == key) {
node.value = value;
return node;
}
if (node.key > key) {
node.left = doPut(node.left,key,value);
}else {
node.right = doPut(node.right,key,value);
}
updateHeight(node);
return balance(node);
}刪除節(jié)點(diǎn)
remove(AVLNode node)
使用遞歸實(shí)現(xiàn)刪除節(jié)點(diǎn)思路：
（1）node == null
（2）沒有找到 key
（3）找到 key 1) 沒有 2）只有一個(gè)孩子 3）有兩個(gè)孩子
（4）更新高度
（5）balance
代碼如下：
//刪除
public AVLNode remove (int key) {
return doRemove(root,key);
}
private AVLNode doRemove (AVLNode node,int key) {
if (node == null) {
return null;
}
if (node.key > key) {
node.left = doRemove(node.left,key);
} else if (node.key < key) {
node.right = doRemove(node.right,key);
}else {
if (node.left == null && node.right == null) {
return null;
} else if (node.right == null) {
node = node.left;
} else if (node.left == null) {
node = node.right;
}else {
AVLNode p = node.right;
while (p.left != null) {
p = p.left;
}
p.right = doRemove(node.right,p.key);
p.left = node.left;
node = p;
}
}
updateHeight(node);
return balance(node);
}實(shí)現(xiàn)AVLTree核心方法的完整代碼
public class AVLTree {
AVLNode root = null;
static class AVLNode {
int key;
Object value;
AVLNode left;
AVLNode right;
int height = 1;
public AVLNode(int key, Object value) {
this.key = key;
this.value = value;
}
public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
//獲取當(dāng)前節(jié)點(diǎn)的高度
private int height (AVLNode node) {
return node == null ? 0 : node.height;
}
//更新當(dāng)前的高度
private void updateHeight (AVLNode node) {
node.height = Integer.max(height(node.left),height(node.right)) + 1;
}
//平衡因子
private int bf (AVLNode node) {
return height(node.left) - height(node.right);
}
//左旋
private AVLNode leftRotate (AVLNode node) {
AVLNode r = node.right;
node.right = r.left;
r.left = node;
updateHeight(node);
updateHeight(r);
return r;
}
//右旋
private AVLNode rightRotate (AVLNode node) {
AVLNode l = node.left;
node.left = l.right;
l.right = node;
updateHeight(node);
updateHeight(l);
return l;
}
//左右旋
private AVLNode leftRightRotate (AVLNode node) {
AVLNode l = node.left;
node.left = leftRotate(l);
return rightRotate(node);
}
//右左旋
private AVLNode rightLeftRotate (AVLNode node) {
AVLNode r = node.right;
node.right = rightRotate(r);
return leftRotate(node);
}
//檢查節(jié)點(diǎn)是否失衡，重新平衡代碼
private AVLNode balance (AVLNode node) {
if(node == null) {
return null;
}
if (bf(node) > 1 && bf(node.left) >= 0) {
return rightRotate(node);
} else if (bf(node) > 1 && bf(node.left) < 0) {
return leftRightRotate(node);
} else if (bf(node) < -1 && bf(node.right) <= 0) {
return leftRotate(node);
}else if (bf(node) < -1 && bf(node.right) > 0) {
return rightLeftRotate(node);
}
return node;
}
//更新
public AVLNode put (int key, Object value) {
return doPut(root,key,value);
}
private AVLNode doPut(AVLNode node, int key, Object value) {
if (node == null) {
return new AVLNode(key,value);
}
if (node.key == key) {
node.value = value;
return node;
}
if (node.key > key) {
node.left = doPut(node.left,key,value);
}else {
node.right = doPut(node.right,key,value);
}
updateHeight(node);
return balance(node);
}
//刪除
public AVLNode remove (int key) {
return doRemove(root,key);
}
private AVLNode doRemove (AVLNode node,int key) {
if (node == null) {
return null;
}
if (node.key > key) {
node.left = doRemove(node.left,key);
} else if (node.key < key) {
node.right = doRemove(node.right,key);
}else {
if (node.left == null && node.right == null) {
return null;
} else if (node.right == null) {
node = node.left;
} else if (node.left == null) {
node = node.right;
}else {
AVLNode p = node.right;
while (p.left != null) {
p = p.left;
}
p.right = doRemove(node.right,p.key);
p.left = node.left;
node = p;
}
}
updateHeight(node);
return balance(node);
}
}到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)中關(guān)于AVL樹的實(shí)現(xiàn)方法詳解的文章就介紹到這了,更多相關(guān)Java AVL樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Java數(shù)據(jù)結(jié)構(gòu)之紅黑樹的實(shí)現(xiàn)方法和原理詳解
- Java數(shù)據(jù)結(jié)構(gòu)中七種排序算法實(shí)現(xiàn)詳解
- Java數(shù)據(jù)結(jié)構(gòu)和算法之鏈表詳解
- Java數(shù)據(jù)結(jié)構(gòu)篇之實(shí)現(xiàn)二叉搜索樹的核心方法
- Java數(shù)據(jù)結(jié)構(gòu)與算法之二分查找詳解
- Java數(shù)據(jù)結(jié)構(gòu)中的HashMap和HashSet詳解
- Java常見的數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列詳解
- java手動(dòng)實(shí)現(xiàn)常見數(shù)據(jù)結(jié)構(gòu)的示例代碼
相關(guān)文章
SpringBoot中Druid連接池與多數(shù)據(jù)源切換的方法
微服務(wù)架構(gòu)中多數(shù)據(jù)源切換是個(gè)常見的需求,Spring Boot 提供了強(qiáng)大的支持來簡(jiǎn)化這一過程.本文給大家介紹了SpringBoot中Druid連接池與多數(shù)據(jù)源切換的方法,需要的朋友可以參考下2024-11-11
這篇文章主要介紹了Java常用工具類—泛型，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
Spring Security Oauth2.0認(rèn)證授權(quán)教程
Spring Security實(shí)現(xiàn)用戶認(rèn)證、會(huì)話管理及授權(quán),支持Token等多方式,OAuth2.0用于分布式系統(tǒng)統(tǒng)一認(rèn)證,網(wǎng)關(guān)解析令牌并轉(zhuǎn)發(fā)請(qǐng)求2025-07-07
Java數(shù)據(jù)結(jié)構(gòu)之最小堆和最大堆的原理及實(shí)現(xiàn)詳解
在計(jì)算機(jī)科學(xué)中，堆(heap)?的實(shí)現(xiàn)是一種基于樹的特殊的數(shù)據(jù)結(jié)構(gòu)，它可以在數(shù)組上構(gòu)建出樹的結(jié)構(gòu)體，并滿足堆的屬性。本文就來和大家詳細(xì)聊聊Java數(shù)據(jù)結(jié)構(gòu)中的堆，感興趣的可以了解一下2022-09-09
通過Spring Boot + Mybatis + Redis快速搭建現(xiàn)代化Web項(xiàng)目
本篇文章介紹了如何通過Spring Boot、Mybatis以及Redis快速搭建一個(gè)現(xiàn)代化的Web項(xiàng)目，并且同時(shí)介紹了如何在Spring Boot下優(yōu)雅地書寫單元測(cè)試來保證我們的代碼質(zhì)量。具體內(nèi)容詳情大家通過本文學(xué)習(xí)下吧2017-12-12
詳解Nacos中注冊(cè)中心和配置中心的實(shí)現(xiàn)
Spring?Cloud?Alibaba?是阿里巴巴提供的一站式微服務(wù)開發(fā)解決方案。而?Nacos?作為?Spring?Cloud?Alibaba?的核心組件之一，提供了兩個(gè)非常重要的功能：注冊(cè)中心和配置中心，我們今天來了解和實(shí)現(xiàn)一下二者2022-08-08
如何使用mybatis-plus實(shí)現(xiàn)分頁查詢功能
最近在研究mybatis,然后就去找簡(jiǎn)化mybatis開發(fā)的工具,發(fā)現(xiàn)就有通用Mapper和mybatis-plus兩個(gè)比較好的可是使用,可是經(jīng)過對(duì)比發(fā)現(xiàn)還是mybatis-plus比較好,下面這篇文章主要給大家介紹了關(guān)于如何使用mybatis-plus實(shí)現(xiàn)分頁查詢功能的相關(guān)資料,需要的朋友可以參考下2022-06-06
Spring 框架實(shí)現(xiàn)賬戶轉(zhuǎn)賬功能(推薦)
通過本文的介紹,我們了解了如何使用Spring框架實(shí)現(xiàn)一個(gè)簡(jiǎn)單的賬戶轉(zhuǎn)賬功能,主要使用了 Spring 的依賴注入、和事務(wù)管理功能,保證了轉(zhuǎn)賬操作的原子性和數(shù)據(jù)的一致性,感興趣的朋友跟隨小編一起看看吧2025-07-07
Spring ApplicationContext接口功能詳細(xì)介紹
ApplicationContext是Spring應(yīng)用程序中的中央接口，由于繼承了多個(gè)組件，使得ApplicationContext擁有了許多Spring的核心功能，如獲取bean組件，注冊(cè)監(jiān)聽事件，加載資源文件等2023-02-02
這篇文章主要介紹了一個(gè)Java編程的小程序-點(diǎn)餐系統(tǒng)，算是對(duì)之前所學(xué)習(xí)的Java基礎(chǔ)知識(shí)作了一個(gè)匯總,需要的朋友可以參考下2017-09-09