Javaで二分探索木(木構造)を実装する

基本情報技術者試験に向けてアルゴリズムを勉強しています。今回は木構造(二分探索木)についてまとめます。

木構造とは

木構造は以下のようにデータを格納したデータ構造です。

11102

木構造の用語

上記の図を参照しながら木構造の用語について説明します。

  • ノード(node、節):⑤などの○で囲まれた数字のことです。
    • 親ノード:②と④から見た③が親ノードです。
    • 子ノード:③から見た②と④が子ノードです。
    • 兄弟ノード:同じ親ノードを持つ②と④が兄弟ノードです。
    • 先祖ノード:②から見た③と⑤が先祖ノードです。
    • 子孫ノード:③から見た②と④と①が子孫ノードです。
    • ルートノード(根):⑤がルートノードです。親ノードを持たないノードのことです。
    • リーフノード(葉):①と④と⑥と⑨がリーフノードです。子ノードを持たないノードのことです。
  • エッジ(edge、枝):ノードとノードを繋ぐ線のことです。
  • 高さ:あるノードからリーフノードへ到達するためのエッジ数が高さです。
    (例えば、ルートノードである⑤のノードから①のノードに達するには、⑤→③→②→①とエッジを3つたどる必要があるので高さは3になります。)
  • 部分木:木構造の一部を取り出したもののことです。
    (例えば、⑧、⑥、⑨で構成される木は全体の木構造の部分木になります。)

木構造の種類

ここまでは1つのノードが最大2つの子ノードしか持たない木構造を見てきました。このような木構造を二分木と言います。

子ノードを3つ以上持つ木を多分木と言います。

61104

任意の数のノードを持てるようにすると扱いが複雑になるため、通常は子ノードの数を限定します。

また、高さに注目し、どの葉に到達する場合もできる限り等しいエッジ数になるようにした木を平衡木(へいこうぎ)と言います。平衡木はノードを追加するときや削除するときに高さが等しくなるように木の再構成が行われます。複雑になるので本記事では扱いません。

二分探索木

今回、本記事で主に扱うのが二分探索木です。

11102

実はこの木構造は適当に並べているのではなく、あるルールに基づいて並んでいます。各ノードは以下の制約に従って並んでいます。

左の子孫ノードの値 < 親ノードの値 <= 右の子孫ノードの値

つまり、「左の数値が小」、「真ん中(親ノード)の数値が中」、「右の数値が大」ということです。

このような制約を付けることにより、木構造からデータを探す際に効率的に探すことが可能になっています。
また、データを追加するときは制約を満たすようにどのノードの子ノードとするかを決定します。

実装する

今回、主に実装するのは以下の3つのメソッドです。

  • void add(int data):二分探索木への要素の追加
  • boolean contains(int data):二分探索木に要素があるかの探索
  • void remove(int data):二分探索木からの要素の削除

まずは、二分探索木のデータ構造を作ります。BinarySearchTreeクラスを作成し、以下の内容を記述してください。

class Node {
    int data;
    Node left;
    Node right;
}

public class BinarySearchTree {
    private Node root;
}

Nodeクラスが木構造の一つのノードを表します。子ノードを参照するためにleftとrightというフィールドを用意します。二分探索木の場合、子ノードは最大2つなので、通常left、rightと個別のフィールドとして定義します。なお、ノードに格納するデータは簡単にするためにint値とします。

BinarySearchTreeは二分木全体を表すクラスです。ルートノードを表すフィールドを定義します。

addメソッドを実装する(ノードの追加)

BinarySearchTreeクラスに以下のメソッドを追記してください。

public void add(int data) {
    // ツリーがない場合の特別処理
    if (root == null) {
        root = new Node();
        root.data = data;
        return;
    }

    // 現在ノードをルートノードとする
    Node current = root;
    while (true) {
        // 「追加する値 < 現在ノードの値」なら左の子を対象とする
        if (data < current.data) {
            // 次のノードが存在しない場合はその位置にデータを追加する
            if (current.left == null) {
                current.left = new Node();
                current.left.data = data;
                return;
            }
            // 存在する場合は次のノードを現在ノードとして繰り返す
            current = current.left;
        }
        // 「現在ノードの値 ≦ 追加する値」なら右の子を対象とする
        else if (current.data <= data) {
            if (current.right == null) {
                current.right = new Node();
                current.right.data = data;
                return;
            }
            current = current.right;
        }
    }
}

「ツリーがない場合の特別処理」として、1つもノードが無い場合は、ルートノードを作成します。

そして、「左の数値が小」、「真ん中(親ノード)の数値が中」、「右の数値が大」という法則に従って、ノードを追加すると、このようなアルゴリズムになります。

