摄影工作室建设_b2c电商平台的特点_sem和seo的关系_百度问答首页

一、接口关系介绍

二、搜索树

2.1 什么是二叉搜索树以及优势

1. 概念：
   
2. 优势：查找元素时可以直接砍去一半的值，达到 log(N)
   • 示例：此时如果要找4，因为4比6小，所以要去6的左边找，此时因为4比3大，所以要去3的右树找，最终找到了
   • 如果找到了就返回，如果直到全部找完遇到null了也没找到，说明该搜索树下根本就没有该元素
3. 有序问题：二叉搜索树的中序遍历是有序的

2.2 模拟二叉搜索树

结构

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;
}

查找元素

1. 特殊情况：如果是单分支为O(N)
   • 当时完全二叉树的时候，时间复杂度为O(logN)，这也是最好的情况
   • 但如果这棵树是一棵单分支的树，时间复杂度就变成O(N)了
   • 为了避免这种情况，我们需要旋转这棵树，让这棵树从单分支变成多分支，也就是实现AVL树
     2 . 其他：插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能

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;
}

插入元素

1. 原则：插入之后，我们依旧需要满足这是一棵二叉树
2. 插入的特点：
   • 二叉搜索树在插入数据的时候，一定是插入到叶子的位置
   • 对于二叉搜索树来说，重复的元素不能插入
3. 思路：
   • 如果是第一次插入时，直接把root指向这个结点。如果不是，遍历该树找到合适的叶子位置插入(为了知道父亲结点是谁以便插入，我们还需要用parent记录父亲结点的位置)
   • 注意，一样的值不能插入

public boolean insert(int key) {TreeNode node = new TreeNode(key);//第一次插入的时候if(root == null) {root = node;return true;}TreeNode cur = root;TreeNode parent = null;while (cur != null) {if(cur.val < key) {parent = cur;cur = cur.right;}else if(cur.val == key) {return false;//一样的值 不能进行插入}else {parent = cur;cur = cur.left;}}if(parent.val > key) {parent.left = node;}else {parent.right = node;}return true;
}

删除元素

1. 查找要删除的元素是否在二叉树：如果确实有，需要记录父亲结点以方便删除

 public void removeNode(int key) {TreeNode cur = root;TreeNode parent = null;while (cur != null) {if(cur.val < key) {parent = cur;cur = cur.right;}else if(cur.val > key) {parent = cur;cur = cur.left;}else {remove(cur,parent);return;}}}

2. 执行具体的删除逻辑：
   
   

 private void remove(TreeNode cur, TreeNode parent) {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(parent.left == cur) {parent.left = cur.left;}else {parent.right = cur.left;}}else {//cur的左右两边 都不为空TreeNode targetParent = cur;TreeNode target = cur.right;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;}}}

三、Map 和 Set

3.1 接口介绍

1. 概念：Map和Set是专门用来进行搜索的容器或数据结构
   • Set是纯key模型，Map是 Key-Value 模型
   • Set最大的功能就是对集合中的元素进行去重
2. 接口实例化：这两个都是接口，其中Map可以由TreeMap、HashMap实例化，Set可以由TreeSet、HashSet实例化
3. 查找效率：TreeSet和TreeMap底层是二叉搜索树，HashSet和HashMap则是哈希表，前者的查找效率最好情况为O(logN)，极端单分支情况为O(N)，后者的查找效率为O(1)，但是是牺牲空间换取了时间

3.2 Map 方法介绍

1. 插入元素：V put(K key, V value)
   • key能比较：此时相当于往搜索树中插入数据，且是和key比较。所以如果插入的元素是个null或无法比较，都会报异常
   • 如果有重复的key：Map里无法存相同的key，相同的key，会更新value值

public static void main(String[] args) {Map<String, Integer> map = new TreeMap<>();map.put("a", 1);map.put("b", 2);map.put("a", 3);   System.out.println(map.get("b"));
}

2. 获取元素：
   • V get(Object key)：根据key的值获取value，如果没获取到，返回null
   • V getOrDefault(Object key, V defaultValue)：根据key的值获取value，如果没获取到，返回设置的defaultValue

public static void main(String[] args) {Map<String, Integer> map = new TreeMap<>();map.put("a", 1);map.put("b", 2);System.out.println(map.get("b")); //2System.out.println(map.get("c"));//nullSystem.out.println(map.getOrDefault("c", 10));//10
}

3. 把Map里面所有不重复的key都放到Set里：Set keySet()

public static void main(String[] args) {Map<String, Integer> map = new TreeMap<>();map.put("a", 1);map.put("b", 2);map.put("a", 3);Set<String> set = map.keySet();//set里面只有a、b2个元素
}

4. 返回所有的key-value映射关系：Set<Map.Entry<K, V>> entrySet()
   • Map.Entry<K, V>：是Map内部实现的用来存放<key, value>键值对映射关系的内部接口
     • K getKey()、K getValue()、V setValue(V value)，注意没有提供设置key的方法
       
5. 其他：
   • 删除结点：V remove(Object key)
     • Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入
   • 把所有的Value都放到一个集合里(可重复)：Collection values()
   • 是否包含Key：boolean containsKey(Object key)
   • 是否包含Value：boolean containsValue(Object value)

3.3 Set 方法介绍

1. 构造方法：
   

2. 添加结点：boolean add(E e)
   

3. 遍历：

   • 返回迭代器：Interator< E> interator
   • 使用迭代器遍历：

public static void main(String[] args) {Set<String> set = new TreeSet<>();set.add("h");set.add("a");set.add("i");Iterator<String> iterator = set.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}
}

4. 其他：
   • 删除结点：boolean remove(Object o)
     • Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
   • 清空集合：void clear()
   • 判断o是否在集合中：boolean contains(Object o)
   • 返回个数：int size()
   • 判断是否为空：boolean isEmpty()
   • 将Set里的元素转为数组：Object[] toArray()
   • 判断集合中的元素是否全在Set里：boolean containsAll(Collection<?> c)
   • 把集合中的元素全部放到Set里，以实现去重效果：boolean addAll(Collection<? extends E> c)