長崎大学工学部 情報工学コース
平成27年度後期: データ構造とアルゴリズム (水曜日2校時)
追加資料
> 平衡木 (balanced tree)
  • 部分木 (subtree)
    • 二分木のあるノードと，そのノードからたどることのできるノードすべては， 全体の二分木よりも小さな木をつくります．これを，部分木といいます．
    • あるノードの，左の子ノードを根とする部分木を，左部分木， 右の子ノードを根とする部分木を，右部分木と言います．
  • 平衡木
    • あるノードについて，左部分木の高さと右部分木の高さが近いほど， そのノードを根とする木のバランスは良い，と言えます．
    • 二分木のあるノードについて，左部分木の高さから右部分木の高さを引いた値の絶対値を， そのノードでの平衡度と言うことにします．
      • (ノードの平衡度) = |(左部分木の高さ) - (右部分木の高さ)|
    • ノードの個数をn個として，すべてのノードの平衡度が O(logn) の木を，平衡木と呼びます．
    • 下図の二分木のうち，平衡木と言えるのは，どれでしょう？
  • 木の回転 (tree rotation)
    • 二分木では，データを追加したり削除するたびに，バランスが崩れます．
    • 二分木をバランス良く作り直す操作を，回転 (rotation) と言います．
  • 二分木の使いみち
    • 二分木は，たくさんのデータを，整列された状態で保持するために，使うことができます．
      • 例．どのノードの値も，左子ノードの値より大きく，かつ，右子ノードの値より小さい，等．
    • その場合，例えば「左子ノードには自分より小さいデータ，右子ノードには自分より大きなデータ」 というように，特定の条件が破られないように，ノードを追加したり削除します．
    • そのため，回転の操作をおこなうときも，その条件が破られないようにしなければいけません．
> 平衡木の回転
  • 右回転: 右のほうへ“重心をずらす”回転
    • あるノード v の，左部分木にあるノードは，すべて v より小さなデータを持っています．
    • よって，ノード v は，左部分木のどのノードであっても，自分の左子ノードにすることができます．
    • 逆に，ノード v の左子ノード vL から見ると，ノード v は自分より大きなデータを持っています．
    • よって，ノード vL は，ノード v を，自分の右子ノードにすることができます．
    • そこで，次の操作を行います．
      1. ノード v から，その左子ノード vL を切り離す．
      2. ノード vL の右子ノード vLR を切り離す．
      3. ノード vLR を，ノード v の新たな左子ノードにする．
      4. ノード vL の新たな右子ノードとして，元は親ノードだったノード v を，代わりにつなげる．




  • 左回転: 左のほうへ“重心をずらす”回転
    • あるノード v の，右部分木にあるノードは，すべて自分より大きなデータを持っています．
    • よって，ノード v は，右部分木のどのノードであっても，自分の右子ノードにすることができます．
    • 逆に，ノード v の右子ノード vR から見ると，ノード v は自分より小さなデータを持っています．
    • よって，ノード vR は，ノード v を，自分の左子ノードにすることができます．
    • そこで，次の操作を行います．
      1. ノード v から，その右子ノード vR を切り離す．
      2. ノード vR の左子ノード vRL を切り離す．
      3. ノード vRL を，ノード v の新たな右子ノードにする．
      4. ノード vR の新たな左子ノードとして，元は親ノードだったノード v を，代わりにつなげる．




  • 回転の効果
    • 右回転を行うことで，左の部分木の高さを減らすことができます．
    • 左回転を行うことで，右の部分木の高さを減らすことができます．
  • 回転の使い方
    • 二分木にデータを追加したり削除するたびに，どちらかの回転操作をおこなえば， 二分木のバランスを完全に維持できます．(AVL木)
    • しかし，一部のノードにだけアクセスが集中すると予想される場合は， 回転の操作を，二分木のバランスを完全に維持するためではなく， アクセスがあったノードをルートの位置に持ってくるために使うほうが， その時点以降の時間計算量を，より多く減らすことができます．(スプレー木)
[戻る]