Java-数据结构-(TreeMap TreeSet)
一、搜索树
① 搜索树的概念
搜索树是一种数据结构，用于高效的存储和查询数据，它通过树形结构组织数据，使得搜索、插入和删除操作的时间复杂度较低，这次我们来介绍比较常见的搜索树："二叉搜索树"
📚 二叉搜索树的性质：
📕 有序性：对于树中的每个节点：
左子树的所有节点值都小于该节点的值
右子树的所有节点值都大于该节点的值
它的左右子树也分别为二叉搜索树
📕 高效操作：
搜索：比较目标值与当前节点值，决定向左或向右子树搜索，时间复杂度为O(log n)(前提为平衡)
插入：按照搜索规则，找到合适位置插入新节点。
删除：删除节点后，调整树结构以保持有序性。
接下来，为了更好的理解二叉搜索树是什么，以及了解二叉搜索树内部如何实现，我们会简单的手动实现一个二叉搜索树，所以在这之前，我们需要先为后续二叉搜索树的实现先写一个基本框架：
📖 代码示例：
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 = null;
}② 搜索操作
时间复杂度：
平均情况：O(log n)
最坏情况：O(n) -> 当树退化成链表时(例如只存在左子树或右子树)
📚 搜索操作：
📕 从根节点开始对二叉树进行查找操作。
📕 如果目标值等于当前节点值，代表搜索成功，返回该结点
📕 如果目标值小于当前节点的值，转向左子树继续搜索。
📕 如果目标值大于当前节点的值，转向右子树继续搜索。
📕 不断重复如上的操作，直到找到目标值或达到空节点(代表该值不存在)
⭐ 图示：
📖 代码示例：
//查找结点
public TreeNode search(int val){
TreeNode cur = root;
while(cur != null){
if(cur.val > val){
cur = cur.left;
}else if(cur.val < val){
cur = cur.right;
}else {
return cur;
}
}
return null;
}③ 插入操作
时间复杂度：
平均情况：O(log n)
最坏情况：O(n) -> 当树退化成链表时(例如只存在左子树或右子树)
📚 插入操作：
📕 从根节点开始，如果树为空，新节点成为根节点
📕 如果目标值小于当前节点的值，转向左子树继续搜索。
📕 如果目标值大于当前节点的值，转向右子树继续搜索。
📕 如果目标值等于当前节点值，代表已经存在，退出插入。
📕 不断重复如上的操作，直到找到一个空位置。
📕 在找到的空位置插入新节点。
📖 代码示例：
//插入结点
public void insert(int val){
if(root == null){
root = new TreeNode(val);
return;
}
TreeNode cur = root;
TreeNode p = null;
while(cur != null) {
p = cur;
if (cur.val > val) {
cur = cur.left;
} else if (cur.val < val) {
cur = cur.right;
} else {
return;
}
}
if(p.val > val){
p.left = new TreeNode(val);
}else if(p.val < val){
p.right = new TreeNode(val);
}
}④ 删除操作
时间复杂度：
平均情况：O(log n)
最坏情况：O(n) -> 当树退化成链表时(例如只存在左子树或右子树)
二叉搜索树的删除操作目的是删除一个节点，同时还要保证树的有序性。所以删除操作相对复杂，因为需要考虑被删除节点的子树的情况。
首先，我们要考虑的第一个问题就是：如果想从树中删除一个结点，那么最基本的也要做到，删除这个结点后，二叉树的链接不会断，这就需要我们同时要拿到要删除的结点的双亲结点，删除节点后再使它和其他节点进行连接。
📕 首先，通过搜索操作找到我们需要删除的结点。
📌 设待删除结点为 cur ，待删除结点的双亲结点为 paren
我们能够将删除操作细分为三种操作：
📚 cur.left == null
📕 如果目标节点的左子树为空，那么还能够细分出三个情况：
1. cur == root，则直接将 root 删除，root = cur.right；
2. cur == parent.left，使 parent.left 原节点删除，与 cur 的 right 链接(parent.left = cur.right)
3. cur == parent.right，使 parent.right 原节点删除，与 cur 的 right 链接(parent.right = cur.right)
📚 cur.right == null
📕 如果目标节点的右子树为空，那么还能够细分出三个情况：
1. cur == root，则直接将 root 删除，root = cur.left；
2. cur == parent.left，使 parent.left 原节点删除，与 cur 的 right 链接(parent.left = cur.left)
3. cur == parent.right，使 parent.right 原节点删除，与 cur 的 right 链接(parent.right = cur.left)
📚 cur.left != null && cur.right != null
📕 当cur.left和cur.right都不为空时，就会比较麻烦，因为我们删除 cur 后，还需要在 parent 后接上一个比 cur 的左子树都大，比 cur 的右子树都小的结点，这里我们要采取到的策略是"替换法"。
📕 何为替换法？就是直接在 cur 的左子树/右子树中查找到符合目标条件的结点 node ，直接使 cur.val = node.val，这样我们再将 node 删除即可。
📕 而删除 node 就需要我们再次存储一下当前 cur 的结点，作为后续查找左子树/右子树的结点的父亲节点，以便找到 node 时的删除操作。
1. 查找 cur 左子树中的最大结点(比 cur 左子树结点都大，比 cur 右子树结点都小)
2. 查找 cur 右子树中的最小结点(比 cur 左子树结点都大，比 cur 右子树结点都小)
📖 代码示例：
//删除结点(难点)
public void remove(int val){
TreeNode cur = root;
TreeNode parent = null;
while(cur != null){
if(cur.val > val){
cur = cur.left;
}else if(cur.val < val){
cur = cur.right;
}else {
removeNode(cur,parent);
return;
}
parent = cur;
}
return;
}
//删除结点(难点)
public void removeNode(TreeNode cur,TreeNode parent){
if(cur.left == null){
if(cur == root){
root = root.right;
}else if(cur == parent.left){
parent.left = cur.right;
}else if(cur == parent.right){
parent.right = cur.right;
}
}else if(cur.right == null){
if(cur == root){
root = root.left;
}else if(cur == parent.left){
parent.left = cur.left;
}else if(cur == parent.right){
parent.right = cur.left;
}
}
TreeNode node = cur.right;
TreeNode nodeParent = cur;
while(node.left != null){
nodeParent = node;
node = node.left;
}
cur.val = node.val;
if(node == nodeParent.left){
nodeParent.left = node.right;
}else if(node == nodeParent.right){
nodeParent.right = node.right;
}
}
二、搜索
① 搜索的概念
在学习 Map 和 Set 之前，大家即便不了解相关知识，至少肯定也是听说过的 ~ 而能够达到这样的知名度和这么广泛的应用场景，想必它们的重要性不言而喻 ~
为什么 Map 和 Set 会这么重要？被这么广泛的应用呢？
因为 Map 和 Set 是一种"搜索"和"插入"的时间复杂度都可以近似看作O(1)的数据结构。
这两种操作都近似看作O(1)，这么看起来是不是非常的可怕呀 ~ 毕竟我们之前所接触到的，不论是暴力枚举，还是优化的二分查找，其速度都和 Map & Set 差远了~
为什么 Map 和 Set 的插入和查询速度会如此之快呢？
举几个生活中的例子，大家就明白了：
比如：通过学生的 id 进行成绩查询
比如：通过输入快递单号，快速的找到快递
不论是学生的id，还是快递的单号，对于解决对应的问题都像是一把key，能够精确快速的解决~
(并且 Map 和 Set 还有自动去重的效果，这使得它们能处理的问题更加丰富了)
② 模型
通常在我们的搜索情况下，都是想要找到某个值(Key)，或者某个值对应的值(Value)，所以我们的模型就随之也拥有两种：
📕 纯 key 模型(Set)，比如：
一个班级的学生名单。其中每个学生的 id 都是唯一的。我们只关心这个学生在哪个班级，而并不关注其他的因素(成绩，年龄等)。那么这就是一个 纯 Key 模型，因为我们只关注" id "。
📕 Key - Value模型(Map)，比如：
一个电话簿。在电话簿中，每个人的名字（Key）对应一个电话号码（Value）。我们不仅关心有哪些人，还关心每个人的电话号码。这种一一对应的关系就是一个Key-Value模型。
三、Map
① Map的概念
Map是一种常见的数据结构，用于存储 Key-Value(键值对) 模型，它能够通过一个键(Key)，快速的查询，存储和删除对应的值(Value)。
Map 的核心特点是"键的唯一性"：每一个键只能映射到一个值。
② Map.Entry<K,V>
Map.Entry<K,V> 是 Java 中 Map 接口的一个内部接口，用于表示 Map 中的一个键值对(Key-Value)。它是 Map 中用于存储数据的基本单元，通常用于遍历 Map 或操作其中的键值对。
📕 K getKey()：返回当前键值对的键(Key)。
📕 V getValue()：返回当前键值对的值(Value)。
📕 V setValue(V value)：设置当前键值对的值(Value)，并返回之前的值。
📕 boolean equals(Object o)：比较当前 Map.Entry 与另一个对象是否相等。
📕 int hashCode()：返回当前 Map.Entry 的哈希值。
② Map 常用方法
📕 V get(Object key)
返回 key 对应的 value
📕 V getOrDefault(Object key，V defaultValue)
返回 key 对应的 value，如果不存在，返回默认值
📕 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
四、Set
① Set的概念
Set 和 Map 类似，只是 Set 是纯key模型，也就代表它只用于存储一个特定的 key，而并不存在映射关系
② Set 常用方法
📕 boolean add(E e)
添加元素，但重复元素不会被添加成功
📕 void clear()
清空set
📕 boolean contains(Object o)
判断 o 是否在 set 中
📕 Iterator<E> iterator()
返回迭代器
📕 boolean remove(Object o)
删除 set 中的 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 中(去重)
那么这篇关于二叉搜索树(TreeMap，TreeSet)的文章到这里就结束啦，作者能力有限，如果有哪里说的不够清楚或者不够准确，还请各位在评论区多多指出，我也会虚心学习的，我们下次再见啦