平衡樹的介紹
平衡樹的介紹
平衡二叉樹（Balanced Binary Tree）具有以下性質(zhì)百科：它是一 棵空樹或它的左右兩個(gè)子樹的高度差的***不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。構(gòu)造與調(diào)整方法 平衡二叉樹的常用算法有紅黑樹、AVL、Treap等。
最小二叉平衡樹的節(jié)點(diǎn)的公式如下 F(n)=F(n-1)+F(n-2)+1 這個(gè)類似于一個(gè)遞歸的數(shù)列，可以參考Fibonacci數(shù)列，1是根節(jié)點(diǎn)，F(xiàn)(n-1)是左子樹的節(jié)點(diǎn)數(shù)量，F(xiàn)(n-2)是右子樹的節(jié)點(diǎn)數(shù)量。
平衡二叉樹是二叉排序樹嗎?
平衡二叉樹不是二叉排序樹。
平衡樹（Balance Tree，BT)指的是，任意節(jié)點(diǎn)的子樹的高度差都小于等于1。
常見的符合平衡樹的有，B樹（多路平衡搜索樹）、AVL樹（二叉平衡搜索樹）等。
平衡樹可以完成**的一系列操作，?時(shí)間復(fù)雜度和空間復(fù)雜度相對(duì)于“2-3樹”要低，在完成**的一系列操作中始終保持平衡，為大型數(shù)據(jù)庫的組織、索引提供了一條新的途徑。
應(yīng)用
在智能電網(wǎng)中，與傳統(tǒng)路由協(xié)議不同，突發(fā)性擁塞不再是數(shù)據(jù)采集的主要風(fēng)險(xiǎn)，風(fēng)險(xiǎn)的新來源是數(shù)據(jù)流過度集中在**的關(guān)鍵節(jié)點(diǎn)而導(dǎo)致的擁塞。
為此，提出了一種能夠?qū)崿F(xiàn)數(shù)據(jù)平衡的數(shù)據(jù)采集路由機(jī)制用以克服**擁塞。該機(jī)制抽象出配用通信**的數(shù)學(xué)模型。
平衡二叉樹是什么？
平衡二叉樹（AVL）
那對(duì)圖 1 進(jìn)行下改造，把數(shù)據(jù)重新節(jié)點(diǎn)重新連接下，圖 2 如下：
圖 2 可以看到以下特性：
1. 所有左子樹的節(jié)點(diǎn)都小于其對(duì)應(yīng)的父節(jié)點(diǎn)（4，5，6）<（7）;（4）<（5）;（8）< （9）;
2. 所有右子樹上的節(jié)點(diǎn)都大于其對(duì)應(yīng)的父節(jié)點(diǎn)（8，9，10）>（7）;（6）>（5）;（10）>（9）;
3. 每個(gè)節(jié)點(diǎn)的平衡因子差值*** <=1;
4. 每個(gè)節(jié)點(diǎn)都符合以上三個(gè)特征。
滿足這樣條件的樹叫平衡二叉樹（AVL）樹。
問：那再次查找節(jié)點(diǎn) 5，需要遍歷多少次呢？
由于數(shù)據(jù)是按照順序組織的，那查找起來非常快，從上往下找：7-5，只需要在左子樹上查找，也就是遍歷 2 次就找到了 5。
假設(shè)要找到葉子節(jié)點(diǎn) 10，只需要在右子樹上查找，那也最多需要 3 次，7-9-10。也就說 AVL 樹在查找方面性能很好，最壞的情況是找到一個(gè)節(jié)點(diǎn)需要消耗的次數(shù)也就是樹的層數(shù)， 復(fù)雜度為 O(logN)
如果節(jié)點(diǎn)非常多呢？假設(shè)現(xiàn)在有 31 個(gè)節(jié)點(diǎn)，用 AVL 樹表示如圖 3：
圖 3 是一棵高度為 4 的 AVL 樹，有 5 層共 31 個(gè)節(jié)點(diǎn)，橙色是 ROOT 節(jié)點(diǎn)，藍(lán)色是葉子節(jié)點(diǎn)。對(duì) AVL 樹的查找來看起來已經(jīng)很完美了，能不能再優(yōu)化下？比如，能否把這個(gè)節(jié)點(diǎn)里存放的 KEY 增加？能否減少樹的總層數(shù)？那減少縱深只能從橫向來想辦法，這時(shí)候可以考慮用多叉樹。
