C++による平衡二分木(AVL木)の実装
前の記事でも書きましたが、趣味で下のgif画像のような平衡二分木(AVL木)を実装したので、それについての解説を書いていこうと思います。
コード全体は以下のレポジトリにあります。
二分木について
二分木とは、何らかの大小関係が定まっており、データに重複がないデータの保持に使われるデータ構造です。
定義としては、
- あるノードに着目すると、そのノードは左ノードと右ノードを持つ。(持たないことも可能)
- あるノードに着目すると、そのノードのデータは左ノードのデータよりも大きく、右ノードのデータより小さい。
です。具体的には下図のような木構造になります。
二分木の検索
二分木の検索は、上に述べた定義を使って行い、以下のような疑似コードになります。
注目ノード = 根ノード while(注目ノード != null){ if(注目ノード.データ == 検索するデータ){ return 検索成功 } if(検索するデータ < 注目ノード.データ){ 注目ノード = 注目ノード.左ノード }else{ 注目ノード = 注目ノード.右ノード } } return 検索失敗
このコードでは、根ノードからデータの大小に応じて左右のノードに注目していき、もし注目しているノードのデータが検索したデータと一致していたら検索成功、そうでないなら検索継続としています。そして、それ以上検索することができなかったら検索失敗とします。
二分木の挿入
二分木の挿入は、「そのノードがあるとしたらどの位置にあるのか」ということに着目して行い、以下のような疑似コードになります。
//searchParentは、引数のデータを持つノードがあると仮定し、そのノードの親ノードを返す。今は既にあるノードが挿入されることはないとします。 親ノード = searchParent(挿入するデータ) if(挿入するデータ < 親ノード.データ){ //newNodeは、引数のデータを持つノードを作って返す。 親ノード.左ノード = newNode(挿入するデータ) }else{ 親ノード.右ノード = newNode(挿入するデータ) }
二分木の削除
二分木の削除は、削除されるノードに部分木がある可能性があり、削除した後にそれらを適切に接続しないといけないので検索・挿入よりは複雑になります。
削除されるノードに左部分木がない場合
以下のように削除されるノードを右部分木で置き換えます。
削除されるノードに左部分木がある場合
以下のように削除されるノードのデータを、削除されるノードの左部分木の中で最大なノードのデータに置き換え、そのノードを削除します
以上をまとめると、以下のような疑似コードになります。
//searchNode関数は引数のデータを持つノードを返します。今は削除するデータがないことは考えません 削除されるノード = searchNode(削除するデータ) if(削除するノード.左ノード == ない){ //replace関数は第一引数で指定されたノードを第二引数で指定されたノードで置き換えます replace(削除するノード,削除するノード.右ノード) //delete関数は引数で指定されたノードを削除します delete(削除するノード) }else{ //leftMax関数は引数で指定されたノードの左部分木の中で最大なノードを返します。 左最大ノード = leftMax(削除するノード) 削除されるノード.データ = 左最大ノード.データ delete(左最大ノード) }
二分木の弱点
二分木はデータの検索、挿入、削除をlognオーダーで行うことができますが、この定義のまま実装すると、下のようなケースのときに最悪nオーダーになってしまいます。
- 単調増加するデータが挿入されたとき
- 0,1,-1,2,-2...とデータが挿入されたとき
以上のケースはどれも、あるノードの左右の部分木に偏りが生じてしまうことで起こります。
このようなケースでも性能を保つための工夫を施した実装が平衡二分木の一つであるAVL木です。
AVL木について
木の高さと偏りについて
この記事では部分木の高さを、
- その部分木の根ノードの左右の部分木の高さの最大値+1
- 左右の部分木がない場合、ない方の高さは0とする。
と定義します。
また、部分木の偏りを、
- その部分木の左右の部分木の高さの差(左が大きい時を正)
と定義します。
具体的には以下のようになります。
AVL木の定義
AVL木は以下のように定義されます。
- 木の中のどの部分木に着目しても、その部分木の偏りは -1,0,1のどれかである。
つまり、左のような二分木はAVL木でなく、右のような部分木はAVL木であるということです。
挿入、削除をしてもそれぞれのステップの最後にはAVL木になっている必要があるので、それぞれの操作の際には偏りを直す操作が必要になることがわかると思います。
回転
偏りを直すための操作の基本となるのが回転操作です。回転操作は、前後で二分木であることは維持しつつも、木の形を変える操作で、以下の4つが挙げられます。
左回転、右回転
以下の画像で、右向きの矢印が右回転、左向きの矢印が左回転です。
疑似コードは以下のようになります。
//右回転 bノード = aノード.左ノード Y = aノード.左ノード.右ノード 回転後のルート = bノード aノード.左ノード = Y if (Y != nullNode) { Y.親ノード = aノード } bノード.右ノード = aノード //Replace関数はaノードをルートとする部分木をbノードをルートとする部分木に置き換える Replace(aノード,bノード) aノード.親ノード = bノード return 回転後のルート
//左回転 aノード = bノード.右ノード Y = bノード.右ノード.左ノード 回転後のルート = aノード bノード.左ノード = Y if (Y != nullNode) { Y.親ノード = bノード } aノード.左ノード = bノード Replace(bノード,aノード) bノード.親ノード = aノード return 回転後のルート
左右二重回転
以下の画像が左右二重回転です。bノードに対して左回転を行った後、aノードに対して右回転を行います。
疑似コードは以下のようになります。
//左回転を行う関数 RotateL(aノード.左ノード) return RotateR(aノード)
右左二重回転
以下の画像が右左二重回転です。bノードに対して右回転を行った後、aノードに対して左回転を行います。
疑似コードは以下のようになります。
//右回転を行う関数 RotateL(aノード.右ノード) return RotateL(aノード)
平衡処理
AVL木の条件を常に満たすために、挿入・削除の度に以上の回転操作を使って、二分木の偏りをなくしていきます。 偏りが生じるケースはいくつかに分類され、そのそれぞれで行う回転操作が異なります。
挿入
左部分木の方から挿入された場合と、右部分木の方から挿入された場合では左右対称になっただけなので、ここでは左部分木の方から挿入された場合を考えます。
また、以下では注目するノードをu、uの左の子をv、vの右の子をwとします。
uの偏りが0になるとき
uをルートとする部分木の高さは挿入の前後で変わらないので、それ以上上のノードで平衡処理をする必要はないので、平衡処理を終了します。
uの偏りが1になるとき
uをルートとする部分木の高さは挿入の前後で1増えます。この部分木はAVL木の条件を満たしてはいますが、高さが増えたことにより、上の木でAVLでなくなる可能性があるので注目ノードをuの親ノードにして平衡処理を続けます。
uの偏りが2になるとき
vをルートとする部分木はAVL木であるため、vの偏りは-1,0,1のどれかですが、もし挿入後の偏りが0であったとすると、挿入によってvをルートとする部分木の高さは変わらず、uの偏りが2とならないため、この場合は除かれます。
よって、vの偏りが-1になったときと、1になったときに場合分けして考えます。
vの偏りが1になるとき
下図のAに挿入されたとき、条件より、B,Cはともに高さhです。右回転をして平衡処理をすると、全体として高さは変わらないので平衡処理を終了します。
vの偏りが-1になるとき
wの偏りによって以下の3つにわけられます。
wの偏りが1になるとき
下図のBに挿入されたとき、条件より、A,B,Dは高さh+1,Cは高さhです。左右回転をして平衡処理をすると、全体として高さは変わらないので平衡処理を終了します。
wの偏りが0になるとき
挿入されるノードがwのとき、左右回転をして平衡処理をすると、全体として高さは変わらないので平衡処理を終了します。
wの偏りが-1になるとき
下図のCに挿入されたとき、条件より、A,C,Dは高さh+1,Bは高さhです。左右回転をして平衡処理をすると、全体として高さは変わらないので平衡処理を終了します。
このように、vの偏りが-1のときは、結局左右回転をするので、uの偏りが2のときは二通りの処理になります。
削除
削除するとき上述のような方法で行えば、必ず削除されるのは葉ノードとなります。 また、削除をするということは、「削除した側の高さが1減る」、つまり「削除していない側の高さが1増える」ことであるので、挿入のときとは全く逆の操作をすればいいことになります。
以上をまとめると、挿入時の平衡処理の疑似コードは以下のようになります。
注目ノード = 挿入されたノード while (注目ノード.親ノード != nullNode) { 親ノード = 注目ノード.親ノード 親の高さ = 親ノード.高さ //左部分木に挿入されたとき if (親ノード.左ノード == 注目ノード) { //bias関数は引数ノードの偏りを返す if (bias(親ノード) == 2) { //Rotate系は回転して高さを更新し、回転後の部分木のルートノードを返す 親ノード = bias(親ノード.左ノード) >= 0 ? RotateR(親ノード) : RotateLR(親ノード) }else { //modHeight関数は引数ノードの高さを更新する modHeight(親ノード) } //右部分木に挿入されたとき }else { if (bias(親ノード) == -2) { 親ノード = bias(親ノード.右ノード) <= 0 ? RotateL(親ノード) : RotateRL(親ノード) }else { modHeight(親ノード) } } //挿入前後で部分木の高さが変わらないなら平衡処理終了 if (親の高さ == 親ノード.高さ) { break } //親ノードに注目して平衡処理を続ける 注目ノード = 親ノード }
また、削除時の疑似コードは以下のようになります。
//削除されるのは必ず葉ノード 注目ノード = 削除されたノードの親 while (注目ノード.親ノード != nullNode) { 親ノード = 注目ノード.親ノード 親の高さ = 親ノード.高さ //右部分木で削除されたとき if (親ノード.右ノード == 注目ノード) { //bias関数は引数ノードの偏りを返す if (bias(親ノード) == 2) { //Rotate系は回転して高さを更新し、回転後の部分木のルートノードを返す 親ノード = bias(親ノード.左ノード) >= 0 ? RotateR(親ノード) : RotateLR(親ノード) }else { //modHeight関数は引数ノードの高さを更新する modHeight(親ノード) } //左部分木で削除されたとき }else { if (bias(親ノード) == -2) { 親ノード = bias(親ノード.右ノード) <= 0 ? RotateL(親ノード) : RotateRL(親ノード) }else { modHeight(親ノード) } } //削除前後で部分木の高さが変わらないなら平衡処理終了 if (親の高さ == 親ノード.高さ) { break } //親ノードに注目して平衡処理を続ける 注目ノード = 親ノード }
このように挿入と削除はほとんど同じですが、「左部分木での挿入時の操作」=「右部分木での削除時の操作」(逆も然り)というところだけが違います。
実装
以上を踏まえると、以下のような実装となります。デストラクタにstd::queueを使っている以外は、全くライブラリを使っておらず、一から実装しきることができました。
工夫として、葉ノードの子をnullNodeという番兵ノードとしたことが挙げられます。このことにより、
- nullNodeは高さ0としているので、高さ・偏りの計算時にnullチェックをする必要がない
- Replaceした結果nullNodeになるときでも統一的に書ける
など好都合であるため、このようにしています。
