【数据结构】搜索树&Map&Set

目录

1.搜索树

1.1概念

1.2查找

1.3插入

1.4删除

2.Map

2.1map说明

2.2TreeMap和HashMap

2.3常用方法

3.Set

3.1set说明

3.2TreeSet和HashSet

3.3常用方法

---

1.搜索树

1.1概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者具有以下性质：

1> 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2> 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3> 它的左右子树也分别为二叉搜索树

1.2查找

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 TreeNode search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            } else {
                return cur;
            }
        }
        return null;
    }
}

1.3插入

从根节点开始，比根结点小向左走，比根结点大向右走，直到达到叶子结点，插入该叶子结点。

public boolean insert(int key) {
    TreeNode node = new TreeNode(key);
    //第一次插入
    if (root == null) {
        root = node;
        return true;
    }
    //之后的插入
    TreeNode cur = root;
    TreeNode parent = null;//用来记录cur的位置
    while (cur != null) {
        if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        }else { //相同数据不能插入
            return false;
        }
    }
    if (parent.val > key) {
        parent.left = node;
    }else {
        parent.right = node;
    }
    return true;
}

1.4删除

方法：替罪羊删除法

找到左树的最右边，即左树最大值，或找到右树的最左边，即右树的最小值 作为替罪羊。

/**
 * @param cur 要删除的结点
 * @param parent 要删除节点的父节点
 */
private void remove(TreeNode cur, TreeNode parent) {
    if(cur.left == null) { //1.cur的左树为空
        if(cur == root) {
            root = cur.right;
        }else if(cur == parent.left) {
            parent.left = cur.right;
        }else {
            parent.right = cur.right;
        }
 
    }else if(cur.right == null) { //2.cur的右树为空
        if(cur == root) {
            root = cur.left;
        }else if(cur == parent.left) {
            parent.left = cur.left;
        }else {
            parent.right = cur.left;
        }
 
    }else { //3.cur的左右树都不为空
        //方法：替罪羊删除法
        //找右树的最小值，即右树的最左边作为替罪羊
        TreeNode targetParent = cur;
        TreeNode target = cur.right;
        while (target.left != null) { //直到左树为空，说明已经找到了替罪羊
            targetParent = target;
            target = target.left;
        }
        cur.val = target.val; //覆盖
        //回到了上面的情况1和情况2
        if(target == targetParent.left) {
            targetParent.left = target.right;
        }else {
            targetParent.right = target.right;
        }
    }
}

Set中存储key，Map中存储Key-value键值对

2.Map

2.1map说明

Map官方文档：Map (Java Platform SE 8 )

注意：

1.Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或HashMap；

2.Map中存放键值对的Key是唯一的，value是可重复的；

3.在TreeMap中插入键值对时，key不能为空，否则会抛出NullPointerException异常，value可以为空。但HashMap的key和value都可以为空；
4. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)；
5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
6. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

2.2TreeMap和HashMap

2.3常用方法

3.Set

3.1set说明

Set官方文档：Set (Java Platform SE 8 )

注意：

1. Set是继承自Collection的一个接口类；
2. Set中只存储key，并且要求key一定要唯一；
3. TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的；
4. Set最大的功能就是对集合中的元素进行去重；
5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序；
6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入；
7. TreeSet中不能插入null的key，HashSet可以。

3.2TreeSet和HashSet

类TreeMap和HashMap：

3.3常用方法