网站html静态化,合肥的电商网站设计,2008 iis 添加 网站 权限设置,搜了网推广效果怎么样目录
一、搜索树
1、概念
2、查找
3、插入
4、删除
二、搜索
1、概念及场景
2、模型
#xff08;1#xff09;纯key模型
#xff08;2#xff09;Key-Value模型
三、Map的使用
1、什么是Map#xff1f;
2、Map的常用方法
#xff08;1#xff09;V put(K …目录
一、搜索树
1、概念
2、查找
3、插入
4、删除
二、搜索
1、概念及场景
2、模型
1纯key模型
2Key-Value模型
三、Map的使用
1、什么是Map
2、Map的常用方法
1V put(K key, V value)
2V get(Object key)
3V getOrDefault(Object key, V defaultValue)
4V remove(Object key)
5Set keySet()
6Collection values()
7Set entrySet()
8boolean containsKey(Object key)
9boolean containsValue(Object value
四、Set的使用
1、什么是Set?
2、Set的常用方法
1boolean add(E e)
2void clear()
3boolean contains(Object o)
4Iterator iterator()
5boolean remove(Object o)
6int size()
7boolean isEmpty()
8Object[] toArray()
9boolean containsAll(Collection c)
10boolean addAll(Collection c) 在前面我们已经学完了数据结构中常见的排序算法而今天我们就要开始学习数据结构上新的里程碑——Map Set。
一、搜索树
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 null;
}
2、查找
这个操作就很简单了我们只需要遍历这棵二叉搜索树判断是否有结点的val值与我们给的val值相等即可。
当然上述是对于一棵普通的二叉树的查找方式而我们的二叉搜索树又称二叉排序树那么它一定是有一定顺序的所以查找方式也是有一定不同的根据上述的性质我们直到左子树的值都小于根节点的值右子树的值多大于根节点的值并且每棵子树也都是二叉搜索树。
1、我们可以先定义一个cur存储root进行遍历 2、如果我们 cur的值小于我们要查找的值就上我们的右子树上去找 cur.val val 执行 cur cur.right 3、如果我们 cur的值大于我们要查找的值就上我们的左子树上去找 cur.val val 执行 cur cur.left 4、如果我们 cur的值等于于我们要查找的值就返回cur cur.val val 执行 return cur 5、如果树为空或者没有要查找的值就返回null
public TreeNode 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 cur;}}return null;} 最优情况下二叉搜索树为完全二叉树其平均比较次数为 O(logN)
最差情况下二叉搜索树退化为单支树其平均比较次数为 N 3、插入
1、我们要先判断是否为空树如果为空树那么我们此时要插入的结点就是我们的根结点 2、不为空树我们就创建两个结点prev和cur,cur用来遍历二叉搜索树prev用来存储cur遍历到结点的根结点。 3、我们要先进行插入数据大小的判断如果大于cur.val先让prev指向cur,然后让cur往右走小于先让prev指向cur然后让cur往左走。 4、如果我们在遍历的过程中发现我们要插入的值在二叉搜索树中存在就直接返回不用插入。
5、如果cur指向null了我们就代表可以进行插入了跳出循环 6、跳出循环后此时prev就是我们cur的父结点我们要进行判断是在prev左边还右边进行插入 如果prev的值小于val,在prev的右边进行插入 prev.val val 执行 prev.right newTreeNode 如果prev的值大于val,在prev的左边进行插入 prev.val val 执行 prev.left newTreeNode public void insert(int val) {TreeNode newTreeNode new TreeNode(val);if(root null){root newTreeNode;return;}TreeNode cur root;TreeNode prev null;while(cur ! null){if(cur.val val){prev cur;cur cur.right;}else if(cur.val val){prev cur;cur cur.left;}else{return;}}if(prev.val val){prev.right newTreeNode;}if(prev.val val){prev.left newTreeNode;}}4、删除
对于删除的操作我们还是要先找到要删除的结点我们还是利用cur和prev两个结点cur用来查找要删除的结点prev用来记录我们遍历过程中cur的父节点而当我们找到这个要删除的结点后我们还要面临几种情况 1、cur.left null 2、cur.rightnull 3、cur.left!nullcur.right!null
我们先创建两个结点 target 存储cur.right 和 targetParent 存储 cur,如果我们想要进行删除我们必须要确保我们删除后此时结点之后的左右子树依然能够是二叉搜索树所以我们要确定我们新的值要比左边大又要比右边小而这时我们有两种删除方法 方法一在左子树中找到左子树中的最大值即左树的最右边的结点
因为左子树的最大值一定大于所有左子树的结点并且因为最大值属于左树左树的值是一定小于右树的因此此时的最大值也一定是小于右树的然后让他的值更新cur结点最后我们只要删除这个结点即可 方法二在右子树中找到右子树中的最小值即右数的最左边的结点
因为右子树的最小值一定小于所有右子树的结点并且因为最小值属于右树右树的值是一定大于左树的因此此时的最小值也一定是大于左树的然后让他的值更新cur结点最后我们只要删除这个结点即可 public void remove(int val){TreeNode cur root;TreeNode prev null;while (cur ! null) {if(cur.val val) {prev cur;cur cur.right;}else if(cur.val val) {prev cur;cur cur.left;}else {removeNode(cur,prev);return ;}}}public void removeNode(TreeNode cur ,TreeNode prev){if(cur.left null){if(cur root ){root root.right;}else if(cur prev.left){prev.left cur.right;}else if(cur prev.right){prev.right cur.right;}}else if(cur.right null){if(cur root ){root root.left;}else if(cur prev.left){prev.left cur.left;}else if(cur prev.right){prev.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(targetParent.left target){targetParent.left target.right;}else{targetParent.right target.right;}}}
二、搜索
1、概念及场景
Map和set是⼀种专门用来进行搜索的容器或者数据结构其搜索的效率与其具体的实例化子类有关。 以前常见的搜索方式有
1、直接遍历时间复杂度为O(N)元素如果比较多效率会非常慢
2、二分查找时间复杂度为,但搜索前必须要求序列是有序的
上述查找方式比较适合进行静态查找的方式我们在这种方式下一般不会进行插入和删除的操作
因此这就要引出我们的动态查找方式而这章要讲的Map和Set就是一种适合动态查找的集合容器。
2、模型
一般把搜索的数据称为关键字Key和关键字对应的称为值Value将其称之为Key-value的键 值对所以模型会有两种 1纯key模型
比如我们有一句英文Failure is the fog through which we glimpse triumph.透过失败的迷雾才能瞥见胜利的光辉。
而我们的纯key模型就是查找我们的单词 fog 是否出现在这句英文中。 2Key-Value模型
而我们的Key-Value模型就是统计这句英文中每个单词出现的次数统计结果是每个单词都有与其对应的次数: 单词单词出现的次数
而接下来我们要介绍的Map中存储的就是key-value的键值对Set中只存储了Key。 三、Map的使用
1、什么是Map
Map是一个接口类该类没有继承自Collection该类中存储的是结构的键值对并且K一定是唯一的不能重复。
2、Map的常用方法
由于Map是是一个接口不能自己进行实例化我们需要使用TreeMap红黑树和HashMap哈希桶进行实例化。 1V put(K key, V value)
解释设置 key 对应的 value 我们发现Map还会根据我们的key值自动排序 2V get(Object key)
解释返回 key 对应的 value 3V getOrDefault(Object key, V defaultValue)
解释返回 key 对应的 valuekey不存在返回默认值 4V remove(Object key)
解释删除 key 对应的映射关系 5SetK keySet()
解释返回所有 key 的不重复集合 6CollectionV values()
解释返回所有 value 的可重复集合 7SetMap.EntryK,V entrySet()
解释返回所有的 key-value 映射关系 在对他进行讲解前我们要先对Map.EntryK,V进行说明 Map.Entry是Map内部实现的用来存放键值对映射关系的内部类该内部类中主要提供了的获取value的设置以及Key的比较方式 方法解释K getKey()返回 entry 中的 keyV getValue()返回 entry 中的 valueV setValue(V value将键值对中的value替换为指定value 8boolean containsKey(Object key)
解释判断是否包含 key 9boolean containsValue(Object value
解释判断是否包含 value 注意事项 1、Map是一个接口不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap或者 HashMap 2、Map中存放键值对的Key是唯一的value是可以重复的 3、在TreeMap中插入键值对时key不能为空否则就会抛NullPointerException异常value可以为空。但是HashMap的key和value都可以为空。 4、Map中的Key可以全部分离出来存储到Set中来进行访问(因为Key不能重复)。 5、Map中的value可以全部分离出来存储在Collection的任何一个子集合中(value可能有重复)。 6、Map中键值对的Key不能直接修改value可以修改如果要修改key只能先将该key删除掉然 后再来进行重新插入。 四、Set的使用
1、什么是Set?
Set与Map主要的不同有两点Set是继承自Collection的接口类Set中只存储了Key。
2、Set的常用方法
1boolean add(E e)
解释添加元素但重复元素不会被添加成功 2void clear()
解释清空集合 3boolean contains(Object o)
解释判断o是否在集合中 4IteratorE iterator()
解释返回迭代器通过迭代器进行打印 5boolean remove(Object o)
解释删除集合中的 o 6int size()
解释返回set中元素的个数 7boolean isEmpty()
解释检测set是否为空空返回true否则返回false 8Object[] toArray()
解释将set中的元素转换为数组返回 9boolean containsAll(Collection? c)
解释集合c中的元素是否在set中全部存在是返回true否则返回false 10boolean addAll(Collection?extends E c)
解释将集合c中的元素添加到set中可以达到去重的效果 注意事项 1、Set是继承自Collection的一个接口类 2、Set中只存储了key并且要求key一定要唯一 3、TreeSet的底层是使用Map来实现的其使用key与Object的一个默认对象作为键值对插入到Map中的 4、Set最大的功能就是对集合中的元素进行去重 5、实现Set接口的常用类有TreeSet和HashSet还有一个LinkedHashSetLinkedHashSet是在 HashSet的基础上维护了一个双向链表来记录元素的插入次序。 6、Set中的Key不能修改如果要修改先将原来的删除掉然后再重新插入 7、TreeSet中不能插入null的keyHashSet可以。 好了今天的分享就到这里了还请大家多多关注我们下一篇见