containsメソッドを実装する(ノードの探索)

BinarySearchTreeクラスに以下のメソッドを追記してください。

public boolean contains(int data) {
    // 現在ノードをルートノードとする
    Node current = root;
    // 次のノードが存在しない場合は探索終了
    while (current != null) {
        // 等しければ探索終了
        if (current.data == data) {
            return true;
        }
        // 「探索値 < 現在ノードの値」なら左の子に進む
         else if (data < current.data) {
            current = current.left;
        }
        // 「現在ノードの値 < 探索値」なら右の子に進む
         else if (current.data < data) {
            current = current.right;
        }
    }
    return false;
}

探索についてはそれほど難しくはありません。というのも探索は追加を行う際にすでに行っているからです。

動作確認

新たに動作確認用のクラスを作成し、mainメソッドに以下のように記述します。

public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();

    int[] data = {5, 3, 8, 2, 1, 4, 9, 6};
    for (int i = 0; i < data.length; i++) {
        tree.add(data[i]);
    }

    System.out.println(tree.contains(3));
    System.out.println(tree.contains(7));
}

動作結果:

true
false

二分探索木に格納されている3はtrue、格納されていない7はfalseと返されていることがわかります。

removeメソッドを実装する(ノードの削除)

データ削除は追加ほど単純ではありません。

11102-1

①を削除する場合、②を削除する場合、⑤を削除する場合を考えてみましょう。

  • ①を削除する場合(子ノードを持たない場合):①は子ノードを持ちません。この場合、①をそのまま削除してしまえばいいことになります。具体的には、②の左の子ノードの参照をなくします。

62301-1

  • ②を削除する場合(子ノードを1つ持つ場合):②は子ノードを1つだけ持ちます。この場合、子ノードを自分の位置に置き換えても二分探索木の制約は維持されます(左の子の場合も右の子の場合も削除対象の親ノードとの制約関係は維持されるからです)。処理としては、親ノードが削除対象の子ノードを参照するようにリンクを付け変えます。

62302-1

  • ⑤を削除する場合(子ノードを2つ持つ場合):⑤を削除する場合を考えます。⑤は子ノードを2つ持っています。この場合、右の部分木の最小のノード(今回は⑥)を削除対象に置き換えます。

62303-1

右部分木の最小ノードは削除対象を一度右に進んだ後、左の子を辿り続ければ取得できます。また、今回の場合は⑥は子ノードを持ちませんが、子ノードがある場合、それを⑧(置き換えようとするノードの親ノード)が参照するように付け変えが必要になります。⑥が子ノードとして⑦を持っている場合を考えてみてください。
※今回の場合、⑥は⑦以外の子ノードを持つことはできません。例えば、⑥が⑥未満の子ノードを持った時点で⑥はルートノードから見たときの右部分木の最小ノードではなくなるからです。

それでは、実際にremoveメソッドを実装します。BinarySearchTreeクラスに以下のメソッドを追記してください。ノードの接続を更新するために補助メソッドとしてupdateLinkメソッドも定義します。

public void remove(int data) {
    Node parent = null;
    Node current = root;
    while (current != null) {
        if (current.data == data) {
            if (current.left == null && current.right == null) {
                // 子ノードなし→ノードをそのまま削除(親ノードからの参照を外す)
                if (current == root) {
                    root = null;
                } else {
                    updateLink(parent, current, null);
                }
            } else if (current.left != null && current.right == null) {
                // 子ノードは左のみ→子ノードが親ノードに直接参照されるようにする
                if (current == root) {
                    root = root.left;
                } else {
                    updateLink(parent, current, current.left);
                }
            } else if (current.left == null && current.right != null) {
                // 子ノードは右のみ→子ノードが親ノードに直接参照されるようにする
                if (current == root) {
                    root = root.right;
                } else {
                    updateLink(parent, current, current.right);
                }
            } else {
                // 子ノードが2つの場合
    
                // まず削除対象ノードの右部分木の最小ノードを取得(左に進めば最小値が得られる)
                Node min_parent = current;
                Node min = current.right;
                while (min.left != null) {
                    min_parent = min;
                    min = min.left;
                }

                // 最小ノードの右ノードを最小ノードの親が直接参照するようにする
                // 削除対象がparentか(左に進んだか)で場合分けをする必要がある
                if (min_parent == current) {
                    min_parent.right = min.right;
                } else {
                    min_parent.left = min.right;
                }

                // 最小ノードを削除対象ノードに置き換える(削除対象ノードの左右の子を引き継ぐ)
                min.left = current.left;
                min.right = current.right;
                if (current == root) {
                    root = min;
                } else {
                    updateLink(parent, current, min);
                }
            }
            return;
        } else if (data < current.data) {
            parent = current;
            current = current.left;
        } else if (current.data < data) {
            parent = current;
            current = current.right;
        }
    }
}

