Java深入分析了解平衡二叉樹
更新時間：2022年06月03日 10:31:15 作者：洛語言
平衡二叉樹又被稱為AVL樹（有別于AVL算法），且具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。本文將詳解介紹一下平衡二叉樹的原理與實現(xiàn)，需要的可以參考一下
AVL樹的引入
搜索二叉樹有著極高的搜索效率，但是搜索二叉樹會出現(xiàn)以下極端情況：
這樣的二叉樹搜索效率甚至比鏈表還低。在搜索二叉樹基礎上出現(xiàn)的平衡二叉樹(AVL樹)就解決了這樣的問題。當平衡二叉樹(AVL樹)的某個節(jié)點左右子樹高度差的絕對值大于1時，就會通過旋轉(zhuǎn)操作減小它們的高度差。
基本概念
AVL樹本質(zhì)上還是一棵二叉搜索樹，它的特點是：
- 本身首先是一棵二叉搜索樹。
- 每個結(jié)點的左右子樹的高度之差的絕對值（平衡因子）最多為1。也就是說，AVL樹，本質(zhì)上是帶了平衡功能的二叉查找樹（二叉排序樹，二叉搜索樹）。
- 當插入一個節(jié)點或者刪除一個節(jié)點時，導致某一個節(jié)點的左右子樹高度差的絕對值大于1，這時需要通過左旋和右旋的操作使二叉樹再次達到平衡狀態(tài)。
平衡因子(balanceFactor)
- 一個結(jié)點的左子樹與右子樹的高度之差。
- AVL樹中的任意結(jié)點的BF只可能是-1，0和1。
基礎設計
下面是AVL樹需要的簡單方法和屬性：
public class AVLTree <E extends Comparable<E>>{
class Node{
E value;
Node left;
Node right;
int height;
public Node(){}
public Node(E value){
this.value = value;
height = 1;
left = null;
right = null;
}
public void display(){
System.out.print(this.value + " ");
}
}
Node root;
int size;
public int size(){
return size;
}
public int getHeight(Node node) {
if(node == null) return 0;
return node.height;
}
//獲取平衡因子(左右子樹的高度差，大小為1或者0是平衡的，大小大于1不平衡)
public int getBalanceFactor(){
return getBalanceFactor(root);
}
public int getBalanceFactor(Node node){
if(node == null) return 0;
return getHeight(node.left) - getHeight(node.right);
}
//判斷一個樹是否是一個平衡二叉樹
public boolean isBalance(Node node){
if(node == null) return true;
int balanceFactor = Math.abs(getBalanceFactor(node.left) - getBalanceFactor(node.right));
if(balanceFactor > 1) return false;
return isBalance(node.left) && isBalance(node.right);
}
public boolean isBalance(){
return isBalance(root);
}
//中序遍歷樹
private void inPrevOrder(Node root){
if(root == null) return;
inPrevOrder(root.left);
root.display();
inPrevOrder(root.right);
}
public void inPrevOrder(){
System.out.print("中序遍歷：");
inPrevOrder(root);
}
}
RR(左旋)
往一個樹右子樹的右子樹上插入一個節(jié)點，導致二叉樹變得不在平衡，如下圖，往平衡二叉樹中插入5，導致這個樹變得不再平衡，此時需要左旋操作，如下：
代碼如下：
//左旋,并且返回新的根節(jié)點
public Node leftRotate(Node node){
System.out.println("leftRotate");
Node cur = node.right;
node.right = cur.left;
cur.left = node;
//跟新node和cur的高度
node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
return cur;
}
LL(右旋)
往一個AVL樹左子樹的左子樹上插入一個節(jié)點，導致二叉樹變得不在平衡，如下圖，往平衡二叉樹中插入2，導致這個樹變得不再平衡，此時需要左旋操作，如下：
代碼如下：
//右旋，并且返回新的根節(jié)點
public Node rightRotate(Node node){
System.out.println("rightRotate");
Node cur = node.left;
node.left = cur.right;
cur.right = node;
//跟新node和cur的高度
node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
return cur;
}
LR(先左旋再右旋)
往AVL樹左子樹的右子樹上插入一個節(jié)點，導致該樹不再平衡，需要先對左子樹進行左旋，再對整棵樹右旋，如下圖所示，插入節(jié)點為5.
RL(先右旋再左旋)
往AVL樹右子樹的左子樹上插入一個節(jié)點，導致該樹不再平衡，需要先對右子樹進行右旋，再對整棵樹左旋，如下圖所示，插入節(jié)點為2.
添加節(jié)點
//添加元素
public void add(E e){
root = add(root,e);
}
public Node add(Node node, E value) {
if (node == null) {
size++;
return new Node(value);
}
if (value.compareTo(node.value) > 0) {
node.right = add(node.right, value);
} else if (value.compareTo(node.value) < 0) {
node.left = add(node.left, value);
}
//跟新節(jié)點高度
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
//獲取當前節(jié)點的平衡因子
int balanceFactor = getBalanceFactor(node);
//該子樹不平衡且新插入節(jié)點(導致不平衡的節(jié)點)在左子樹的左子樹上，此時需要進行右旋
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
return rightRotate(node);
}
//該子樹不平衡且新插入節(jié)點(導致不平衡的節(jié)點)在右子樹子樹的右子樹上，此時需要進行左旋
else if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
return leftRotate(node);
}
//該子樹不平衡且新插入節(jié)點(導致不平衡的節(jié)點)在左子樹的右子樹上，此時需要先對左子樹左旋，在整個樹右旋
else if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
//balanceFactor < -1 && getBalanceFactor(node.left) > 0
//該子樹不平衡且新插入節(jié)點(導致不平衡的節(jié)點)在右子樹的左子樹上，此時需要先對右子樹右旋，再整個樹左旋
else if(balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
刪除節(jié)點
//刪除節(jié)點
public E remove(E value){
root = remove(root,value);
if(root == null){
return null;
}
return root.value;
}
public Node remove(Node node, E value){
Node retNode = null;
if(node == null)
return retNode;
if(value.compareTo(node.value) > 0){
node.right = remove(node.right,value);
retNode = node;
}
else if(value.compareTo(node.value) < 0){
node.left = remove(node.left,value);
retNode = node;
}
//value.compareTo(node.value) = 0
else{
//左右節(jié)點都為空，或者左節(jié)點為空
if(node.left == null){
size--;
retNode = node.right;
}
//右節(jié)點為空
else if(node.right == null){
size--;
retNode = node.left;
}
//左右節(jié)點都不為空
else{
Node successor = new Node();
//尋找右子樹最小的節(jié)點
Node cur = node.right;
while(cur.left != null){
cur = cur.left;
}
successor.value = cur.value;
successor.right = remove(node.right,value);
successor.left = node.left;
node.left = node.right = null;
retNode = successor;
}
if(retNode == null)
return null;
//維護二叉樹平衡
//跟新height
retNode.height = Math.max(getHeight(retNode.left),getHeight(retNode.right));
}
int balanceFactor = getBalanceFactor(retNode);
//該子樹不平衡且新插入節(jié)點(導致不平衡的節(jié)點)在左子樹的左子樹上，此時需要進行右旋
if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
return rightRotate(retNode);
}
//該子樹不平衡且新插入節(jié)點(導致不平衡的節(jié)點)在右子樹子樹的右子樹上，此時需要進行左旋
else if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
return leftRotate(retNode);
}
//該子樹不平衡且新插入節(jié)點(導致不平衡的節(jié)點)在左子樹的右子樹上，此時需要先對左子樹左旋，在整個樹右旋
else if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
retNode.left = leftRotate(retNode.left);
return rightRotate(retNode);
}
//該子樹不平衡且新插入節(jié)點(導致不平衡的節(jié)點)在右子樹的左子樹上，此時需要先對右子樹右旋，再整個樹左旋
else if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
}
return retNode;
}
到此這篇關于Java深入分析了解平衡二叉樹的文章就介紹到這了,更多相關Java平衡二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
本文核心為分層領域模型（VO ， PO ， BO， DAO ，POJO等）概念的個人理解，結(jié)合springmvc淺談分層領域模型的相關知識，感興趣的朋友跟隨小編一起看看吧2021-08-08
IDEA創(chuàng)建Java項目保姆級教程(超詳細!)
這篇文章主要給大家介紹了關于IDEA創(chuàng)建Java項目保姆級教程的相關資料,Java是一種廣泛使用的編程語言,廣泛用于Web應用程序和客戶端應用程序的開發(fā),文中通過圖文介紹的非常詳細,需要的朋友可以參考下2023-09-09
詳解Spring Boot使用系統(tǒng)參數(shù)表提升系統(tǒng)的靈活性
Spring Boot項目中常有一些相對穩(wěn)定的參數(shù)設置項，其作用范圍是系統(tǒng)級的或模塊級的，這些參數(shù)稱為系統(tǒng)參數(shù)。這些變量以參數(shù)形式進行配置，從而提高變動和擴展的靈活性，保持代碼的穩(wěn)定性2021-06-06
IDEA配置Tomcat創(chuàng)建web項目的詳細步驟
Tomcat是一個Java?Web應用服務器,實現(xiàn)了多個Java?EE規(guī)范(JSP、Java?Servlet等),這篇文章主要給大家介紹了關于IDEA配置Tomcat創(chuàng)建web項目的詳細步驟,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了Java獲取此次請求URL以及服務器根路徑的方法,需要的朋友可以參考下2015-08-08
這篇文章主要介紹了java根據(jù)url抓取并生成縮略圖的示例,需要的朋友可以參考下2014-05-05
解決Java中由于數(shù)據(jù)太大自動轉(zhuǎn)換成科學計數(shù)法的問題
今天小編就為大家分享一篇解決Java中由于數(shù)據(jù)太大自動轉(zhuǎn)換成科學計數(shù)法的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
這篇文章主要為大家介紹了java?guava主要功能介紹及使用心得總結(jié)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04
這篇文章主要介紹了Java類初始化時機測試過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-08-08
利用Java實現(xiàn)更改Word中的頁面大小和頁面方向
這篇文章主要為大家詳細介紹了一種高效便捷的方法——通過Java應用程序，以編程方式更改Word中的頁面大小和頁面方向，感興趣的可以了解一下2023-03-03