【概述】

二叉排序樹的查找效率取決于二叉排序樹的形態(tài)，而構(gòu)造一棵形態(tài)均勻的二叉排序樹與結(jié)點(diǎn)的插入次序有關(guān)，但結(jié)點(diǎn)的插入次序不是隨人的意志決定的，這就要求我們找到一種動(dòng)態(tài)平衡的方法，對(duì)于任意給定的關(guān)鍵碼序列都能構(gòu)造一科形態(tài)均勻、平衡的二叉排序樹。

平衡二叉樹（Balance Binary Tree）又稱 AVL 樹，其本質(zhì)是一種高度平衡的二叉排序樹，其或是一棵空的二叉排序樹，或是滿足以下性質(zhì)的二叉排序樹：

• 根結(jié)點(diǎn)的左子樹和右子樹深度最多相差 1
• 根結(jié)點(diǎn)的左子樹和右子樹也是平衡二叉樹

根據(jù)平衡二叉樹的定義，將某個(gè)結(jié)點(diǎn)的左子樹的深度與右子樹的深度之差稱為平衡因子（Balance Factor），將在平衡二叉樹構(gòu)造過(guò)程中，以距離插入結(jié)點(diǎn)最近的、且平衡因子絕對(duì)值大于 1 的結(jié)點(diǎn)為根的子樹稱為最小不平衡子樹（Minimal Unbalance SubTree）

【平衡二叉樹的構(gòu)造】

構(gòu)造平衡二叉樹的基本思想是：在構(gòu)造二叉排序樹的過(guò)程中，每插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否因結(jié)點(diǎn)插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹，在保持二叉排序樹的特性前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)的位置，進(jìn)行相應(yīng)旋轉(zhuǎn)，使其成為新的平衡子樹。

設(shè)結(jié)點(diǎn) A 為最小平衡樹的根結(jié)點(diǎn)，對(duì)該子樹進(jìn)行平衡調(diào)整歸納起來(lái)有以下四種情況：

1.LL 型

當(dāng)新插入的結(jié)點(diǎn)是插在結(jié)點(diǎn) A 的左孩子的左子樹上，即為 LL 型。

設(shè)結(jié)點(diǎn) B 是結(jié)點(diǎn) A 的左子樹的根結(jié)點(diǎn)，Bl、Br 分別為結(jié)點(diǎn) B 的左右子樹，Ar 為結(jié)點(diǎn) A 的右子樹，且 Bl、Br、Ar 三棵子樹的深度均為 h，將結(jié)點(diǎn) x 插入到結(jié)點(diǎn) B 的左子樹 Bl 上，導(dǎo)致結(jié)點(diǎn) A 的平衡因子由 1 變?yōu)?2，使得以結(jié)點(diǎn) A 為根的子樹失去了平衡，如下圖：

將支撐點(diǎn)由 A 改為 B，相應(yīng)的進(jìn)行順時(shí)針旋轉(zhuǎn)，旋轉(zhuǎn)后，結(jié)點(diǎn) A 及其右子樹 Ar 和結(jié)點(diǎn) B 的右子樹?Br 發(fā)生沖突，按旋轉(zhuǎn)優(yōu)先原則，結(jié)點(diǎn) A 成為 B 的右孩子結(jié)點(diǎn)，結(jié)點(diǎn) B 的右子樹 Br 成為結(jié)點(diǎn) A 的左子樹，如下圖：

2.RR 型

當(dāng)新插入的結(jié)點(diǎn)是插在結(jié)點(diǎn) A 的右孩子的右子樹上，即為 RR?型。

設(shè)結(jié)點(diǎn) B 是結(jié)點(diǎn) A 的右子樹的根結(jié)點(diǎn)，Bl、Br 分別為結(jié)點(diǎn) B 的左右子樹，Al?為結(jié)點(diǎn) A 的左子樹，且 Bl、Br、Ar 三棵子樹的深度均為 h，將結(jié)點(diǎn) x 插入到結(jié)點(diǎn) B 的右子樹 Br?上，導(dǎo)致結(jié)點(diǎn) A 的平衡因子由 -1?變?yōu)?-2，使得以結(jié)點(diǎn) A 為根的子樹失去了平衡，如下圖：

將支撐點(diǎn)由 A 改為 B，相應(yīng)的進(jìn)行逆時(shí)針旋轉(zhuǎn)，旋轉(zhuǎn)后，結(jié)點(diǎn) A 及其左子樹 Al?和結(jié)點(diǎn) B 的左子樹?Bl?發(fā)生沖突，按旋轉(zhuǎn)優(yōu)先原則，結(jié)點(diǎn) A 成為 B 的左孩子結(jié)點(diǎn)，結(jié)點(diǎn) B 的左子樹 Bl?成為結(jié)點(diǎn) A 的右子樹，如下圖：

3.LR 型

