二分探索木パターン

中級

カテゴリ: binary-search

概要

二分探索木（BST: Binary Search Tree）は、各ノードが最大2つの子ノードを持ち、左の子孫の値がノードの値より小さく、右の子孫の値がノードの値より大きいという性質を持つ木構造です。この特性により、要素の検索、挿入、削除が平均的にO(log n)の時間で行えます。二分探索木は、順序付けられたデータを効率的に管理するための基本的なデータ構造であり、多くの高度なデータ構造（AVL木、赤黒木など）の基礎となっています。

コードテンプレート

Java

Python

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

- 二分探索木の基本実装
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val) {
        this.val = val;
    }
}

class BinarySearchTree {
    private TreeNode root;
    
    // 要素の検索
    public TreeNode search(int val) {
        return searchRecursive(root, val);
    }
    
    private TreeNode searchRecursive(TreeNode root, int val) {
        // 基底ケース: ルートがnullまたは値が見つかった場合
        if (root == null || root.val == val) {
            return root;
        }
        
        // 値がルートより小さい場合は左部分木を探索
        if (val < root.val) {
            return searchRecursive(root.left, val);
        }
        
        // 値がルートより大きい場合は右部分木を探索
        return searchRecursive(root.right, val);
    }
    
    // 要素の挿入
    public void insert(int val) {
        root = insertRecursive(root, val);
    }
    
    private TreeNode insertRecursive(TreeNode root, int val) {
        // 基底ケース: 空のノードに到達した場合、新しいノードを作成
        if (root == null) {
            return new TreeNode(val);
        }
        
        // 値がルートより小さい場合は左部分木に挿入
        if (val < root.val) {
            root.left = insertRecursive(root.left, val);
        }
        // 値がルートより大きい場合は右部分木に挿入
        else if (val > root.val) {
            root.right = insertRecursive(root.right, val);
        }
        // 値が既に存在する場合（重複を許可しない場合）
        
        return root;
    }
    
    // 要素の削除
    public void delete(int val) {
        root = deleteRecursive(root, val);
    }
    
    private TreeNode deleteRecursive(TreeNode root, int val) {
        // 基底ケース: 空の木
        if (root == null) {
            return null;
        }
        
        // 削除するノードを探す
        if (val < root.val) {
            root.left = deleteRecursive(root.left, val);
        } else if (val > root.val) {
            root.right = deleteRecursive(root.right, val);
        } else {
            // 削除するノードが見つかった場合
            
            // ケース1: 葉ノード（子を持たないノード）
            if (root.left == null && root.right == null) {
                return null;
            }
            
            // ケース2: 1つの子を持つノード
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
            
            // ケース3: 2つの子を持つノード
            // 右部分木の最小値（後継者）を見つける
            root.val = findMin(root.right).val;
            // 後継者を削除
            root.right = deleteRecursive(root.right, root.val);
        }
        
        return root;
    }
    
    // 部分木内の最小値を持つノードを見つける
    private TreeNode findMin(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }
    
    // 中順走査（昇順に要素を取得）
    public void inorder() {
        inorderRecursive(root);
    }
    
    private void inorderRecursive(TreeNode root) {
        if (root != null) {
            inorderRecursive(root.left);
            System.out.print(root.val + " ");
            inorderRecursive(root.right);
        }
    }
}

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

二分探索木BSTBinary Search Tree順序付き木検索木中順走査In-order Traversalバランス木AVL木赤黒木順序統計量

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
二分探索木の検証（Validate Binary Search Tree）: 与えられた木が有効な二分探索木かどうかを判定する
2
二分探索木の構築（Convert Sorted Array to Binary Search Tree）: ソート済み配列から高さバランスの取れた二分探索木を構築する
3
k番目に小さい要素（Kth Smallest Element in a BST）: 二分探索木内のk番目に小さい要素を見つける
4
最近共通祖先（Lowest Common Ancestor of a Binary Search Tree）: 2つのノードの最近共通祖先を見つける
5
二分探索木の範囲合計（Range Sum of BST）: 特定の範囲内の値を持つノードの合計を計算する

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

易

二分木の中順走査

二分木の根ノードが与えられたとき、その木の中順走査（inorder traversal）の結果を返してください。中順走査とは、左の子 → 自分自身 → 右の子の順に訪問する走査方法です。...

易

二分木の前順走査

二分木の根ノードが与えられたとき、その木の前順走査（preorder traversal）の結果を返してください。前順走査とは、自分自身 → 左の子 → 右の子の順に訪問する走査方法です。...

易

二分木の最大深さ

二分木の根ノードが与えられたとき、その木の最大深さを求めてください。二分木の最大深さとは、根ノードから最も遠い葉ノードまでの最長パスに沿ったノードの数です。 **注意**: 葉ノードとは、子を持...