做h5那个网站模板好,免费网站整站模板源码,成都做网站做的好的公司,品牌logo设计理念介绍Hi~#xff01;这里是奋斗的明志#xff0c;很荣幸您能阅读我的文章#xff0c;诚请评论指点#xff0c;欢迎欢迎 ~~ #x1f331;#x1f331;个人主页#xff1a;奋斗的明志 #x1f331;#x1f331;所属专栏#xff1a;数据结构、LeetCode专栏 #x1f4da;本系… 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。
