平衡二叉樹 AVL樹結構詳解 [Java實現]

2021-01-07 百家號

作者

NeroJings

來源

https://blog.csdn.net/zhang6622056/article/details/82698859

本文思維導圖

簡述

先不說平衡二叉樹，我們單開來說，這樣比較方便理解。

先說二叉樹，再說平衡條件，沒那麼多花裡胡哨的理論，我只是想讓大家看完能明白，能寫出來。

二叉樹

什麼是二叉樹？二叉樹數據結構，顧名思義，只有兩個叉，在數據結構中，操作性能要遠高於線性結構，有O(height)的索引性能。與線性結構有相同的空間複雜度,特性如下：

每個節點最多只有兩個兒子節點左兒子小，右兒子大 (大小按照我們默認的比較規則，本例用int來比較)線行找7與二叉數找7

線性找7

二叉樹找7 okay,我想大家聰明人已經看出來了，二叉樹搜索用了2次，而線性結構卻用了5次。

說白了，二叉樹結構，我每次問一個節點，都會離著我的目標越來越近，但是線性的則不然，我必須一個個問。

說到這兒，我想會有博友提出質疑了，如果線性查找，7恰好就在第一個呢？那不是一下就找到了嗎？

哈哈，你怎麼不上天呢 - -。還第一個。開個小玩笑。

這就是二叉樹索引的好處。相比看圖比碼字要清楚的多。

平衡條件

那麼，什麼叫平衡呢？其實很簡單，任何一個節點的子節點高度差必須小於2

第一個二叉平衡樹

從下往上數，第一個高度為1(比較符合日常生活數數),那我們數數吧5:———1高度 | 4,7,23,71 ———2高度| 6,50 ———3高度 | 15 ———4高度比如節點6，那麼4和7的高度都是2，那就2-2 < 2 。平衡！！難點一 遞歸

遞歸查找

我又加入了一些節點，方便大家理解遞歸深度

每一次正向橙色線條的滾動，就是一次遞歸查找每一次正向橙色線條的滾動，方法的入棧！遞歸的深度，取決於線條走了幾次，那就有多大的棧深度本次查找，刨除root，共4次進棧 難點二 回溯

插入回溯

先不要關心這個旋轉操作，如圖所示，我們在遞歸的基礎上，沿著線條理解一下回溯

每一次逆向橙色線條的滾動，就是一次回溯操作遞歸的每一個節點，都會在回溯的軌跡上正因為每一次遞歸，都有每一次回溯，那麼，我們就可以先完成相關操作(增加或刪除)之後，判定平衡 4種旋轉

左左類型旋轉

博主儘量放慢了速度，讓大家看清楚究竟旋轉是如何進行的,這是一個插入操作，我們看到在不平衡的時候，進行了左旋轉，這裡我們看到

正向插入，遞歸3-2-1逆向回溯，1-2 判斷平衡條件 ，是平衡的再次回溯，2-3，3的左邊高度為2，右邊沒有節點為0，那麼2-0 > 1，不平衡！到這裡我們基本上理解了平衡的判斷，下面正式說一下旋轉:

判斷不平衡邊 在3節點判定，不平衡，那麼左邊高，我們需要調整左邊，獲取左邊節點2判斷旋轉類型 這時候我們拿到節點2，判斷節點2哪邊高。左邊高，為左左類型。右邊高為左右旋轉類型，我們先不管旋轉操作 3.left = 2.right; 2.right = 3; 重新計算，2和3節點的高度

右右類型旋轉[同上，不再敘述]

左右類型旋轉

右左類型旋轉

到此旋轉就說完了，希望大家好好的理解第一個左左類型!（理解了一個也就都理解了）

後續部分沒有講是因為說太多反而更亂。

後續的理解不了沒關係，我們代碼在看。

代碼基礎部分

node類

