AVL木の平衡原理

目的地が設定できる手帳のような使い心地のTODOアプリを公開しています。

スポンサードリンク

どのノードから見ても左右の子ノードの深さの差が1以内のツリー構造を指す。以下はAVL木を保つ為の考え方。

例えばこんなbinary treeがあった場合、ノード10から子孫ノードを辿った場合、子孫の高さが2階層以上の差があることになる。

     10
   5    15
 2  6       // +1階層
1           // + 2階層

2階層以上の差がある場合、以下の手順でtreeを平衡させ、1階層差以内に収める。

1 子孫の階層が多い方の子ノードを持ち上げる。

     5
   2 6 10
 1       15

2 持ち上げただけでは、ノード5に3つの子[2, 6, 10]がいるように見えるので、真ん中のノード6を自分のノードの変わりに右子孫ノードのleftに付けてあげればよい。

     5
   2   10
 1    6  15

これでtreeの高さが平衡になる。

イマイチ理解できてないけど多分こういうことかな...。

     10
   4     15
 2   7      17
1   6 8   
   5

1 基本的に端を深くしておく。

      10
    7      15
  4   8      17
 2 6    
1   5

2 まだ2階層差があるので浅いノードを深くする。

      7
   4      10
  2 6    8  15
 1   5       17

間違ってるかも。

リンク