平衡二叉樹和二叉排序樹的關系
發布時間：2024-05-16 點擊：137
平衡二叉樹和二叉排序樹并沒有直接的關系，但是二叉排序樹的查找效率與二叉樹的形態有關，所有當我們希望二叉排序樹的形態是均勻的時候，這樣的二叉樹就被稱為平衡二叉樹。
1. 二叉排序樹
二叉排序樹（binary sort tree），又稱二叉查找樹（binary search tree），亦稱二叉搜索樹。
二叉排序樹定義：
二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
若左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；若右子樹不空，則右子樹上所有節點的值均大于它的根節點的值；左、右子樹也分別為二叉排序樹。
如圖下圖所示就是一棵二叉排序樹：
對二叉排序樹進行中序遍歷，便可得到一個按關鍵字排序的序列，如對上圖進行一次中序遍歷可得到一個有序序列：10，42，45，55，58，63，67，70，83，90，98
二叉排序樹的查找分析
就查找的平均時間性能而言，二叉排序樹上的查找與折半查找類似，但就維護表的有序性而言，二叉排序樹更高效，因為它無需移動節點，只需修改指針即可完成二叉排序樹的插入和刪除操作。
二叉排序樹查找在在最壞的情況下，需要的查找時間取決于樹的深度：
當二叉排序樹接近于滿二叉樹時，其深度為log2nlog_2nlog2n ,因此最壞情況下的查找時間為o(log2nlog_2nlog2n)，與折半查找是同數量級的。當二叉樹如下圖所示形成單枝樹時，其深度為n，最壞情況下查找時間為o(n)，與順序查找屬于同一數量級。
所以為了保證二叉排序樹查找有較高的查找速度，希望該二叉樹接近于滿二叉樹，或者二叉樹的每一個節點的左、右子樹深度盡量相等2. 平衡二叉樹
通過上面的分析可知，二叉排序樹的查找效率與二叉樹的形態有關，我們希望二叉排序樹的形態是均勻的，這樣的二叉樹稱為平衡二叉樹。
平衡二叉樹定義
平衡二叉樹（balanced binary tree），它是一棵空樹，或者是具有以下性質：它的左右兩個子樹的深度差的絕對值不超過1；它的左右兩個子樹也分別是平衡二叉樹。
將二叉樹節點的左子樹的深度減去它的右子樹的深度稱為平衡因子bf，則平衡二叉樹上所有節點的平衡因子只可能是-1、0和1，如下圖左邊的為平衡二叉樹，右邊的為非平衡二叉樹。
因為平衡二叉樹上任何節點的左、右子樹的深度之差都不會超過1，可以證明它的深度和n個節點的完全二叉樹的深度?log2n?\\\\lfloor log_2n \\\\rfloor?log2n? 1是同數量級的。因此，它的平均查找次數也是和?log2n?\\\\lfloor log_2n \\\\rfloor?log2n? 1同數量級的。
要構造一棵平衡二叉樹，georgii m. adelson-velskii 和 evgenii m. landis 提出了一種動態保持二叉平衡樹的方法，其基本思想是：在構造二叉排序樹的時候，每當插入一個節點時，先檢查是否因插入節點而破壞了樹的平衡性，如果是，則找出其中最小不平衡子樹，在保持排序樹的前提下，調整最小不平衡子樹中各節點之間的連接關系，以達到新的平衡，所以這樣的平衡二叉樹簡稱avl樹。其中最小平衡子樹是指：離插入節點最近，且平衡因子絕對值大于1的節點作為根節點的子樹。
調整最小不平衡子樹一般有四種情況：單向右旋(ll型)： 插入位置為左子樹的左子樹，以左子樹為軸心，進行單次向右旋轉，如下圖所示。節點旁邊的數字為該節點的平衡因子，i節點為當前插入節點(如果i節點處于正中，則表示i節點既可以是左孩子也可以是右孩子。
注意ll型，以中間節點為軸心進行旋轉。為什么這里i為bl左孩子不能將b-bl-i作為ll型，是因為a節點才是離i節點最近的平衡因子絕對值>1的子樹，其余節點的平衡因子絕對值都沒有超過1；同理當i為bl右孩子，也不能將b-bl-i作為lr型。
2. 單向左旋(rr型)： 插入位置為右子樹的右子樹，右子樹為軸心，進行單次向左旋轉
注意rr型，以中間節點為軸心進行旋轉。這里i為左右子樹并不影響其實rr型，原理同上。
3. 雙向旋轉先左后右(lr型)：插入位置為左子樹的右子樹，要進行兩次旋轉，先向左旋轉，再向右旋轉。
插入節點為左孩子：注意為什么不能b-c-i作為子樹將其定為rl型，原理同rr型中的解釋，對于lr型，，是以r端或者l靠近插入節點端作為旋轉軸心（如下圖相當于先旋轉以b為根的子樹后，成為了ll型，再旋轉以a為根的子樹）。
插入節點為右孩子：
4. 雙向旋轉先右后左(rl型)：插入位置為右子樹的左子樹，進行兩次調整，先右旋轉再左旋轉；處理情況與lr類似。
插入節點為左孩子：
插入節點為右孩子：
經過上面的我們可以發現，平衡因子與類型有很大的關系，需要以離插入節點最近且平衡因子絕對值>1的節點作為根節點的子樹進行判定是哪種類型。
練習
如下圖所示，先插入節點2后，成為ll型，然后整體右旋處理后平衡。
再依次插入8和6之后，節點5的平衡因子絕對值>1，成為rl型，所以先以5為根節點，將其子樹8-6右旋（成為rr型），然后將5為根節點的整棵樹再左旋。
繼續插入節點9后，節點4的平衡因子>1，成為rr型，所以以4為根節點，將整體左旋。
云服務器怎么部署web項目
我ssl證書怎么申請
香港云服務器租賃指南
申請短暫解封-虛擬主機/數據庫問題
加速云服務器推薦網站
5m帶寬的云服務器實際下載速度
阿里云云服務器ecs漏洞怎么修復
最好用的播放器排行 最全優質播放器合集
1. 二叉排序樹
二叉排序樹（binary sort tree），又稱二叉查找樹（binary search tree），亦稱二叉搜索樹。
二叉排序樹定義：
二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
若左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；若右子樹不空，則右子樹上所有節點的值均大于它的根節點的值；左、右子樹也分別為二叉排序樹。
如圖下圖所示就是一棵二叉排序樹：
對二叉排序樹進行中序遍歷，便可得到一個按關鍵字排序的序列，如對上圖進行一次中序遍歷可得到一個有序序列：10，42，45，55，58，63，67，70，83，90，98
二叉排序樹的查找分析
就查找的平均時間性能而言，二叉排序樹上的查找與折半查找類似，但就維護表的有序性而言，二叉排序樹更高效，因為它無需移動節點，只需修改指針即可完成二叉排序樹的插入和刪除操作。
二叉排序樹查找在在最壞的情況下，需要的查找時間取決于樹的深度：
當二叉排序樹接近于滿二叉樹時，其深度為log2nlog_2nlog2n ,因此最壞情況下的查找時間為o(log2nlog_2nlog2n)，與折半查找是同數量級的。當二叉樹如下圖所示形成單枝樹時，其深度為n，最壞情況下查找時間為o(n)，與順序查找屬于同一數量級。
所以為了保證二叉排序樹查找有較高的查找速度，希望該二叉樹接近于滿二叉樹，或者二叉樹的每一個節點的左、右子樹深度盡量相等2. 平衡二叉樹
通過上面的分析可知，二叉排序樹的查找效率與二叉樹的形態有關，我們希望二叉排序樹的形態是均勻的，這樣的二叉樹稱為平衡二叉樹。
平衡二叉樹定義
平衡二叉樹（balanced binary tree），它是一棵空樹，或者是具有以下性質：它的左右兩個子樹的深度差的絕對值不超過1；它的左右兩個子樹也分別是平衡二叉樹。
將二叉樹節點的左子樹的深度減去它的右子樹的深度稱為平衡因子bf，則平衡二叉樹上所有節點的平衡因子只可能是-1、0和1，如下圖左邊的為平衡二叉樹，右邊的為非平衡二叉樹。
因為平衡二叉樹上任何節點的左、右子樹的深度之差都不會超過1，可以證明它的深度和n個節點的完全二叉樹的深度?log2n?\\\\lfloor log_2n \\\\rfloor?log2n? 1是同數量級的。因此，它的平均查找次數也是和?log2n?\\\\lfloor log_2n \\\\rfloor?log2n? 1同數量級的。
要構造一棵平衡二叉樹，georgii m. adelson-velskii 和 evgenii m. landis 提出了一種動態保持二叉平衡樹的方法，其基本思想是：在構造二叉排序樹的時候，每當插入一個節點時，先檢查是否因插入節點而破壞了樹的平衡性，如果是，則找出其中最小不平衡子樹，在保持排序樹的前提下，調整最小不平衡子樹中各節點之間的連接關系，以達到新的平衡，所以這樣的平衡二叉樹簡稱avl樹。其中最小平衡子樹是指：離插入節點最近，且平衡因子絕對值大于1的節點作為根節點的子樹。
調整最小不平衡子樹一般有四種情況：單向右旋(ll型)： 插入位置為左子樹的左子樹，以左子樹為軸心，進行單次向右旋轉，如下圖所示。節點旁邊的數字為該節點的平衡因子，i節點為當前插入節點(如果i節點處于正中，則表示i節點既可以是左孩子也可以是右孩子。
注意ll型，以中間節點為軸心進行旋轉。為什么這里i為bl左孩子不能將b-bl-i作為ll型，是因為a節點才是離i節點最近的平衡因子絕對值>1的子樹，其余節點的平衡因子絕對值都沒有超過1；同理當i為bl右孩子，也不能將b-bl-i作為lr型。
2. 單向左旋(rr型)： 插入位置為右子樹的右子樹，右子樹為軸心，進行單次向左旋轉
注意rr型，以中間節點為軸心進行旋轉。這里i為左右子樹并不影響其實rr型，原理同上。
3. 雙向旋轉先左后右(lr型)：插入位置為左子樹的右子樹，要進行兩次旋轉，先向左旋轉，再向右旋轉。
插入節點為左孩子：注意為什么不能b-c-i作為子樹將其定為rl型，原理同rr型中的解釋，對于lr型，，是以r端或者l靠近插入節點端作為旋轉軸心（如下圖相當于先旋轉以b為根的子樹后，成為了ll型，再旋轉以a為根的子樹）。
插入節點為右孩子：
4. 雙向旋轉先右后左(rl型)：插入位置為右子樹的左子樹，進行兩次調整，先右旋轉再左旋轉；處理情況與lr類似。
插入節點為左孩子：
插入節點為右孩子：
經過上面的我們可以發現，平衡因子與類型有很大的關系，需要以離插入節點最近且平衡因子絕對值>1的節點作為根節點的子樹進行判定是哪種類型。
練習
如下圖所示，先插入節點2后，成為ll型，然后整體右旋處理后平衡。
再依次插入8和6之后，節點5的平衡因子絕對值>1，成為rl型，所以先以5為根節點，將其子樹8-6右旋（成為rr型），然后將5為根節點的整棵樹再左旋。
繼續插入節點9后，節點4的平衡因子>1，成為rr型，所以以4為根節點，將整體左旋。
云服務器怎么部署web項目
我ssl證書怎么申請
香港云服務器租賃指南
申請短暫解封-虛擬主機/數據庫問題
加速云服務器推薦網站
5m帶寬的云服務器實際下載速度
阿里云云服務器ecs漏洞怎么修復
最好用的播放器排行 最全優質播放器合集
上一篇：企業云盤和NAS，你如何選擇？
下一篇：怎么搭建服務器