publicstaticclassAvlNodeInteger{private Integer value;private Integer height;private AvlNodeInteger left;private AvlNodeInteger right;publicAvlNodeInteger(int t){ initNode(t,null,null,1); }publicAvlNodeInteger(int t,AvlNodeInteger left,AvlNodeInteger right){ initNode(t,left,right,null); }privatevoidinitNode(int t,AvlNodeInteger left,AvlNodeInteger right,Integer height){this.setValue(t);this.left = left;this.right = right;this.height = height; }public Integer getValue() {returnvalue; }publicvoidsetValue(Integer value) {this.value = value; }public Integer getHeight() {return height; }publicvoidsetHeight(Integer height) {this.height = height; }public AvlNodeInteger getLeft() {return left; }publicvoidsetLeft(AvlNodeInteger left) {this.left = left; }public AvlNodeInteger getRight() {return right; }publicvoidsetRight(AvlNodeInteger right) {this.right = right; } }高度計算

/**** 求一個節點的高度 * @param t * @return */privateintheight(AvlNodeInteger t){returnnull == t ? 0 : t.getHeight(); }

/*** * 求左右子節點最大高度 * @param left * @param right * @return */privateint maxHeight(AvlNodeInteger left,AvlNodeInteger right){ return height(left) > height(right) ? height(left) : height(right); }插入操作

旋轉

