二分探索木の実装

はじめに

この実験では、Java で二分探索木を実装する方法を学びます。二分探索木は、各ノードの値がその左部分木の値以上であり、その右部分木の値以下である二分木データ構造です。

Skills Graph

BSTNode クラスの作成

まず、二分探索木のノードを表す Java クラスを作成して BSTNode と呼びましょう。二分探索木のノードは値と 2 つの子ノードを持つ必要があります。1 つは左に、もう 1 つは右にあります。

class BSTNode {
    int value;
    BSTNode leftChild;
    BSTNode rightChild;

    BSTNode(int val) {
        this.value = val;
        this.leftChild = null;
        this.rightChild = null;
    }
}

二分探索木への要素の挿入

二分探索木に要素を挿入するには、以下のアルゴリズムに従います。

• 新しい値が現在のノードの値より小さい場合、左の子に再帰的に移動します。
• 新しい値が現在のノードの値より大きい場合、右の子に再帰的に移動します。
• 現在のノードが null の場合、この位置に新しい値を追加します。

public static BSTNode insert(int value, BSTNode current) {
    if (current == null) {
        BSTNode newNode = new BSTNode(value);
        return newNode;
    } else {
        if (value < current.value)
            current.leftChild = insert(value, current.leftChild);
        else
            current.rightChild = insert(value, current.rightChild);
    }
    return current;
}

このメソッドをテストするには、二分探索木を作成していくつかの要素を挿入します。

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // 挿入を確認するために木を出力します
    System.out.println("Traversal after insertion: ");
    inorderTraversal(root);
}

// 木を中順で巡回する関数
public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

出力:

Traversal after insertion:
5 7 9 12 20 21

二分探索木内の要素の検索

二分探索木内の要素を検索するには、以下のアルゴリズムに従います。

• 現在のノードの値が見つけようとしている値と一致する場合、true を返します。
• 現在のノードの値が見つけようとしている値より大きい場合、左の子に再帰的に移動します。
• 現在のノードの値が見つけようとしている値より小さい場合、右の子に再帰的に移動します。
• 現在のノードが null の場合、false を返します。

public static boolean search(int key, BSTNode current) {
    if (current == null)
        return false;
    if (current.value == key)
        return true;
    else {
        if (key < current.value)
            return search(key, current.leftChild);
        else
            return search(key, current.rightChild);
    }
}

このメソッドをテストするには、いくつかの要素を検索します。

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // 要素を検索する
    System.out.println(search(7, root));
    System.out.println(search(9, root));
    System.out.println(search(17, root));
}

出力:

true
true
false

二分探索木から要素の削除

二分探索木から要素を削除することは、以前のステップよりも少し複雑です。なぜなら、ノードの種類に応じてさまざまなケースを処理する必要があるからです。

• ノードが**子を持たない（葉ノード）**場合、単に削除します。
• ノードが子を 1 つだけ持つ場合、その子で置き換えます。
• ノードが子を 2 つ持つ場合、右部分木の最小値または左部分木の最大値で置き換えます。

public static BSTNode delete(int value, BSTNode current) {
    if (current == null)
        return current;
    if (value < current.value)
        current.leftChild = delete(value, current.leftChild);
    else if (value > current.value)
        current.rightChild = delete(value, current.rightChild);
    else if (value == current.value) {
        if (current.leftChild!= null && current.rightChild!= null) {
            int min = current.rightChild.value;
            BSTNode temp = current.rightChild;
            while (temp.leftChild!= null) {
                min = temp.leftChild.value;
                temp = temp.leftChild;
            }
            current.value = min;
            current.rightChild = delete(min, current.rightChild);
        } else if (current.leftChild == null)
            return current.rightChild;
        else if (current.rightChild == null)
            return current.leftChild;
    }
    return current;
}

このメソッドをテストするには、いくつかのノードを削除して木を出力します。

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // いくつかのノードを削除する
    root = delete(12, root);
    root = delete(20, root);
    root = delete(9, root);

    // 削除を確認するために木を出力する
    System.out.println("Traversal after deletion: ");
    inorderTraversal(root);
}

出力:

Traversal after deletion:
5 7 21

二分探索木の巡回

二分探索木をさまざまな方法で巡回できます。

• 中順巡回（左-根-右）
• 前順巡回（根-左-右）
• 後順巡回（左-右-根）
• 階層順巡回（幅優先探索）

public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

public static void preorderTraversal(BSTNode current) {
    if (current == null)
        return;
    System.out.print(current.value + " ");
    preorderTraversal(current.leftChild);
    preorderTraversal(current.rightChild);
}

public static void postorderTraversal(BSTNode current) {
    if (current == null)
        return;
    postorderTraversal(current.leftChild);
    postorderTraversal(current.rightChild);
    System.out.print(current.value + " ");
}

public static void levelOrderTraversal(BSTNode root) {
    Queue<BSTNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        BSTNode temp = queue.poll();
        System.out.print(temp.value + " ");
        if (temp.leftChild!= null)
            queue.add(temp.leftChild);
        if (temp.rightChild!= null)
            queue.add(temp.rightChild);
    }
}

これらのメソッドをテストするには、各巡回手法を使って木を出力します。

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    System.out.print("中順巡回: ");
    inorderTraversal(root);
    System.out.print("\n前順巡回: ");
    preorderTraversal(root);
    System.out.print("\n後順巡回: ");
    postorderTraversal(root);
    System.out.print("\n階層順巡回: ");
    levelOrderTraversal(root);
}

出力:

中順巡回: 5 7 9 12 20 21
前順巡回: 12 7 5 9 20 21
後順巡回: 5 9 7 21 20 12
階層順巡回: 12 7 20 5 9 21

まとめ

この実験では、Java で二分探索木を作成し、要素を挿入し、要素を検索し、要素を削除し、そして巡回する方法を学びました。

まず、二分探索木のノードを表す BSTNode クラスを作成しました。次に、二分探索木に固有のアルゴリズムを使用して挿入、検索、および削除機能を実装しました。最後に、中順、前順、後順、および階層順巡回などのさまざまな巡回手法を使用して二分探索木を巡回する方法を学びました。

これらの概念を使えば、自分自身の Java プログラムで二分探索木を実装できるようになるはずです。