\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年1月21日 星期三

[ AVL Tree ] 優化AVL樹

AVL樹是以子樹的高度做為平衡的條件
其平衡條件為:
     左子樹的高度與右子樹的高度差不能超過1

因為每次的插入及刪除都有可能壞平衡,所以必須要進行旋轉來修正其平衡性。
共有4種旋轉方法,一序為 : 左左、左右、右右、右左,若想知道關於如何進行平衡的介紹請點擊這裡,其插入刪除常數較大,故其平均效率比Size Balanced Tree要差。

因為在網路上看到很多的AVL樹,其寫法都過於冗長,所以我這邊發一個AVL樹的模板,其code複雜度跟Size Balanced Tree差不多。
主要是將相同的平衡操作合併成一個balanced()函數,插入和刪除完後呼叫即可。

以下為模板:

沒有留言:

張貼留言