什么叫理想平衡二叉樹 平衡二叉樹是不是必須左小右大
平衡二叉樹怎么理解??？平衡二叉樹定義，什么是“理想平衡二叉樹？平衡二叉樹是什么？能通俗地說一下并舉例子嗎？什么叫做平衡二叉樹？平衡二叉樹是什么？
本文導航
二叉樹深度是怎么算的
這要涉及到滿二叉樹與完全二叉樹的問題
滿二叉樹是將一個n層二叉樹完全排滿的二叉樹，第n層有2^n個元素；
n層完全二叉樹是將n層滿二叉樹最后一層從后向前依次去處少于2^n個元素；
完全二叉樹是平衡二叉樹的一個特例，平衡二叉樹是將完全二叉樹的最后一層元素任意排在空位上的一種二叉樹。
如下圖所示，左為滿二叉樹，右為完全二叉樹：
平衡二叉樹的調(diào)整方法
所謂平衡二叉樹是指樹中任一結點的左、右子樹高度大致相同。平衡二叉樹有很多種最著名的是由前蘇聯(lián)數(shù)學家Adelse—Velskil和Landis在1962年提出的，稱為AVL樹。平衡二叉樹(AVL樹)定義如下：平衡二叉樹或者是一棵空樹，或者是具有以下性質(zhì)的二叉排序樹：(1)它的左子樹和右子樹的高度之差絕對值不超過1；(2)它的左子樹和右子樹都是平衡二叉樹。
平衡二叉樹構建圖解
理想二叉樹是一種特殊的滿二叉樹，其所有葉結點均在同一高度或者同一深度，也即一棵深度(高度)為h且有 2^h-1個結點的二叉樹。
如何構造平衡二叉樹
簡單說就是平衡二叉排序樹，也就是首先是二叉排序樹，然后還是平衡的?？梢赃@樣理解
它要么是一 棵空樹，要么是它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹
平衡二叉樹構造方法
這要涉及到滿二叉樹與完全二叉樹的問題
滿二叉樹是將一個n層二叉樹完全排滿的二叉樹，第n層有2^n個元素；
n層完全二叉樹是將n層滿二叉樹最后一層從后向前依次去處少于2^n個元素；
完全二叉樹是平衡二叉樹的一個特例，平衡二叉樹是將完全二叉樹的最后一層元素任意排在空位上的一種二叉樹。
如下圖所示，左為滿二叉樹，右為完全二叉樹：
平衡二叉樹是不是必須左小右大
平衡二叉樹（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ù)？那減少縱深只能從橫向來想辦法，這時候可以考慮用多叉樹。
