二分探索木の概念

二分探索木は、空の木または以下の性質を持つ二分木です。

• 左部分木が空でない場合、左部分木のすべてのノードの値は根ノードの値より小さい。
• 右部分木が空でない場合、右部分木のすべてのノードの値は根ノードの値より大きい。
• 左右の部分木もまた二分探索木である。

TreeSetやTreeMapは内部的に赤黒木（平衡二分探索木）を使用しており、中間順巡回の結果がソートされたリストとなります。これらの集合クラスに格納されるデータは必ず比較可能な型である必要があります。

int[] array = {5, 3, 4, 1, 7, 8, 2, 6, 0, 9};

ノードの定義

static class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

検索操作

public boolean search(int key) {
    TreeNode cur = root;
    while (cur != null) {
        if (key < cur.val) {
            cur = cur.left;
        } else if (key > cur.val) {
            cur = cur.right;
        } else {
            return true;
        }
    }
    return false;
}

挿入操作

public boolean insert(int val) {
    if (root == null) {
        root = new TreeNode(val);
        return true;
    }
    TreeNode cur = root;
    TreeNode parent = null;
    while (cur != null) {
        parent = cur;
        if (val < cur.val) {
            cur = cur.left;
        } else if (val > cur.val) {
            cur = cur.right;
        } else {
            return false;
        }
    }
    TreeNode newNode = new TreeNode(val);
    if (val < parent.val) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
    return true;
}

削除操作

削除操作は複雑であり、次の手順を踏みます。

private void removeNode(TreeNode cur, TreeNode parent) {
    if (cur.left == null) {
        replaceChild(parent, cur, cur.right);
    } else if (cur.right == null) {
        replaceChild(parent, cur, cur.left);
    } else {
        TreeNode successorParent = cur;
        TreeNode successor = cur.right;
        while (successor.left != null) {
            successorParent = successor;
            successor = successor.left;
        }
        cur.val = successor.val;
        removeNode(successor, successorParent);
    }
}

private void replaceChild(TreeNode parent, TreeNode oldChild, TreeNode newChild) {
    if (parent == null) {
        root = newChild;
    } else if (parent.left == oldChild) {
        parent.left = newChild;
    } else {
        parent.right = newChild;
    }
}

ハッシュ表の概念

ハッシュ表は、要素のキーとその保存位置の間に直接的な対応関係を持つ構造です。理想的な検索方法として、ハッシュ関数によって要素の保存位置を決定し、比較なしに素早く要素を見つけられるようにします。

ハッシュ衝突

異なるキーが同じハッシュアドレスを持つ現象を「ハッシュ衝突」と呼びます。これを避けるために、効果的なハッシュ関数の設計が必要です。

public class HashTable {

    static class Entry {
        public int key;
        public int value;
        public Entry next;

        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Entry[] buckets;
    private int size;

    public HashTable() {
        buckets = new Entry[16];
    }

    public void put(int key, int value) {
        int index = hash(key);
        Entry entry = buckets[index];
        while (entry != null) {
            if (entry.key == key) {
                entry.value = value;
                return;
            }
            entry = entry.next;
        }
        Entry newEntry = new Entry(key, value);
        newEntry.next = buckets[index];
        buckets[index] = newEntry;
        size++;
    }

    public int get(int key) {
        int index = hash(key);
        Entry entry = buckets[index];
        while (entry != null) {
            if (entry.key == key) {
                return entry.value;
            }
            entry = entry.next;
        }
        return -1;
    }

    private int hash(int key) {
        return Math.abs(key % buckets.length);
    }
}

Javaでの実装例

TreeMapの使用例

import java.util.Map;
import java.util.TreeMap;

public class Example {
    public static void testMap() {
        Map<String, String> map = new TreeMap<>();
        map.put("林冲", "豹子头");
        map.put("鲁智深", "花和尚");
        for (Map.Entry<String, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

HashSetの使用例

import java.util.HashSet;
import java.util.Set;

public class Example {
    public static void testSet() {
        Set<String> set = new HashSet<>();
        set.add("apple");
        set.add("banana");
        for (String s : set) {
            System.out.println(s);
        }
    }
}

性能分析

ハッシュ表の挿入、削除、検索の時間計算量は通常O(1)と見なされます。ただし、衝突が多い場合は性能が低下します。