Hi~!这里是奋斗的明志,很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~~
🌱🌱个人主页:奋斗的明志
🌱🌱所属专栏:数据结构、LeetCode专栏
📚本系列文章为个人学习笔记,在这里撰写成文一为巩固知识,二为展示我的学习过程及理解。文笔、排版拙劣,望见谅。
这里写目录标题
- 前言
- 一、二叉搜索树
- 1.概念
- 2.search 搜索或查找
- 3.insert 插入
- 4.删除(难点)
- 4.1 根结点的左子树为空
- 4.2 根结点的右子树为空
- 4.3 根结点的左右子树都不为空
- 4.4 完整代码
- 5.性能分析
- 二、1.7 和 java 类集的关系
- 三、搜索
- 1.概念及场景
- 2.模型
前言
Map接口是独立的
实现Iterable接口的集合都是可以使用 for - Each 语句进行打印的
搜索性能会非常高
一、二叉搜索树
1.概念
二叉搜索树又称为二叉排序树,它或者是一棵空树,或者是具以下性质的二叉树:
若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
如果中序遍历这棵二叉搜索树,会发现遍历的结果是有序的
接下来就模拟实现一下二叉搜索树
首先,和之前二叉树的实现一样,都是一个节点包括值和指向左右节点的引用(利用孩子兄弟表示法)
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;
}
2.search 搜索或查找
若根节点不为空:
如果 查找key == 根节点的值 返回true
如果 查找key > 根节点的值 在其右子树查找
如果 查找key < 根节点的值 在其左子树查找
/*** search 搜索的意思** @param val* @return*/public boolean search(int val) {TreeNode cur = root;while (cur != null) {if (val > cur.val) {cur = cur.right;} else if (val < cur.val) {cur = cur.right;} else {return true;}}return false;}
算法从根节点开始,根据当前节点的值与 val 的大小关系,决定是向左子树还是向右子树移动,直到找到匹配的节点或者搜索到空节点为止。因为每一步都是根据节点值的大小进行移动,而树的高度(树的深度)是 log(n) 级别的(其中 n 是树中节点的数量),所以在平均情况下,search 方法的时间复杂度是 O(log n)。
3.insert 插入
如果该树为空树,即 根节点 == null 直接实例化一个结点,进行插入
如果树不是空树,按照查找逻辑确定插入位置,插入新的节点
public void insert(int val) {//判断是否是空树if (root == null) {root = new TreeNode(val);return;}//定义一个前驱结点TreeNode parent = null;//定义一个临时节点TreeNode cur = root;while (cur != null) {if (val > cur.val) {parent = cur;cur = cur.right;} else if (val < cur.val) {parent = cur;cur = cur.left;} else {return;}}//插入的这个结点TreeNode node = new TreeNode(val);if (val > parent.val) {parent.right = node;}if (val < parent.val) {parent.left = node;}
}
这个方法用于向二叉搜索树中插入一个新的节点,如果节点已经存在则不插入。插入操作首先需要找到要插入位置的父节点,然后根据 val 的大小决定是插入为左子节点还是右子节点。与 search 方法类似,插入操作的时间复杂度也取决于树的高度。在平均情况下,插入一个节点的时间复杂度也是 O(log n)。
4.删除(难点)
设待删除结点为cur,待删除节点的双亲结点为parent
4.1 根结点的左子树为空
cur.left == null
cur 是 root,则 root == cur.right
cur 不是 root ,cur 是 parent.left,则 parent.left = cur.right
cur 不是 root ,cur 是 parent.right,则 parent.right = cur.right
4.2 根结点的右子树为空
cur.right == null
cur 是 root,则 root = cur.left
cur 不是 root ,cur 是 parent.left,则 parent.left = cur.left
cur 不是 root ,cur 是 parent.right,则 parent.right = cur.left
4.3 根结点的左右子树都不为空
cur.left != null && cur.right != null
需要使用替换法进行删除,即在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被 删除节点中,再来处理该结点的删除问题
- 删除结点的左树的最大值,替换当前删除的结点(一定没有左子树)
- 删除结点的右树的最小值,替换当前删除的结点(一定没有右子树)
【情况一】
【情况二】
4.4 完整代码
/*** 删除这个结点* 利用替换的思路** @param val*/public void remove(int val) {//首先需要查找该树有没有该值TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (val > cur.val) {parent = cur;cur = cur.right;} else if (val < cur.val) {parent = cur;cur = cur.left;} else {//如果等于的话,说明该树有该值removeNode(parent, cur);return;}}}//进行覆盖的方法,删除结点private void removeNode(TreeNode parent, TreeNode 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) {if (cur == root) {root = cur.left;} else if (cur == parent.left) {parent.left = cur.left;} else {parent.right = cur.left;}} else {TreeNode t = cur.right;TreeNode tp = cur;while (t.left != null) {tp = t;t = t.left;}cur.val = t.val;if (tp.left == t) {tp.left = t.right;} else {tp.right = t.right;}}}
5.性能分析
插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度 的函数,即结点越深,则比较次数越多。
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
最优情况下,二叉搜索树为完全二叉树,其平均比较次数为: log2N 最差情况下,二叉搜索树退化为单支树,其平均比较次数为:
问题:如果退化成单支树,二叉搜索树的性能就失去了。那能否进行改进,不论按照什么次序插入关键码,都可以 是二叉搜索树的性能最佳?
二、1.7 和 java 类集的关系
TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set
;实际上用的是红黑树,而红黑树是一棵近似平衡的 二叉搜索树
,即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证,关于红黑树的内容后序再进行介绍
三、搜索
1.概念及场景
Map和set是一种专门用来进行搜索的容器或者数据结构,其搜索的效率与其具体的实例化子类有关。以前常见的 搜索方式有:
- 直接遍历,时间复杂度为O(N),
元素如果比较多效率会非常慢
- 二分查找,时间复杂度为o(log N) ,
但搜索前必须要求序列是有序的
上述排序比较适合静态类型的查找,即一般不会对区间进行插入和删除操作了,而现实中的查找比如:
- 根据姓名查询考试成绩
- 通讯录,即根据姓名查询联系方式
- 不重复集合,即需要先搜索关键字是否已经在集合中
可能在查找时进行一些插入和删除的操作,即动态查找,那上述两种方式就不太适合了,本节介绍的Map和Set是 一种适合动态查找的集合容器。
2.模型
一般把搜索的数据称为关键字(Key),和关键字对应的称为值(Value),将其称之为Key-value的键值对,所以 模型会有两种:
纯 key 模型,比如:
- 有一个英文词典,快速查找一个单词是否在词典中 。
- 快速查找某个名字在不在通讯录中
Key-Value 模型,比如:
- 统计文件中每个单词出现的次数,统计结果是每个单词都有与其对应的次数: <单词,单词出现的次数> 。
- 梁山好汉的江湖绰号:每个好汉都有自己的江湖绰号
而Map中存储的就是key-value的键值对, Set中只存储了Key。