AVL木の追加/削除後の調整の説明【平衡係数】

AVL木の追加/削除後の平衡係数による調整について、葉から説明するものがあまりなかったので、葉から説明するものを書く。

対象

AVL木の基本は知っている

注意

回転については説明しない。
削除前にノードを交換することについては説明しない。

追加

• 全部で0個の状態のところに1つ追加したらそれで終わり。
• 全部で1個以上あるなら、どれかを親として親の下に追加する。
  • 子を1つ持っていた親の下に2個目を追加したらその親は平衡係数が0。そこで終わり。
  • 子を持っていない親の下に追加したらその親は平衡係数が1(-1)。この場合、高さが増えたフラグを解消するまで(つまり平衡係数が2(-2)のものが上にある可能性が消えるまで)上に登って以下の確認と操作をする。
    • 平衡係数が0のものがあれば、操作対象部分の高さが増えたことによって0になった。このとき、そのノードを根とする部分木の高さは変わらないのでそこで終わり。
    • 平衡係数が1(-1)であれば、増えたことによって1(-1)になったので解消されておらず、さらに上に登る。
    • 平衡係数が2(-2)であれば、増えたことによって2(-2)になったので回転をする。するとその位置を根とする部分木の高さは追加前と変化なし。平衡係数は2(-2)から回転をして0になる。高さの変化なしなのでここで終わり。

削除

削除前に別のノードと交換することがある(二分探索木の性質)。

• 全部で1つの場合はそれを削除したら終わり。
• 全部で2個以上あるなら、ある親の下のものを削除する。削除するものが葉の場合、それを削除する。削除するものが子が1つ持つ場合は、削除してからその子を引き上げる。次に操作対象部分の高さが減ったフラグを解消するまで(つまり平衡係数が2(-2)のものが上にある可能性が消えるまで)以下の確認と操作をしながら上に登る。削除した場所の親から開始する。
  • 平衡係数が0のものがあれば、減ったことによって1(-1)から0になった。この場合、そのノードを根とする部分木の高さは減っている。さらに上へ。
  • 平衡係数が1(-1)のものがあれば、減ったことによって1(-1)になったのでそのノードを根とする部分木の高さは変わってないので終わり。
  • 平衡係数が2(-2)のものがあれば回転する。回転によってその位置を根とする部分木の高さは減っている。さらに上へ。