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