💕"活着是为了活着本身而活着"💕
作者：Mylvzi
文章主要内容：数据结构之Map/Set讲解+硬核源码剖析
一.搜索树
1.概念
二叉搜索树又叫二叉排序树，他或者是一颗空树，或者是具有以下性质的树
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
简单来说，二叉搜索树上存储结点的值满足以下条件:
left < root < right
注意：二叉搜索树中不能存在两个相同的值
2.二叉搜索树的操作及其实现
前提准备
static class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } } private TreeNode root = null;
1.查询操作(search)
根据二叉搜索树的性质很容易实现查询的操作
代码实现：
// search public boolean 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 true; } } return false; }
2.插入操作(insert)
让cur走到合适的位置，再去判断parent.val 与 val的关系，进行插入
画图分析：
代码实现：
// insert public boolean insert(int val) { TreeNode newNode = new TreeNode(val); // 空树直接插入 if (root == null) { root = newNode; return true; } // 保留cur的根节点 TreeNode parent = null; TreeNode cur = root; while(cur != null) { parent = cur; if(cur.val < val) { cur = cur.right; } else if(cur.val > val){ cur = cur.left; }else { // 二叉搜索树中不能存在两个相同的数字 return false; } } // 此时cur就是要插入的位置 if(parent.val < val) { parent.right = newNode; }else { parent.left = newNode; } return true; }
3.删除操作(remove)
如果你要删除的cur的结点只有一个子节点，此时删除十分容易
但是如果你想要删除的结点有两个子节点，处理稍微麻烦，因为在你删除cur结点之后，还要保证剩下的结点也满足二叉搜索树的性质，这里采用“替罪羊”法解决删除拥有两个子节点的结点
思路分析：
我现在想要删除90这个结点，但是删除之后谁来替代这个结点呢？
根据二叉搜索树的性质，90看作根节点，则他一定比左树的所有结点的值大，比右树所有结点的值小
我们需要找一个合理的结点去替换90，替换之后仍要满足二叉搜索树的性质，这个合理的结点可以通过两个方法实现
- 找左树的最大值
- 找右树的最小值
现在以找右树的最小值为例演示
代码实现
public void remove(int val) { TreeNode parent = null; TreeNode cur = root; while(cur != null) { parent = cur; if (cur.val < val) { cur = cur.right; } else if (cur.val > val) { cur = cur.left; }else { removeNode(parent,cur); return; } } } private void removeNode(TreeNode parent, TreeNode cur) { // 注意此时cur就是我要删除的数据 // cur的左树为空 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) { // cur的右树为空 if (cur == root) { root = cur.left; } else if (cur == parent.left) { parent.left = cur.left; }else { parent.right = cur.left; } }else {// 都不等于Null // 找右树的最小值 // 使用替罪羊法 /* TreeNode targetParent = cur; TreeNode target = cur.right; // 找右树的最小值 直到某个结点的left为null 则此节点就是右树最左边的结点 也就是右树的最小值 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; }*/ // 求左树的最大值 TreeNode tp = cur; TreeNode t = cur.left; while (t.right != null) { tp = t; t = t.right; } // 此时t就是左树的最大值 cur.val = t.val; // 重写链接 if (t == tp.left) { tp.left = t.left; }else { tp.right = t.left; } } }
3.性能分析
对于二叉搜索树来说，进行插入/删除操作都要先进行查询，所以二叉搜索树的性能取决于查询的效率 最好情况是二叉树是一颗完全二叉树 最坏情况则是二叉树是一颗单分支的二叉树
问题：如果是单分支的情况，二叉搜索树的效率会变得很低，如何解决这种问题呢？
4.和 java 类集的关系
TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的 二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证，关于红黑树的内容后序再进行讲解。
二.搜索
1.概念和场景
Map和Set是一种专门用来进行“搜索”的数据结构/容器，其搜索效率取决于其具体实现的子类
我们之前其实也学过搜索
1.直接遍历 最粗暴的搜索方法 时间复杂度0(N)
2.二分查找 需要序列是有序的 时间复杂度O(logN)
上述查找适合静态的查找，即在查找的过程中不会进行插入和删除的操作，但是现实中的很多查找都需要动态的进行插入和删除，比如：
1.根据学号查成绩
2.根据通讯录名字查找电话号
3.根据身高找女朋友(bushi)
......
在查找的过程中可能会出现插入和删除的操作，Map和Set就是用于动态的插入和删除的搜索容器
2.搜索的模型
搜索的方式其实有两种，一种是直接在一大堆数据中寻找，另一种是根据对应关系进行查找（比如你需要先找到通讯录的名字，才能根据通讯录的名字找到你要寻找的手机号），我们一般把搜索的数据称为关键字Key，key对应的称为值Value，将其称之为Key-value的键值对
1. 纯 key 模型(找有没有)
- 在词典中找单词
2. Key-Value 模型(找对应关系)
- 梁山好汉的江湖绰号：每个好汉都有自己的江湖绰号
- 学号对应着你的名字
而Map中存储的是Key-Value 模型，Set中存储的是纯 key 模型
三.Map的使用
先放一张Java中和数据结构有关的类的图
1.概念
Map是一个接口类，不能直接实例化对象，如果要使用，需要根据实现他的类来实例化具体的对象，比如TreeMap(底层是红黑树)和HashMap(底层是哈希表)
2.常用方法
1.put
在Map中添加key与value的映射关系
// 根据实现Map的类TreeMap来实例化一个对象 Map<String,Integer> map = new TreeMap<>(); // Put方法 // 设置 单词--出现的次数 这样的一个key与value的映射 map.put("apple",14); map.put("bank",15); map.put("cat",17);
注意：
1.我们知道，TreeMap的底层是一颗红黑树，存储的时候是使用结点来存储元素的，它实际上存储的是Key-Value的映射关系，实际上Map中存在一个内部类Map.Entry,用于表示映射关系
2.既然TreeMap是一种红黑树，那他在存入数据的时候必然要排序，排序的根据是Key
2.get方法
存在两个get方法 但都是为了返回key对应的value值
System.out.println(map.get("apple"));// 输出14 System.out.println(map.get("bank"));// 输出15 System.out.println(map.get("cat"));// 输出17 // get时进行判断 如果Map中含有传入的key就返回其value 没有则返回其默认值(解某些题很有用) System.out.println(map.getOrDefault("apple", 100));// 输出14 因为Map中含有apple System.out.println(map.getOrDefault("Dog", 100));// 输出100 因为Map中不含有Dog
数据结构之Map/Set讲解+硬核源码剖析（二）+https://developer.aliyun.com/article/1413571
