平衡二叉樹和二叉排序樹之間有什么關系

本篇文章給大家分享的是有關平衡二叉樹和二叉排序樹之間有什么關系，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

平衡二叉樹和二叉排序樹并沒有直接的關系，但是二叉排序樹的查找效率與二叉樹的形態有關，所有當我們希望二叉排序樹的形態是均勻的時候，這樣的二叉樹就被稱為平衡二叉樹。

1. 二叉排序樹

二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。

• 二叉排序樹定義：

二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：

1. 若左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；
2. 若右子樹不空，則右子樹上所有節點的值均大于它的根節點的值；
3. 左、右子樹也分別為二叉排序樹。

如圖下圖所示就是一棵二叉排序樹：

對二叉排序樹進行中序遍歷，便可得到一個按關鍵字排序的序列，如對上圖進行一次中序遍歷可得到一個有序序列：10，42，45，55，58，63，67，70，83，90，98

• 二叉排序樹的查找分析

就查找的平均時間性能而言，二叉排序樹上的查找與折半查找類似，但就維護表的有序性而言，二叉排序樹更高效，因為它無需移動節點，只需修改指針即可完成二叉排序樹的插入和刪除操作。

二叉排序樹查找在在最壞的情況下，需要的查找時間取決于樹的深度：

1. 當二叉排序樹接近于滿二叉樹時，其深度為log2n ,因此最壞情況下的查找時間為O(log2n)，與折半查找是同數量級的。
2. 當二叉樹如下圖所示形成單枝樹時，其深度為n，最壞情況下查找時間為O(n)，與順序查找屬于同一數量級。
   
   所以為了保證二叉排序樹查找有較高的查找速度，希望該二叉樹接近于滿二叉樹，或者二叉樹的每一個節點的左、右子樹深度盡量相等

2. 平衡二叉樹

通過上面的分析可知，二叉排序樹的查找效率與二叉樹的形態有關，我們希望二叉排序樹的形態是均勻的，這樣的二叉樹稱為平衡二叉樹。

• 平衡二叉樹定義
  平衡二叉樹（Balanced Binary Tree），它是一棵空樹，或者是具有以下性質：

1. 它的左右兩個子樹的深度差的絕對值不超過1；
2. 它的左右兩個子樹也分別是平衡二叉樹。

將二叉樹節點的左子樹的深度減去它的右子樹的深度稱為平衡因子BF，則平衡二叉樹上所有節點的平衡因子只可能是-1、0和1，如下圖左邊的為平衡二叉樹，右邊的為非平衡二叉樹。

因為平衡二叉樹上任何節點的左、右子樹的深度之差都不會超過1，可以證明它的深度和n個節點的完全二叉樹的深度?log2n?+1是同數量級的。因此，它的平均查找次數也是和?log2n?+1同數量級的。

要構造一棵平衡二叉樹，Georgii M. Adelson-Velskii 和 Evgenii M. Landis 提出了一種動態保持二叉平衡樹的方法，其基本思想是：在構造二叉排序樹的時候，每當插入一個節點時，先檢查是否因插入節點而破壞了樹的平衡性，如果是，則找出其中最小不平衡子樹，在保持排序樹的前提下，調整最小不平衡子樹中各節點之間的連接關系，以達到新的平衡，所以這樣的平衡二叉樹簡稱AVL樹。其中最小平衡子樹是指：離插入節點最近，且平衡因子絕對值大于1的節點作為根節點的子樹。

• 調整最小不平衡子樹一般有四種情況：

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為根節點，將整體左旋。

undefined

以上就是平衡二叉樹和二叉排序樹之間有什么關系，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。