平衡二叉樹的左右旋以及雙旋轉的圖文詳解
高度平衡的搜索二叉樹
一棵平衡樹，或是空樹，或是具有以下性質的二叉搜索樹：左子樹和右子樹都是AVL樹，且左右子樹的高度之差的絕對值不超過1。
該二叉樹，根結點的右子樹高度為3，左子樹高度為2。結點上方的數(shù)字為平衡因子，因為右子樹高度比左子樹高度大1，所以根結點的平衡因子為1。
一顆平衡二叉樹，如果有n個結點，其高度可保持O(log2^n),平均搜索長度也可以保持在O(log2^n)
平衡化旋轉
AVL樹相較于普通的二叉搜索樹，自主要的就是做了平衡化處理，使得二叉樹變的平衡，高度降低。
在插入一個結點后應該沿搜索路徑將路徑上的結點平衡因子進行修改，當平衡因子大于1時，就需要進行平衡化處理。從發(fā)生不平衡的結點起，沿剛才回溯的路徑取直接下兩層的結點，如果這三個結點在一條直線上，則采用單旋轉進行平衡化，如果這三個結點位于一條折線上，則采用雙旋轉進行平衡化。
單旋轉
左單旋
動圖演示，圖片內容可以無視，看懂操作進行了
將右子樹的左子樹鏈接到父親節(jié)點的右孩子結點，父親節(jié)點作為ptr結點的左孩子結點便完成了旋轉
右單旋
右單旋是左單旋的鏡像旋轉.
當前節(jié)點ptr，與父親節(jié)點和當前節(jié)點的左孩子結點位于一條直線上時，使用右單旋進行平衡。
雙旋轉
先左后右雙旋轉
當在ptr的左子樹的右子樹中插入一個結點后，造成了ptr平衡因子為-2的不平衡，將ptr向下找到當前結點的左孩子的右孩子，先進行左單旋ptr->left = subL，然后將ptr的右子樹斷開指向subR，此時便完成了旋轉，最后將平衡因子進行更新。
先右后左雙旋轉
先右單旋再左單旋，是先左后右的鏡像旋轉，這里就不做贅述了。
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對腳本之家的支持。如果你想了解更多相關內容請查看下面相關鏈接
相關文章
SpringCache常用注解及key中參數(shù)值為null問題解析
這篇文章主要介紹了SpringCache常用注解及key中參數(shù)值為null的問題解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-09-09
這篇文章主要介紹了SpringBoot2.1.4中的錯誤處理機制，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-10-10
基于Java中throw和throws的區(qū)別(詳解)
下面小編就為大家?guī)硪黄贘ava中throw和throws的區(qū)別(詳解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-07-07
這篇文章主要介紹了Java調用groovy實現(xiàn)原理代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-12-12
本篇文章給大家詳細講述了Java構造函數(shù)與普通函數(shù)用法以及相關知識點，對此有興趣的朋友可以參考學習下。2018-03-03
下面小編就為大家?guī)硪黄猯og4j.properties 配置(實例講解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08
Java數(shù)據(jù)結構之有向圖設計與實現(xiàn)詳解
有向圖是具有方向性的圖，由一組頂點和一組有方向的邊組成，每條方向的邊都連著一對有序的頂點。本文為大家介紹的是有向圖的設計與實現(xiàn)，需要的可以參考一下2022-11-11
下面小編就為大家?guī)硪黄贘ava中最常用的集合類框架之HashMap(詳解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-11-11
本文主要介紹了java中&與&&的區(qū)別，具有很好的參考價值。下面跟著小編一起來看下吧2017-03-03
Java使用HttpUtils實現(xiàn)發(fā)送HTTP請求
這篇文章主要介紹了Java使用HttpUtils實現(xiàn)發(fā)送HTTP請求,HTTP請求，在日常開發(fā)中，還是比較常見的，今天給大家分享HttpUtils如何使用,需要的朋友可以參考下2023-05-05