private void updateLink(Node parent, Node target, Node replace) {
    if (parent.left == target) {
        parent.left = replace;
    } else if (parent.right == target) {
        parent.right = replace;
    }
}

かなり長いですが、個々の処理はそれほど難しくなく、上で検討した通りの記述になっています。

コメントだけでは読み解くのに苦労しそうな一部の処理について説明します。
子ノードが2つある場合の以下の処理は頭の中でイメージするのが少し難しいかもしれません。

Node min_parent = current;
Node min = current.right;
while (min.left != null) {
    min_parent = min;
    min = min.left;
}

// 最小ノードの右ノードを最小ノードの親が直接参照するようにする
// 削除対象がparentか(左に進んだか)で場合分けをする必要がある
if (min_parent == current) {
    min_parent.right = min.right;
} else {
    min_parent.left = min.right;
}

// 最小ノードを削除対象ノードに置き換える(削除対象ノードの左右の子を引き継ぐ)
min.left = current.left;
min.right = current.right;
if (current == root) {
    root = min;
} else {
    updateLink(parent, current, min);
}

まず、一度だけ右ノードに移動します。以下の処理です。

Node min_parent = current;
Node min = current.right;

続いて、上記処理の「移動後のノード(右ノード)」の左ノードを順々に辿りながら一番下のノードまで移動します。以下の処理です。

while (min.left != null) {
    min_parent = min;
    min = min.left;
}

続いて、min_parentcurrentを比較します。以下の処理です。

// 最小ノードの右ノードを最小ノードの親が直接参照するようにする
// 削除対象がparentか(左に進んだか)で場合分けをする必要がある
if (min_parent == current) {
    min_parent.right = min.right;
} else {
    min_parent.left = min.right;
}

これは削除対象のノードを置き換えるための事前準備です。ここでのmin_parentは上記のwhile文が走った(左ノードを辿った)場合と走らなかった(左ノードを辿らなかった)場合で、格納されるノードが異なります。

左ノードを辿らなかった場合は、min_parentcurrentは同じノードを指します。そして、minmin_parentの右ノードを指します。min_parent.rightmin.rightに置き換えます。以下の図を例に説明すると(左ノードを辿らなかった場合の説明なので、ここでは⑥の存在を無視してください)、⑤が削除対象の場合、⑧を⑨に置き換えるということです。

11102-1

左ノードを辿った場合は、min_parent.leftmin.rightに置き換えます。ここで注意したいのはminmin_parentの左ノードを指しているということです。以下の図を例に説明すると、⑤が削除対象の場合、⑥を⑦に置き換えるということです。

62101

最後に、「左ノードを辿らなかった場合の⑧」や「左ノードを辿った場合の⑥」を削除対象のノードと置き換えます。

// 最小ノードを削除対象ノードに置き換える(削除対象ノードの左右の子を引き継ぐ)
min.left = current.left;
min.right = current.right;
if (current == root) {
    root = min;
} else {
    updateLink(parent, current, min);
}

動作確認

新たに動作確認用のクラスを作成し、mainメソッドに以下のように記述します。

public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();
    int[] data = {5, 3, 8, 2, 1, 4, 9, 6};
    for (int i = 0; i < data.length; i++) {
        tree.add(data[i]);
    }

    System.out.println(tree.contains(5));
    tree.remove(5);
    System.out.println(tree.contains(5));
}

動作結果:

true
false

containsメソッドの結果から「5」が削除できていることがわかります。

二分探索木の走査

二分探索木の全ノードを処理することを考えましょう。全ノードを処理することを走査(traverse)と言います。

走査を行う方法としては、深さ優先探索と幅優先探索の2つがあります。

深さ優先探索とは

深さ優先探索はノードを処理する際に次のノードとして子ノードを処理対象とする走査方法です。子ノードがなくなった場合、親ノードに戻り、次の子ノードに処理を進めます。これを繰り返すことで全ノードについて処理を行います。

63101

(1) ルートノードの左の子である③のノードに進む
(2) ③のノードの左の子である②のノードに進む
(3) ②のノードの左の子である①のノードに進む
(4) ①のノードには子はいないので親である②のノードに戻る
(5) ②のノードに右の子はいないので親である③のノードに戻る
(6) ③のノードの右の子である④のノードに進む
(7) ④のノードには子はいないので親である③のノードに戻る

