AVL樹是以子樹的高度做為平衡的條件
其平衡條件為:
左子樹的高度與右子樹的高度差不能超過1
因為每次的插入及刪除都有可能壞平衡，所以必須要進行旋轉來修正其平衡性。
共有4種旋轉方法，一序為 : 左左、左右、右右、右左，若想知道關於如何進行平衡的介紹請點擊這裡，其插入刪除常數較大，故其平均效率比Size Balanced Tree要差。
因為在網路上看到很多的AVL樹，其寫法都過於冗長，所以我這邊發一個AVL樹的模板，其code複雜度跟Size Balanced Tree差不多。
主要是將相同的平衡操作合併成一個balanced()函數，插入和刪除完後呼叫即可。
以下為模板:
沒有留言:
張貼留言