TreeMap 和 TreeSet 是 Java 中利用搜索树实现的 Map 和 Set，具体来说是利用的红黑树，红黑树是一棵近似平衡的二叉搜索树，即在二叉树搜索树的基础上添加颜色和红黑树的性质验证。那么什么是搜索树？什么是 Map ？什么是 Set ?

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 的比较方式。

方法	解释
K getKey()	返回 entry 中的 key
V getValue()	返回 entry 中的 value
VsetValue(V value)	将键值对中的 value 替换为指定的 value

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

2.1.2 Map的常用方法

方法	解释
V get(Object key)	返回 key 对应的 value
V getOrDefault(Object key, V defaultValue)	返回 key 对应的 value，key 不存在，返回默认值
V put(K key, V value)	设置 key 对应的 value
V remove(Object key)	删除 key 对应的映射关系
Set< K > keySet()	返回所有 key 的不重复集合
Collection< V > values()	返回所有 value 的可重复集合
Set<Map.Entry<K, V>> entrySet()	返回所有的 key-value 映射关系
boolean containsKey(Object key)	判断是否包含 key
boolean containsValue(Object value)	判断是否包含 value

说明：

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 的常用方法

方法	解释
boolean add(E e)	添加元素，但重复元素不会被添加成功
void clear()	清空集合
boolean contains(Object o)	判断 o 是否在集合中
Iterator< E > iterator()	返回迭代器
boolean remove(Object o)	删除集合中的 o
int size()	返回set中元素的个数
boolean isEmpty()	检测set是否为空，空返回true，否则返回false
Object[] toArray()	将set中的元素转换为数组返回
boolean containsAll(Collection<?> c)	集合c中的元素是否在set中全部存在，是返回true，否则返回false
boolean addAll(Collection<? extends E> c)	将集合c中的元素添加到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 的内容到这里就结束啦，有任何问题欢迎私信留言一起探讨！