當(dāng)新插入的結(jié)點(diǎn)是插在結(jié)點(diǎn) A 的左孩子的右子樹上，即為 LR?型。

設(shè)結(jié)點(diǎn) B 是結(jié)點(diǎn) A 的左子樹的根結(jié)點(diǎn)，結(jié)點(diǎn) C 是結(jié)點(diǎn) B 的右子樹的根節(jié)點(diǎn)，Ar?為結(jié)點(diǎn) A 的右子樹，Bl?為結(jié)點(diǎn) B 的左子樹，Cl、Cr 分別為結(jié)點(diǎn) C 的左右子樹，且 Bl、Ar 兩棵子樹的深度為 h，Cl、Cr 兩棵子樹的深度為 h-1，將結(jié)點(diǎn) x 插入到結(jié)點(diǎn) C?的左子樹 Cl?上，導(dǎo)致結(jié)點(diǎn) A 的平衡因子由 1?變?yōu)?2，使得以結(jié)點(diǎn) A 為根的子樹失去了平衡，如下圖：

對(duì)于 LR 型，需旋轉(zhuǎn)兩次：

1）第一次旋轉(zhuǎn)：根節(jié)點(diǎn) A 不動(dòng)，調(diào)整結(jié)點(diǎn) A 的左子樹，將支撐點(diǎn)由結(jié)點(diǎn) B 調(diào)整到結(jié)點(diǎn) C 處，相應(yīng)的進(jìn)行逆時(shí)針旋轉(zhuǎn)，旋轉(zhuǎn)后，結(jié)點(diǎn) B 及其左子樹與結(jié)點(diǎn) C 的左子樹 Cl 發(fā)生沖突，按旋轉(zhuǎn)優(yōu)先原則，結(jié)點(diǎn) C 的左子樹成為 B 的右子樹，如下圖：

2）第二次旋轉(zhuǎn)：將支撐點(diǎn)由結(jié)點(diǎn) A 調(diào)整到結(jié)點(diǎn) C，?相應(yīng)的進(jìn)行順時(shí)針旋轉(zhuǎn)，旋轉(zhuǎn)后，結(jié)點(diǎn) A 及其右子樹 Ar 與結(jié)點(diǎn) C 的右子樹 Cr 發(fā)生沖突，按旋轉(zhuǎn)優(yōu)先原則，結(jié)點(diǎn) C 的右子樹成為結(jié)點(diǎn) A 的左子樹，如下圖：

4.RL 型

當(dāng)新插入的結(jié)點(diǎn)是插在結(jié)點(diǎn) A 的右孩子的左子樹上，即為 RL 型。

設(shè)結(jié)點(diǎn) B 是結(jié)點(diǎn) A 的右子樹的根結(jié)點(diǎn)，結(jié)點(diǎn) C 是結(jié)點(diǎn) B 的左子樹的根節(jié)點(diǎn)，Al?為結(jié)點(diǎn) A 的左子樹，Br?為結(jié)點(diǎn) B 的右子樹，Cl、Cr 分別為結(jié)點(diǎn) C 的左右子樹，且 Br、Al?兩棵子樹的深度為 h，Cl、Cr 兩棵子樹的深度為 h-1，將結(jié)點(diǎn) x 插入到結(jié)點(diǎn) C?的右子樹 Cr?上，導(dǎo)致結(jié)點(diǎn) A 的平衡因子由 -1?變?yōu)?-2，使得以結(jié)點(diǎn) A 為根的子樹失去了平衡，如下圖：

對(duì)于 RL 型，需旋轉(zhuǎn)兩次：

1）第一次旋轉(zhuǎn)：根節(jié)點(diǎn) A 不動(dòng)，調(diào)整結(jié)點(diǎn) A 的右子樹，將支撐點(diǎn)由結(jié)點(diǎn) B?調(diào)整到結(jié)點(diǎn) C 處，相應(yīng)的進(jìn)行順時(shí)針旋轉(zhuǎn)，旋轉(zhuǎn)后，結(jié)點(diǎn) B 及其右子樹與結(jié)點(diǎn) C 的右子樹 Cr?發(fā)生沖突，按旋轉(zhuǎn)優(yōu)先原則，結(jié)點(diǎn) C 的右子樹成為 B 的左子樹，如下圖：

2）第二次旋轉(zhuǎn)：將支撐點(diǎn)由結(jié)點(diǎn) A 調(diào)整到結(jié)點(diǎn) C，?相應(yīng)的進(jìn)行逆時(shí)針旋轉(zhuǎn)，旋轉(zhuǎn)后，結(jié)點(diǎn) A 及其左子樹 Al?與結(jié)點(diǎn) C 的左子樹 Cl?發(fā)生沖突，按旋轉(zhuǎn)優(yōu)先原則，結(jié)點(diǎn) C 的左子樹成為結(jié)點(diǎn) A 的右子樹，如下圖：

?

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的理论基础 —— 查找 —— 平衡二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。