php代碼實現平衡二叉樹詳解（平衡二叉樹實現的實例）

本文目錄一覽：

• 1、設計演算法統計二叉樹中平衡結點的個數
• 2、題目3． 平衡二叉樹演算法查找樹中某節點的時間複雜度是多少？
• 3、二叉排序樹的建立的過程中是如何實現平衡
• 4、平衡二叉樹為什麼叫AVL？

設計演算法統計二叉樹中平衡結點的個數

平衡二叉樹

：首先要求是一棵二叉排序樹，然後要求每個結點的平衡因子（左子樹高度減右子樹高度）在1，0，-1之間。

給定二叉樹根節點root, 編程判斷一個二叉樹是否為平衡二叉樹

演算法思路：按照某種遍歷規則遍歷二叉樹，在遍歷的過程中，檢查根是不是大於左子樹（不空時）的根而且小於右子樹（不空時）的根，並計算左右子樹高度之差是在在1，0，-1之間。如果所有結點都滿足這兩條件則為平衡二叉樹

題目3． 平衡二叉樹演算法查找樹中某節點的時間複雜度是多少？

平均查找的時間複雜度為O(log n)。

平衡樹的查找過程和排序樹的相同。在查找過程中和給定值進行比較關鍵字個數不超過樹的深度。

如果二叉樹的元素個數為n，那麼不管是對樹進行插入節點、查找、刪除節點都是log(n)次循環調用就可以了。它的時間複雜度相對於其他數據結構如數組等是最優的。

是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。常用演算法有紅黑樹、AVL、Treap、伸展樹等。

擴展資料：

二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：

(1)空二叉樹——(a)

(2)只有一個根結點的二叉樹——(b);

(3)右子樹為空的二叉樹——(c);

(4)左子樹為空的二叉樹——(d);

(5)完全二叉樹——(e)

注意：儘管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。

參考資料來源：百度百科-二叉樹演算法

二叉排序樹的建立的過程中是如何實現平衡

它或者是一棵空樹，或者是具有下列性質的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差之差的絕對值不超過1.。常用演算法有：紅黑樹、AVL樹、Treap等。平衡二叉樹的調整方法平衡二叉樹是在構造二叉排序樹的過程中，每當插入一個新結點時，首先檢查是否因插入新結點而破壞了二叉排序樹的平衡性，若是，則找出其中的最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關係，進行相應的旋轉，使之成為新的平衡子樹。具體步驟如下：⑴ 每當插入一個新結點，從該結點開始向上計算各結點的平衡因子，即計算該結點的祖先結點的平衡因子，若該結點的祖先結點的平衡因子的絕對值均不超過1，則平衡二叉樹沒有失去平衡，繼續插入結點；⑵ 若插入結點的某祖先結點的平衡因子的絕對值大於1，則找出其中最小不平衡子樹的根結點；⑶ 判斷新插入的結點與最小不平衡子樹的根結點的關係，確定是哪種類型的調整；⑷ 如果是LL型或RR型，只需應用扁擔原理旋轉一次，在旋轉過程中，如果出現衝突，應用旋轉優先原則調整衝突；如果是LR型或LR型，則需應用扁擔原理旋轉兩次，第一次最小不平衡子樹的根結點先不動，調整插入結點所在子樹，第二次再調整最小不平衡子樹，在旋轉過程中，如果出現衝突，應用旋轉優先原則調整衝突；

平衡二叉樹為什麼叫AVL？

平衡二叉樹(Balanced Binary Tree) 是二叉搜索樹（又名二叉查找樹排序二叉樹）的一種。在二叉搜索樹中，搜索、插入、刪除的複雜度都和書的高度相關，因此樹高是制約二叉搜索樹時間效率的最大瓶頸。理論上，任意高度為h二叉樹最多能容納2h − 1個元素，即h=O(lg n)。實際上，由於普通二叉樹的形態常常受操作順序的影響，各子樹左右兒子節點數目相差比較大，極端情況下，二叉樹蛻化成一條鏈，此時h=O(n)

平衡二叉樹通過一組平衡化旋轉規則，使得各個子樹的形態發生變化，從而使樹高趨近於lg n。

常見的平衡二叉樹有如下的幾種

AVL樹 其主要思想是維護樹高，使之平衡

紅黑樹 其主要思想是對節點染色，對不同顏色的節點採用不同的判斷，編程複雜度較高

AA樹 是紅黑樹的一種特例

伸展樹 有四種旋轉規則

Treap 其主要思想是對每個節點附加隨機權值，並根據權值維護為堆，因此被命名為Tree+Heap=Treap，其編程複雜度較低，性價比較高。

Size Balanced Tree 其主要思想為直接維護各子樹的節點個數，使之嚴格平衡。其論文由中國OIer廣東紀念中學的陳啟峰於2006年底完成，並在Winter Camp 2007中發表。