以降も同様に処理を繰り返すことにより全ノードを処理することができます。

深さ優先探索では、いつ処理を行うかで以下の3つの種類に分かれます。

  • 前順:初めてノードに到達したとき(子ノードに進む前)に処理を行います。
    ⑤→③→②→①→④→⑧→⑥→⑨の順に処理します。
  • 間順:左子ノードから戻ってきたときに処理を行います。
    ①→②→③→④→⑤→⑥→⑧→⑨の順に処理します。
  • 後順:左右の子ノードから戻ってきたときに処理を行います。
    ①→②→④→③→⑥→⑨→⑧→⑤の順に処理します。

11102-1

再帰処理

深さ優先探索はひとつのノードに注目すると以下のように記述できます。(前順の場合)

  1. ノードを処理する
  2. 左部分木(左の子ノード)について深さ優先探索を行う
  3. 右部分木(右の子ノード)について深さ優先探索を行う

2.と3.について、「深さ優先探索」について記述するのに「深さ優先探索」という言葉を使っています。このような定義にその言葉自身が出てくることを再帰的であると言います。

例えば、再帰の有名な例としてはフィボナッチ数列があります。これは木構造で再帰を表現するので木構造再帰(tree recursion)と呼ばれます。

フィボナッチ数列の定義:
$F_n = F_{n-1} + F_{n-2}$

$F_3$を計算するには$F_1$と$F_2$の足し算を行います。

簡単に言うと、1つ前の数字と2つ前の数字を足すと次の数字になるということです。数列は、 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584 …と続きます。

プログラミング言語では通常、あるメソッドを記述するのに自分自身を呼び出すということが可能です。これを再帰呼び出しと言います。

例えば、フィボナッチ数列を計算するメソッドは以下のように記述することができます。新しくクラスを作成し、以下を記述してください。

public static void main(String[] args) {
    int n = 5;
    int sum = fib(n);

    System.out.printf("Fibonacci fib: (%d) -> %d", n, sum);
}

static int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

このプログラムではフィボナッチ数列の5番目にあたる5というフィボナッチ数を求めます(配列と同じで0番目からカウントしています)。実行結果は以下です。

Fibonacci fib: (5) -> 5

今回の計算は以下のような木構造で表すことができます。図の矢印は計算する順番を表します。リーフノードにぶら下がっている"1"を合計した数が計算結果です。

fig105

しかし、この方法は代表的な木構造再帰として教育的ではありますが、あまりに冗長なので、フィボナッチ数の計算としては良い方法とは言えません。ここではあくまで再帰処理を紹介する目的で取り上げています。

データ構造やアルゴリズムの中には再帰的なもの(定義の中に自分自身が現れるもの)があります。なので、再帰の概念についてはよく理解しておいてください。

話を二分探索木に戻します。左部分木、右部分木を処理するために深さ優先探索を再利用していますが、木構造では子ノードを辿っていけばいずれリーフノード(部分木を持たない)に辿りつきます。そこまで行けばそれ以上進むことなく、親に戻るという処理が行われます。

inOrderメソッドを実装する(深さ優先探索)

実際に「間順」の深さ優先探索を行うinOrderメソッドを実装します。今回は処理として単純にノードの値を表示するという処理を行うことにします。

BinarySearchTreeクラスに以下のメソッドを追記してください。

public void inOrder() {
    inOrder(root);
    System.out.println();
}

private void inOrder(Node n) {
    if (n != null) {
        inOrder(n.left);
        System.out.print(n.data + ", ");
        inOrder(n.right);
    }
}

引数なしのinOrderメソッドはクラスの外から呼ばれるものでルートノードを起点として間順探索をスタートしています。引数ありのinOrderメソッドは間順探索の本体で再帰呼び出しを行うことで非常に簡単に深さ優先探索が記述できています。

具体的な動きを見てみましょう。⑤のノードを処理する順番を考えます。

11102-1

