平衡二叉樹和二叉排序樹之間有什么關(guān)系-創(chuàng)新互聯(lián)

創(chuàng)新互聯(lián)www.cdcxhl.cn八線動(dòng)態(tài)BGP香港云服務(wù)器提供商，新人活動(dòng)買多久送多久，劃算不套路！

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名與空間、虛擬空間、營銷軟件、網(wǎng)站建設(shè)、忻州網(wǎng)站維護(hù)、網(wǎng)站推廣。

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

平衡二叉樹和二叉排序樹并沒有直接的關(guān)系，但是二叉排序樹的查找效率與二叉樹的形態(tài)有關(guān)，所有當(dāng)我們希望二叉排序樹的形態(tài)是均勻的時(shí)候，這樣的二叉樹就被稱為平衡二叉樹。

1. 二叉排序樹

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

• 二叉排序樹定義：

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

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

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

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

• 二叉排序樹的查找分析

就查找的平均時(shí)間性能而言，二叉排序樹上的查找與折半查找類似，但就維護(hù)表的有序性而言，二叉排序樹更高效，因?yàn)樗鼰o需移動(dòng)節(jié)點(diǎn)，只需修改指針即可完成二叉排序樹的插入和刪除操作。

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

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

2. 平衡二叉樹

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

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

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

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

因?yàn)槠胶舛鏄渖先魏喂?jié)點(diǎn)的左、右子樹的深度之差都不會(huì)超過1，可以證明它的深度和n個(gè)節(jié)點(diǎn)的完全二叉樹的深度?log2n?+1是同數(shù)量級的。因此，它的平均查找次數(shù)也是和?log2n?+1同數(shù)量級的。

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

• 調(diào)整最小不平衡子樹一般有四種情況：

1. 單向右旋(LL型)： 插入位置為左子樹的左子樹，以左子樹為軸心，進(jìn)行單次向右旋轉(zhuǎn)，如下圖所示。節(jié)點(diǎn)旁邊的數(shù)字為該節(jié)點(diǎn)的平衡因子，I節(jié)點(diǎn)為當(dāng)前插入節(jié)點(diǎn)(如果I節(jié)點(diǎn)處于正中，則表示I節(jié)點(diǎn)既可以是左孩子也可以是右孩子。

注意LL型，以中間節(jié)點(diǎn)為軸心進(jìn)行旋轉(zhuǎn)。為什么這里I為BL左孩子不能將B-BL-I作為LL型，是因?yàn)锳節(jié)點(diǎn)才是離I節(jié)點(diǎn)最近的平衡因子絕對值>1的子樹，其余節(jié)點(diǎn)的平衡因子絕對值都沒有超過1；同理當(dāng)I為BL右孩子，也不能將B-BL-I作為LR型。

2. 單向左旋(RR型)： 插入位置為右子樹的右子樹，右子樹為軸心，進(jìn)行單次向左旋轉(zhuǎn)

注意RR型，以中間節(jié)點(diǎn)為軸心進(jìn)行旋轉(zhuǎn)。這里I為左右子樹并不影響其實(shí)RR型，原理同上。

3. 雙向旋轉(zhuǎn)先左后右(LR型)：插入位置為左子樹的右子樹，要進(jìn)行兩次旋轉(zhuǎn)，先向左旋轉(zhuǎn)，再向右旋轉(zhuǎn)。

插入節(jié)點(diǎn)為左孩子：注意為什么不能B-C-I作為子樹將其定為RL型，原理同RR型中的解釋，對于LR型，，是以R端或者L靠近插入節(jié)點(diǎn)端作為旋轉(zhuǎn)軸心（如下圖相當(dāng)于先旋轉(zhuǎn)以B為根的子樹后，成為了LL型，再旋轉(zhuǎn)以A為根的子樹）。

插入節(jié)點(diǎn)為右孩子：

4. 雙向旋轉(zhuǎn)先右后左(RL型)：插入位置為右子樹的左子樹，進(jìn)行兩次調(diào)整，先右旋轉(zhuǎn)再左旋轉(zhuǎn)；處理情況與LR類似。

插入節(jié)點(diǎn)為左孩子：

插入節(jié)點(diǎn)為右孩子：

經(jīng)過上面的我們可以發(fā)現(xiàn)，平衡因子與類型有很大的關(guān)系，需要以離插入節(jié)點(diǎn)最近且平衡因子絕對值>1的節(jié)點(diǎn)作為根節(jié)點(diǎn)的子樹進(jìn)行判定是哪種類型。

• 練習(xí)

如下圖所示，先插入節(jié)點(diǎn)2后，成為LL型，然后整體右旋處理后平衡。

再依次插入8和6之后，節(jié)點(diǎn)5的平衡因子絕對值>1，成為RL型，所以先以5為根節(jié)點(diǎn)，將其子樹8-6右旋（成為RR型），然后將5為根節(jié)點(diǎn)的整棵樹再左旋。

繼續(xù)插入節(jié)點(diǎn)9后，節(jié)點(diǎn)4的平衡因子>1，成為RR型，所以以4為根節(jié)點(diǎn)，將整體左旋。

undefined

以上就是平衡二叉樹和二叉排序樹之間有什么關(guān)系，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見到或用到的。希望你能通過這篇文章學(xué)到更多知識(shí)。更多詳情敬請關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道。

分享名稱：平衡二叉樹和二叉排序樹之間有什么關(guān)系-創(chuàng)新互聯(lián)
URL地址：http://muchs.cn/article36/csggpg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、小程序開發(fā)、做網(wǎng)站、商城網(wǎng)站、電子商務(wù)、全網(wǎng)營銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)