Java でゼロから作る二分探索木

はじめに
二分探索ツリー (BST) は、各ノードが最大 2 つの子 (左の子と右の子と呼ばれます) を持つバイナリ ツリーの一種です。各ノードについて、左側のサブツリーにはノードの値より小さい値を持つノードのみが含まれ、右側のサブツリーにはノードの値より大きい値を持つノードのみが含まれます。 BST は、効率的な検索、挿入、削除操作に使用されます。

二分探索ツリーを使用する理由
BST にはいくつかの利点があります:

効率的な検索: 検索、挿入、削除の平均時間計算量は O(log n) です。
項目の動的セット: 静的配列とは異なり、動的操作をサポートします。
順序付けされた要素: BST を順番に走査すると、並べ替えられた順序で要素が得られます。
BST を構築するためのステップバイステップ ガイド
ステップ 1: ノード構造を定義する
最初のステップは、ツリー内のノードの構造を定義することです。各ノードには、値、左の子への参照、右の子への参照という 3 つの属性があります。

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

ステップ 2: コンストラクターを使用して BST クラスを作成する
次に、ツリーのルートへの参照と要素を挿入するメソッドを含む BST クラスを作成します。

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }
}

ステップ 3: 挿入メソッドを実装する
BST に要素を挿入するには、新しいノードの正しい位置を見つける必要があります。挿入メソッドは通常、再帰関数として実装されます。

public void insert(int value) {
    root = insertRec(root, value);
}

private TreeNode insertRec(TreeNode root, int value) {
    // Base case: if the tree is empty, return a new node
    if (root == null) {
        root = new TreeNode(value);
        return root;
    }

    // Otherwise, recur down the tree
    if (value < root.value) {
        root.left = insertRec(root.left, value);
    } else if (value > root.value) {
        root.right = insertRec(root.right, value);
    }

    // Return the (unchanged) node pointer
    return root;
}

視覚化
挿入がどのように機能するかをよりよく理解するために、例を考えてみましょう。次の数値シーケンスを BST に挿入するとします: 50、30、70、20、40、60、80。

50

  50
 /
30

  50
 /  \
30  70

50
 /  \
30  70
/

40 を挿入:

  50
 /  \
30  70
/ \

60 を挿入

  50
 /  \
30  70
/ \  /

80 を挿入:

  50
 /  \
30  70
/ \  / \

完全なコード
BST を作成して要素を挿入するための完全なコードは次のとおりです:

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value < root.value) {
            root.left = insertRec(root.left, value);
        } else if (value > root.value) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    // Additional methods for traversal, search, and delete can be added here

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int value : values) {
            bst.insert(value);
        }

        // Add code to print or traverse the tree
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

以上がJava でゼロから作る二分探索木の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。