(1) inOrder(n.left)によって③に移動し、再帰呼び出しが行われます。
(2) inOrder(n.left)によって②に移動し、再帰呼び出しが行われます。
(3) inOrder(n.left)によって①に移動し、再帰呼び出しが行われます。
(4) inOrder(n.left)によって再帰呼び出しが行われますが、左ノードが無いので何も起こりません。
(5) System.out.print(n.data + ", ")によって、1,が出力されます。
(6) inOrder(n.right)によって再帰呼び出しが行われますが、右ノードが無いので何も起こりません。
(7) 処理が終わったので呼び出し元の②に移動し、System.out.print(n.data + ", ")によって、2,が出力されます。
(8) inOrder(n.right)によって再帰呼び出しが行われますが、右ノードが無いので何も起こりません。
(9) 処理が終わったので呼び出し元の③に移動し、System.out.print(n.data + ", ")によって、3,が出力されます。
(10) inOrder(n.right)によって④に移動し、再帰呼び出しが行われます。
(11) inOrder(n.left)によって再帰呼び出しが行われますが、左ノードが無いので何も起こりません。
(12) System.out.print(n.data + ", ")によって、4,が出力されます。
(13) inOrder(n.right)によって再帰呼び出しが行われますが、右ノードが無いので何も起こりません。
(14) 処理が終わったので呼び出し元の③に移動しますが、③の処理も終わっているので⑤に移動します。
(15) System.out.print(n.data + ", ")によって、5,が出力されます。
(16) inOrder(n.right)によって⑧に移動し、再帰呼び出しが行われます。
(17) inOrder(n.left)によって⑥に移動し、再帰呼び出しが行われます。
(18) inOrder(n.left)によって再帰呼び出しが行われますが、左ノードが無いので何も起こりません。

...

まだ処理は続きますが、動きは非常に単純です。

動作確認

新たに動作確認用のクラスを作成し、mainメソッドに以下のように記述します。

public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();
    int[] data = {5, 3, 8, 2, 1, 4, 9, 6};
    for (int i = 0; i < data.length; i++) {
        tree.add(data[i]);
    }

    tree.inOrder();
}

以下のような二分探索木が作成されます。

11102-1

動作結果:

1, 2, 3, 4, 5, 6, 8, 9,

幅優先探索とは

幅優先探索はノードを処理する際に次のノードとして兄弟ノードを処理対象とする走査方法です。兄弟ノードがなくなると各兄弟ノードの子ノードについて処理を行います。イメージとしては、同じ高さのノードについて先に処理をするという形になります。同じ高さのものについて先に探索を行うため、レベル順(level-order)とも呼ばれます。

63201

処理順序は次のようになります。

(1) ルートノードを処理する
(2) ルートノードは兄弟がいないのでルートノードの子ノードに進む。③のノードを処理する
(3) ③のノードの兄弟ノードの⑧のノードを処理する
(4) これ以上兄弟ノードがいないので③のノードの子ノードの②のノードを処理する
(5) ②のノードの兄弟ノードの④のノードを処理する

...

まだ処理は続きますが、動きは非常に単純です。

levelOrderメソッドを実装する(幅優先探索)

実際に幅優先探索を行うlevelOrderメソッドを実装します。処理内容は深さ優先探索の時と同様、単純にノードの値を表示するという処理を行うことにします。

BinarySearchTreeクラスに以下のメソッドを追記してください。また、ArrayDequeクラスについては適切にimportを行ってください。

public void levelOrder() {
    ArrayDeque<Node> queue = new ArrayDeque<Node>();
    // ルートノードをキューに入れる 
    if (root != null) {
        queue.offer(root);
    }
    // キューにノードがある間繰り返し
    while (queue.size() > 0) {
        // キューからノードを取り出し処理
        Node n = queue.poll();
        System.out.print(n.data + ", ");
        // ノードの子ノードをキューに加える 
        if (n.left != null) {
            queue.offer(n.left);
        }
        if (n.right != null) {
            queue.offer(n.right);
        }
    }
    System.out.println();
}

ArrayDequeクラスは両端キューとも呼ばれ、先頭末尾の双方から要素を出し入れできるキューの実装です。ArrayDequeクラスを利用することで、キュー(FIFO:First In First Out)やスタック(LIFO:Last In First Out)といったデータ構造を表現できます。offerメソッドでノードをキューへ格納、pollメソッドでキューからノードを取り出します。sizeメソッドではキューに格納されている要素数を返します。

簡単に説明すると、以下のような処理を行っています。

  1. ルートノードをキューに入れる。

63202

  1. キューからノードを取り出し処理を行う。
  2. ノードの子ノードをキューに加える。

63203

  1. キューにノードがあれば2.に戻る。なければ終了する。

63204

動作確認

新たに動作確認用のクラスを作成し、mainメソッドに以下のように記述します。

public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();
    int[] data = {5, 3, 8, 2, 1, 4, 9, 6};
    for (int i = 0; i < data.length; i++) {
        tree.add(data[i]);
    }

    tree.levelOrder();
}

以下のような二分探索木が作成されます。

11102-1

動作結果:

5, 3, 8, 2, 4, 6, 9, 1,

参考資料
スクールの教科書
計算機プログラムの構造と解釈 第二版