二叉搜索树（BST），哈希表讲解及Java实现_在具有n个结点的bst中查找数据元素

public boolean contains(int val) {
    return contains(root, val);
}
 
 
/**
* 判断当前以root为根的BST中是否包含了val
*
* @param root
* @param val
* @return
*/
private boolean contains(TreeNode root, int val) {
    if (root == null) {
        return false;
    }
    if (root.val == val) {
        return true;
    } else if (val > root.val) {
        return contains(root.right, val);
    } else {
        return contains(root.left, val);
    }
}

//删除最小值节点，并返回最小值
public int removeMin() {
    int min = findMin();
    root = removeMin(root);
    return min;
}
 
 
//删除最大值节点，并返回最大值
public int removeMax() {
    int max = findMax();
    root = removeMax(root);
    return max;
}
 
 
/**
* 删除以root为根的最大值节点
* @param root
* @return
*/
private TreeNode removeMax(TreeNode root) {
    if (root.right == null) {
        TreeNode left = root.left;
        root.left = root = null;
        size--;
        return left;
    }
    root.right = removeMax(root.right);
    return root;
}
 
 
/**
* 删除以root为根的最小值节点
* @param root
* @return
*/
private TreeNode removeMin(TreeNode root) {
    if (root.left == null) {
        TreeNode right = root.right;
        root.right = root = null;
        size--;
        return right;
    }
    root.left = removeMin(root.left);
    return root;
}

        删除任意值***

    //删除值为val的任意节点
    public void remove(int val) {
        root = remove(root, val);
    }
 
 
    /**
     * 删除以root为根节点中值为val的节点
     *
     * @param root
     * @param val
     * @return
     */
    private TreeNode remove(TreeNode root, int val) {
        if (root == null) {
            // 把树中所有节点都遍历完还没找到值为val的节点，就不存在值val的节点
            throw new NoSuchElementException("BST中没有值为" + val + " 的节点。");
        } else if (val > root.val) {
            // 此时待删除的节点位于左子树
            root.right = remove(root.right,val);
            return root;
        } else if (val < root.val) {
            // 此时待删除的节点位于右子树
            root.left = remove(root.left,val);
            return root;
        } else {
            // 此时root.val == val
            // root就是待删除的节点
            if (root.left == null) {
                //只有有右孩子
                TreeNode right = root.right;
                root.right = root = null;
                size--;
                return right;
            }
            if (root.right == null) {
                //只有左孩子
                TreeNode left = root.left;
                root.left = root = null;
                size--;
                return left;
            }
            // 此时说明root.left 和 root.right 都不为空
            // Hibbard Deletion
            // 方法一：找到后继节点
            TreeNode successor = minNode(root.right);
            // removeMin中size已经--
            // 1.先让后继节点的右树连接root删除右树最小节点后的右树
            successor.right = removeMin(root.right);
            // 2.再让后继节点的左树连接root的左树
            // 1和2顺序不可颠倒
            successor.left = root.left;
            // 删除root节点
            root.left = root.right = root = null;
            // 拼接后继节点
            return successor;
            //方法二：找到前驱节点
//            TreeNode prevNode = maxNode(root.left);
//            prevNode.left = removeMax(root.left);
//            prevNode.right = root.right;
//            root.left = root.right = root = null;
//            return prevNode;
        }
    }

/**
* 基于开散列方式下整型哈希表的实现
*
* @author 是阿秋啊
* @date 2022/03/23 14:57
**/
public class MyHashMap {
    private class Node {
        // 对key求哈希运算
        int key;
        int value;
        Node next;
 
 
        public Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
 
 
    // 记录存入的键值对个数
    private int size;
    // 默认哈希表长度
    private static final int DEFAULT_CAPACITY = 16;
    // 默认负载因子
    private static final double LOAD_FACTOR = 0.75;
    // 取模数，用于获取key索引
    private int M;
    // 实际存储的数组
    private Node[] data;
 
 
    public MyHashMap() {
        // 默认无参构造数组长度为默认值
        this(DEFAULT_CAPACITY);
    }
 
 
    public MyHashMap(int initCap) {
        // 定义初始长度
        this.M = initCap;
        this.data = new Node[initCap];
    }
 
 
    // 哈希函数
    public int hash(int key) {
        // 获取索引
        return Math.abs(key) % M;
    }
 
 
    // 在当前的哈希表添加一个键值对 key = value
    public int put(int key, int value) {
        // 1.先获取key值对应的索引
        int index = hash(key);
        // 2.在哈希表中查找是否存储过
        for (Node x = data[index]; x != null; x = x.next) {
            if (x.key == key) {
                //key存在，修改value值
                int oldVal = x.value;
                x.value = value;
                return oldVal;
            }
        }
        // 走到这里则表示哈希表中没有存储key值
        // 使用头插法将新key插入
        Node node = new Node(key, value, data[index]);
        data[index] = node;
        size++;
        // 4.添加一个元素后查看哈希表是否需要扩容
        if (data.length * LOAD_FACTOR <= size) {
            // 扩容
            resize();
        }
        return value;
    }
 
 
    // 哈希表扩容
    private void resize() {
        Node[] newData = new Node[data.length << 1];
        this.M = newData.length;
        for (Node datum : data) {
            if (datum != null) {
                // 对应的链表不为空
                // 进行对应的链表遍历
                for (Node x = datum; x != null; ) {
                    // 此处不在for循环中写x递进条件，是因为x会指向新数组的节点，next会发生变化
                    // 暂存一下后继节点
                    Node next = x.next;
                    // 新数组的头插
                    int newIndex = hash(x.key);
                    x.next = newData[newIndex];
                    newData[newIndex] = x;
                    // 继续进行下一个节点的搬移操作
                    x = next;
                }
            }
        }
        data = newData;
    }
 
 
    /**
     * 删除哈希表中key对应的节点
     * 返回删除前的value
     *
     * @param key
     * @return
     */
    public int remove(int key) {
        int index = hash(key);
        // 判断头节点是否是待删除的节点
        Node head = data[index];
        if (head.key == key) {
            int val = head.value;
            data[index] = head.next;
            head.next = head = null;
            size--;
            return val;
        }
        // 此时不是头节点
        Node prev = head;
        // 此时不需要判断头节点
        while (prev.next != null) {
            // prev为待删除值的前驱节点
            if (prev.next.key == key) {
                Node cur = prev.next;
                int val = cur.value;
                prev.next = cur.next;
                cur.next = cur = null;
                return val;
            }
            prev = prev.next;
        }
        // 走到此时说明哈希表中没有key的节点
        throw new NoSuchElementException("no such key! cannot remove!");
    }
 
 
    // 判断哈希表中是否含有key的节点
    public boolean containsKey(int key) {
        int index = hash(key);
        for (Node x = data[index]; x != null; x = x.next) {
            if (x.key == key) {
                return true;
            }
        }
        return false;
    }
 
 
    // 判断含有值为value的节点
    public boolean containsValue(int value) {
        // 不同于查找key，查找value需要遍历整个哈希表
        for (Node datum : data) {
            for (Node x = datum; x != null; x = x.next) {
                if (x.value == value) {
                    return true;
                }
            }
        }
        return false;
    }
}