Java数据结构 | TreeMap 和 TreeSet

1. 搜索树

1.1 概念

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

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

如图是根据数组int array = {4,1,3,6,8,7,2,9,0,4} 构建的一棵二叉搜索树

1.2 搜索树的查找、插入、删除思路及代码

1.2.1 查找

思路： 给定一个要查找的 value 值，让 value 值与根节点进行比较，若 value 值比根节点值大，则去根节点的右子树查找，若 value 值比根节点值小，则去根节点的左子树查找

⭐代码实现：

    public TreeNode search(int val) {
        //让cur指向根节点
        TreeNode cur = root;
        while (cur != null) {
            if (val > cur.val) {
                cur = cur.right;//val比根节点的值大，去右子树找
            } else if (val < cur.val) {
                cur = cur.left;//val比根节点的值小，去左子树找
            } else {
                return cur;//找到了
            }
        }
        return null;
    }

1.2.2 插入

思路： 插入的思路和查找类似，给定一个要插入的 value 值，让 value 值与根节点的值进行比较，若 value 值比根节点的值大，则去根节点的右子树继续判断；若 value 值比根节点的值小，则去根节点的左子树继续判断；若遇到相同数值，则不插入；若根节点为空。则创建节点将 value 值插入。在写代码时，我们需要定义一个 cur 引用去寻找位置，同时还需要定义一个 parent 引用去记录 cur 所指节点的父亲节点，若不定义 parent 则会丢失插入位置！

⭐代码实现：

    public void insert(int val) {
        TreeNode newNode = new TreeNode(val);
        if (root == null) {
            root = newNode;
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            parent = cur;
            if (val > cur.val) {
                cur = cur.right;
            } else if (val < cur.val) {
                cur = cur.left;
            } else {
                return;//存在相同数值，不插入
            }
        }
        //走到这里，cur为空了，创建节点
        if (val > parent.val) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
    }

1.2.3 删除（难点）

待删除节点的引用为 cur ，待删除结点的双亲节点为 parent

思路：

• 情况一：待删除结点的左孩子为空，即 cur.left == null

  • a. cur 是根节点；
  • b. cur 不是根节点，cur == parent.left；
  • c. cur 不是根节点，cur == parent.right；
    

• 情况二：待删除结点的右孩子为空，即 cur.right == null

  • a. cur 是根节点；
  • b. cur 不是根节点，cur == parent.left；
  • c. cur 不是根节点，cur == parent.right；
    

• 情况三：待删除结点的左右孩子都不为空，即 cur.left != null && cur.right != null

  • 使用替换法进行删除，在左子树中寻找一个最大值节点或者在右子树中寻找一个最小值节点，与当前 cur 节点替换，再处理节点的删除问题；（以取右子树最小值为例）
    

⭐代码实现：

    //二叉搜索树的删除
    public void remove(int val) {
        TreeNode cur = root;
        TreeNode parent = null;
        //查找到节点位置
        while (cur != null) {
            parent = cur;
            if (cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            } else {
                //找到节点，进行删除
                removeNode(cur,parent);
                return;
            }
        }
    }
    private void removeNode(TreeNode cur, TreeNode parent) {
        if (cur.left == null) {
            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) {
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else {
                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.left) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }

1.3 二叉搜索树的性能分析

要进行二叉搜索树的插入和删除操作都必须进行查找操作，查找效率代表了二叉搜索树中各个操作的性能。
对于同一个关键码集合，如果插入的次序不同，则可能会得到不同结构的二叉搜索树。

最优情况下：二叉搜索树为完全二叉树，平均比较次数为 logN ，查找的时间复杂度为 O(logN)
最差情况下：二叉搜索树退化为单只树，平均比较次数为 N ，查找的时间复杂度为 O(N)

2. Map 和 Set

Map 和 Set 是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关，Map 和 Set 是一种适合动态查找的集合容器。

模型： 一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为 Key-Value 的键值对，因此模型会有两种：

• 纯 Key 模型： 比如查找一个单词是否在这篇文章里
• Key-Value模型： 比如一个单词在在文章中出现的次数

注：Map 中存储的就是 Key-Value 键值对，而 Set 中只存储了 Key

2.1 Map 接口

Map是一个接口类，该类没有继承自 Collection ，该类中存储的是 <K,V> 结构的键值对，K 一定是唯一的，并且不能重复。

2.1.1 Map.Entry<K,V>

Map.Entry<K,V> 是 Map 内部实现的用来存放 <Key,Value> 键值对映射关系的内部类，该内部类中主要提供了 <Key,Value> 的获取，Value 的设置以及 Key 的比较方式。

注：Map.Entry<K,V> 中没有提供设置 Key 的方法

2.1.2 Map的常用方法

说明：

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

2.2 Set 接口

Set 是继承自 Collection 的接口类，Set 中只存储了 Key，并且 Key 唯一

2.2.1 Set 的常用方法

说明：

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

⚠️⚠️⚠️ 注：Map 和 Set 的常用方法需要通过不断的练习进行掌握！！！

TreeMap 和 TreeSet 的内容到这里就结束啦，有任何问题欢迎私信留言一起探讨！