/*** * 左左旋轉模型 * @param node 旋轉之前的parent node 節點 * @return 旋轉之後的parent node節點 */private AvlNodeInteger leftLeftRotate(AvlNodeInteger node){ AvlNodeInteger newRoot = node.getLeft(); node.setLeft(newRoot.getRight()); newRoot.setRight(node);//由此node的高度降低了，newRoot的高度提高了。//newRoot的高度由node的高度而來 node.setHeight(maxHeight(node.getLeft(),node.getRight())+1); newRoot.setHeight(maxHeight(newRoot.getLeft(),newRoot.getRight())+1);return newRoot; }/*** * 右右旋轉模型 * @param node * @return */private AvlNodeInteger rightRightRotate(AvlNodeInteger node){ AvlNodeInteger newRoot = node.getRight(); node.setRight(newRoot.getLeft()); newRoot.setLeft(node);//由此node的高度降低了，newRoot的高度提高了。//newRoot的高度由node的高度而來 node.setHeight(maxHeight(node.getLeft(),node.getRight())); newRoot.setHeight(maxHeight(newRoot.getLeft(),newRoot.getRight()));return newRoot; }/** * 左右模型，先右右，再左左 * @param node * @return */private AvlNodeInteger leftRightRotate(AvlNodeInteger node){//注意傳遞的參數 node.setLeft(rightRightRotate(node.getLeft()));return leftLeftRotate(node); }/*** * 右左模型，先左左，在右右 * @param node * @return */private AvlNodeInteger rightLeftRotate(AvlNodeInteger node){ node.setRight(leftLeftRotate(node.getRight()));return rightRightRotate(node); }insert

/**** * 對外開放，插入操作 * @param val * @throws Exception */public void insert(Integer val) throws Exception {if(null == root){ initRoot(val); size++;return; }if(contains(val)) thrownewException("The value is already exist!"); insertNode(this.root,val); size++; }/** * 遞歸插入 * parent == null 到最底部插入前節點判斷情況 * @param parent * @param val * @return */private AvlNodeInteger insertNode(AvlNodeInteger parent,Integer val){if(parent == null){return createSingleNode(val); }if(val < parent.getValue()){ //插入判斷，小於父節點，插入到右邊//注意理解回溯，這裡最終返回的是插入完成節點//每一層回溯，都會返回相應當時遞歸的節點！！！parent.setLeft(insertNode(parent.getLeft(),val));//判斷平衡，不要在意這裡的parent是誰，//這個parent肯定是遞歸層級上，回溯的一個節點！每一個節點都需要判斷平衡if(height(parent.getLeft()) - height(parent.getRight()) > 1){ Integer compareVal = (Integer) parent.getLeft().getValue();//左左旋轉類型if(val < Integer.valueOf(compareVal)){parent = leftLeftRotate(parent); }else{ //左右旋轉類型parent = leftRightRotate(parent); } } }if(val > parent.getValue()){ //插入判斷，小於父節點，插入到右邊//注意理解回溯，這裡最終返回的是插入完成節點//每一層回溯，都會返回相應當時遞歸的節點！！！parent.setRight(insertNode(parent.getRight(),val));//判斷平衡，不要在意這裡的parent是誰，//這個parent肯定是遞歸層級上，回溯的一個節點！每一個節點都需要判斷平衡if(height(parent.getRight()) - height(parent.getLeft()) > 2){ Integer compareVal = (Integer) parent.getLeft().getValue();if(val > compareVal){parent = rightRightRotate(parent); }else{parent = rightLeftRotate(parent); } } }parent.setHeight((maxHeight(parent.getLeft(),parent.getRight()))+1);returnparent; }刪除操作

public void remove(Integer val) {if(null == val || null == root){return;}if(!contains(val)){return; } remove(root,val); }/**** * AVL刪除，平衡樹實現 * @param parent * @param val * @return */private AvlNodeInteger remove(AvlNodeInteger parent,Integer val){if(val < parent.getValue()){ //左子樹遞歸查詢//刪除以後返回替換的新節點 AvlNodeInteger newLeft = remove(parent.getLeft(),val);parent.setLeft(newLeft);//檢查是否平衡，刪除的左邊，那麼用右邊-左邊if(height(parent.getRight()) - height(parent.getLeft()) > 1){ AvlNodeInteger tempNode = parent.getRight();if(height(tempNode.getLeft()) > height(tempNode.getRight())){ //RL類型 rightLeftRotate(parent); }else{ //RR類型 rightRightRotate(parent); } } }elseif(val > parent.getValue()){ //右子樹遞歸查找//刪除以後返回替換的新節點 AvlNodeInteger newRight = remove(parent.getRight(),val);parent.setRight(newRight);//檢查是否平衡if(height(parent.getLeft()) - height(parent.getRight()) > 1){ AvlNodeInteger tempNode = parent.getLeft();if(height(tempNode.getLeft()) > height(tempNode.getRight())){ //LL類型 leftLeftRotate(parent); }else{ //LR類型 leftRightRotate(parent); } } }else{ //相等，匹配成功if(null != parent.getLeft() && null != parent.getRight()){ //左右子節點都不為空//判斷高度，高的一方，拿到最大(左)，最小(右)的節點，作為替換節點。//刪除原來匹配節點//左邊更高，獲取到左邊最大的節點if(parent.getLeft().getHeight() > parent.getRight().getHeight()){ AvlNodeInteger leftMax = getMax(parent.getLeft());parent.setLeft(remove(parent.getLeft(),leftMax.getValue())); leftMax.setLeft(parent.getLeft()); leftMax.setRight(parent.getRight()); leftMax.setHeight(maxHeight(leftMax.getLeft(),leftMax.getRight()));parent = leftMax; }else{ //右邊更高，獲取到右邊最小的節點 AvlNodeInteger rightMin = getMin(parent.getRight());parent.setRight(remove(parent.getRight(),rightMin.getValue())); rightMin.setLeft(parent.getLeft()); rightMin.setRight(parent.getRight()); rightMin.setHeight(maxHeight(parent.getLeft(),parent.getRight())+1);parent = rightMin; } }else{//有任意一方節點為空，則不為空的那一方作為替換節點，刪除原來的節點parent = null; } }returnparent; }/*** * 刪除時用到，獲取當前節點子節點最大值 * @param currentRoot * @return */private AvlNodeInteger getMax(AvlNodeInteger currentRoot){if(currentRoot.getRight() != null){ currentRoot = getMax(currentRoot.getRight()); }return currentRoot; }/*** * 刪除時用到，獲取當前節點子節點最小值 * @param currentRoot * @return */private AvlNodeInteger getMin(AvlNodeInteger currentRoot){if(currentRoot.getLeft() != null){ currentRoot = getMin(currentRoot.getLeft()); }return currentRoot; }

以上就是難點插入和刪除的實現了， 沒有過多闡述，是因為大家如果真的理解了上面說明的理論， 那麼應該沒有問題來理解這些code。

當然有任何問題大家可以在留言區回復我 ，歡迎大家指正!

4種遍歷

前序遍歷 根左右中序遍歷 左跟右後序遍歷 左右根層級遍歷 從root開始，一層層

相關焦點

  • 什麼是平衡二叉樹(AVL)
    前言Wiki:在計算機科學中，AVL樹是最早被發明的自平衡二叉查找樹。在AVL樹中，任一節點對應的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時間複雜度都是O(logn)。增加和刪除元素的操作則可能需要藉由一次或多次樹旋轉，以實現樹的重新平衡。
  • 數據結構(八)--平衡二叉樹
    該來的總會來，平衡二叉樹果然又來了....出現背景前文已經研究過普通的二叉樹，為什麼要用二叉樹呢？因為二叉樹的結構可以實現二分法查找的效果。你比如前文介紹的滿二叉樹：如下圖所示，如果你想要查找4號元素，你只需要遍歷3次即可。所以在理想情況下，二叉樹可以優化遍歷。
  • 數據結構 | 四種平衡二叉樹介紹
    二叉樹是樹形結構的一個重要類型，許多實際問題抽象出來的數據結構往往都是二叉樹的類型。即使是一般的樹也可以轉化為二叉樹，並且二叉樹的存儲結構和算法相對而言都比較簡單。因此研究二叉樹對於研究數據結構有著重要的意義。
  • 一文讀懂 AVL 樹
    背景AVL 樹是一棵平衡的二叉查找樹，於 1962 年，G. M.
  • 二叉查找樹 Java實現
    }BSTree是二叉樹，它保護了二叉樹的根節點mRoot；mRoot是BSTNode類型，而BSTNode是二叉查找樹的節點，它是BSTree的內部類。BSTNode包含二叉查找樹的幾個基本信息：(01) key    -- 它是關鍵字，是用來對二叉查找樹的節點進行排序的。(02) left   -- 它指向當前節點的左孩子。
  • 平衡二叉樹專題
    力扣關於平衡二叉樹的題目還是有一些的，並且都非常經典，推薦大家練習。今天給大家精選了 4 道題，如果你徹底搞明白了這幾道題，碰到其他的平衡二叉樹的題目應該不至於沒有思路。當你領會了我的思路之後， 建議再找幾個題目練手，鞏固一下學習成果。110.
  • 五分鐘帶你玩轉平衡二叉樹
    通過上一篇二叉查找樹的文章，相信大家已經掌握了二叉查找樹的相關概念和操作，如果忘了可以通過下方的連結進行學習。帶你玩轉二叉查找樹本文呢，我們將在二叉查找樹的基礎上，繼續學習一種新的樹狀結構-平衡二叉樹。
  • 樹型結構詳解
    本文探討另外一種重要的數據結構----樹，其大部分時間可以保證操作的運行平均時間複雜度為O(logN)，第一部分先來看一下樹的一些預備知識。首先看一下樹形結構的樣子，下圖代表的是樹型結構的一般形態：在下一部分的二叉查找樹說明完之後，會講讓二叉樹帶有自平衡條件，成為平衡樹。 二叉查找樹二叉樹的一個重要應用是在它們查找中的使用。
  • 騰訊面試題:有了二叉查找樹、平衡樹為啥還需要紅黑樹?
    本文作者：帥地紅黑樹算是很難的一種數據結構吧，一般很少考察插入、刪除等具體操作步驟，如果遇到要你手寫紅黑樹的面試官，就直接告辭吧。所以，更多是會考察你對紅黑樹的理解程度，考察的最多的估計就是為什麼有了二查找查找樹/平衡樹還需要紅黑樹這個問題了，今天，你只需要花一分鐘的時間，就知道怎麼回答這個問題了。
  • 一文讀懂平衡二叉樹|技術頭條
    作者 | 宋廣澤責編 | 伍杏玲出品 | CSDN(ID：CSDNnews)平衡二叉樹，又稱AVL樹，指的是左子樹上的所有節點的值都比根節點的值小，而右子樹上的所有節點的值都比根節點的值大，且左子樹與右子樹的高度差最大為1。因此，平衡二叉樹滿足所有二叉排序（搜索）樹的性質。
  • 二叉查找樹之 Java的實現【上】
    二叉查找樹(Binary Search Tree)，又被稱為二叉搜索樹。它是特殊的二叉樹：對於二叉樹，假設x為二叉樹中的任意一個結點，x節點包含關鍵字key，節點x的key值記為key[x]。如果y是x的左子樹中的一個結點，則key[y] <= key[x]；如果y是x的右子樹的一個結點，則key[y] >= key[x]。那麼，這棵樹就是二叉查找樹。如下圖所示：
  • 數據結構+算法(第11篇)玩平衡二叉樹就像蹺蹺板一樣簡單!
    二分查找樹》中提到了：平衡二叉樹的目的就是使得平均查找長度最短。那麼這裡就引出兩個問題：什麼是平衡二叉樹？為什麼平衡二叉樹的平均查找長度最短？如何將非平衡二叉樹調整成平衡二叉樹？1. 平衡二叉樹是什麼鬼？
  • 【數據結構與算法圖文動畫詳解】終於可以徹底弄懂:紅黑樹、B-樹、B+樹、B*樹、滿二叉樹、完全二叉樹、平衡二叉樹、二叉搜索樹
    通過自平衡操作（即旋轉）構建兩個子樹高度差不超過1的平衡二叉樹。> 具體可以參閱1962年G.M. Adelson-Velsky 和 E.M. Landis的論文"An algorithm for the organization of information"。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。
  • 圖解:什麼是AVL樹?(上篇)
    平衡二叉樹（Balanced Binary Tree 或 Height-Balanced Tree）又稱為 AVL 樹，其實就是一顆 平衡的二叉排序樹 ，解決了昨天講的二叉排序樹的不平衡問題，即斜樹。AVL樹或者是一顆空樹，或者是具有下列性質的二叉排序樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過 1 。什麼是平衡因子？
  • 「算法與數據結構」二叉樹之美
    腦圖👇樹的基本概念樹是用來模擬具有樹狀結構性質的數據集合。或者你可以把它認為是一種「抽象數據結構」或是實現這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。我們可以根據維基百科的依據來作為分類的標準👇無序樹：樹中任意節點的子節點之間沒有順序關係，這種樹稱為無序樹，也稱為自由樹；有序樹：樹中任意節點的子節點之間有順序關係，這種樹稱為有序樹；完全二叉樹：對於一顆二叉樹，假設其深度為d（d>1）。
  • 二叉樹結構相關算法總結 | 原力計劃
    寫在前面樹結構對於程式設計師來說應該不陌生，特別是二叉樹，基本只要接觸算法這一類的都一定會碰到的，所以我打算通過一篇文章，對二叉樹結構的相關算法進行總結匯總，思路和代碼實現相結合，後面如果遇到特殊的思路結構，如多叉樹，我會特別說明。首先我們先給出二叉樹的節點定義（這個定義應該不陌生吧，有刷算法題都會碰到）。
  • 二叉樹的應用—二叉樹遍歷的應用
    1．查找數據元素Search（bt，x）在bt 為二叉樹的根結點指針的二叉樹中查找數據元素x。查找成功時返回該結點的指針；查找失敗時返回空指針。算法實現如下，注意遍歷算法中的Visite(bt->data)等同於其中的一組操作步驟。
  • Python數據結構——AVL樹的實現
    由於這是一個遞歸的過程，我們看看更新平衡因子的兩個基本條件：我們將實現AVL樹的子類BinarySearchTree。首先，我們將重寫_put方法，並寫一個新的輔助方法updateBalance。這些方法如Listing 1所示。除了第7行和第13行對 updateBalance的調用，你會注意到_put和簡單的二叉搜索樹的定義完全相同。
  • Python數據結構――AVL樹的實現
    由於這是一個遞歸的過程，我們看看更新平衡因子的兩個基本條件： 遞歸調用已到達樹的根。 父節點的平衡因子已調整為零。一旦子樹平衡因子為零，那麼父節點的平衡因子不會發生改變。 我們將實現 AVL 樹的子類BinarySearchTree。首先，我們將重寫_put方法，並寫一個新的輔助方法updateBalance。
  • 圖解:什麼是AVL樹?(刪除總結篇)
    上一篇文章討論了平衡二叉樹的插入操作，沒有看的可以去看一下 圖解：什麼是AVL樹？，有助於理解今天要講的平衡二叉樹的刪除操作。平衡二叉樹的優缺點分析優點平衡二叉樹的優點不言而喻，相對於二叉排序樹（BST）而言，平衡二叉樹避免了二叉排序樹可能出現的最極端情況（斜樹）問題，其平均查找的時間複雜度為