public class BinarySearchTree {

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

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

    public TreeNode root;

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

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

    public void removeVal(int val) {
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (val < cur.val) {
                parent = cur;
                cur = cur.left;
            } else if (val > cur.val) {
                parent = cur;
                cur = cur.right;
            } else {
                removeNode(parent, cur);
                return;
            }
        }
    }

    private void removeNode(TreeNode parent, TreeNode cur) {
        if (cur.left == null) {
            if (cur == root) {
                root = root.right;
            }
            if (cur == parent.left) {
                parent.left = cur.right;
            }
            if (cur == parent.right) {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            }
            if (cur == parent.left) {
                parent.left = cur.left;
            }
            if (cur == parent.right) {
                parent.right = cur.left;
            }
        } else { // 替换法
            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            // 替换值
            cur.val = target.val;
            // 删除
            if (target == targetParent.right) {
                targetParent.right = target.right;
            } else {
                targetParent.left = target.right;
            }
        }
    }
}

import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class Test {

    public static void main(String[] args) {

        Map<String, Integer> map = new TreeMap<>(); // TreeMap的创建

        map.put("Hello", 5); // 比较 key
        map.put("Halo", 6);
        map.put("Meat", 10);

        int val1 = map.get("Meat");
        System.out.println(val1); // 返回 key 所对应的 value
        System.out.println(map.getOrDefault("Halo", 666)); // 返回 key 所对应的 value，不存在返回默认值

        map.remove("Meat"); // 删除 key 对应的映射关系

        Set<String> set = map.keySet(); // 返回所有 key 的不重复集合
        System.out.println(set);

        Collection<Integer> collection = map.values(); // 返回所有 value 的重复集合
        System.out.println(collection);

        Set<Map.Entry<String, Integer>> entries = map.entrySet(); // 返回所有 key-value的映射关系
        for (Map.Entry<String, Integer> entry : entries ) {
            String key = entry.getKey();
            Integer val = entry.getValue();
            System.out.println("Key:" + key + " " + "val:" + val);
        }

        System.out.println(map.containsKey("hello")); // 判断是否包含 key
        System.out.println(map.containsValue(5)); // 判断是否包含 value
    }
}

import java.util.*;

public class Test {

    public static void main(String[] args) {
        Set<String> strings = new TreeSet<>();
        strings.add("Hello"); // 添加元素，重复元素不会添加
        strings.add("Meat");
        System.out.println(strings);
        System.out.println(strings.size()); // 返回集合大小
        System.out.println(strings.contains("Hello")); // 判断是否包含指定元素
        System.out.println(strings.isEmpty()); // 返回集合是否为空
        strings.clear(); // 清空集合
    }
}

public class MyHashBuck {
    static class node {
        public int key;
        public int val;
        public node next;

        public node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public node[] array;
    public int usedSize;
    public double load_factor = 0.75;

    public MyHashBuck() {
        this.array =  new node[10];
    }

    public void put(int key, int val) {
        int index = key % 10;
        node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        node newNode = new node(key, val);
        newNode.next = array[index];
        array[index] = newNode;
        this.usedSize++;
        if (doFactor(usedSize) > load_factor) {
            grow();
        }

    }

    public int get(int key) {
        int index = key % array.length;
        node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    private void grow() {
        node[] newArray = new node[2 * array.length];
        for (int i = 0; i < newArray.length; i++) {
            node cur = array[i];
            while (cur != null) {
                int newIndex = cur.key % newArray.length;
                node curNext = cur.next;
                cur.next = array[newIndex];
                array[newIndex] = cur;
                cur = curNext;
            }
        }
        this.array = newArray;
    }

    private double doFactor(int usedSize) {
        return usedSize * 1.0 / array.length;
    }

}