在学习TreeMap和TreeSet之前需要先学习有关搜索树的相关知识以及接口Map和Set。
1. 搜索树
1.1 概念
二叉搜索树又称二叉排序树,其特点是,该节点的左边都比其小,右边都比其大,每一棵子树都必须满足这个条件。如下图所示例子。2的左边都比2小,2的右边都比2大;7的左边都比7小,7的右边都比7大;15的左边都比15小,15的右边都比15大,以此类推。
1.2 二叉搜索树的实现
1.2.1 插入
public void insert(int key) {TreeNode node = new TreeNode(key);if(root == null) {root = node;return;}TreeNode parent = null;TreeNode cur = root;while(cur != null) {if (cur.val == key) {return;} else if (cur.val > key) {parent = cur;cur = cur.left;} else {parent = cur;cur = cur.right;}}if(parent.val > key) {parent.left = node;}else {parent.right = node;}}
1.2.2 查找
/*** 时间复杂度:* 最好情况:O(logN)* 最坏情况:O(N)* @param key* @return*/public TreeNode search(int key) {TreeNode cur = root;while(cur != null) {if(cur.val == key) {return cur;}else if(cur.val > key) {cur = cur.left;}else {cur = cur.right;}}return null;}
1.2.3 删除
分成三种情况
public void remove(int key) {TreeNode cur = root;TreeNode parent = null;while(cur != null) {if(key < cur.val) {parent = cur;cur = cur.left;}else if(key > cur.val) {parent = cur;cur = cur.right;}else {removeNode(parent,cur);return;}}}private void removeNode(TreeNode parent, TreeNode cur) {if(cur.left == null) {if(cur == root) {root = root.right;}else if(cur == parent.left) {parent.left = cur.right;}else {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 {parent.right = cur.left;}}else {//第一种:找左边最大值/*TreeNode target = cur.left;TreeNode targetParent = cur;while(target.right != null) {targetParent = target;target = target.right;}cur.val = target.val;if(targetParent.left == target) {targetParent.right = target.left;}else {targetParent.left = target.left;}*///第二种:找右边最小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.2.4 完整代码
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;public void insert(int key) {TreeNode node = new TreeNode(key);if(root == null) {root = node;return;}TreeNode parent = null;TreeNode cur = root;while(cur != null) {if (cur.val == key) {return;} else if (cur.val > key) {parent = cur;cur = cur.left;} else {parent = cur;cur = cur.right;}}if(parent.val > key) {parent.left = node;}else {parent.right = node;}}/*** 时间复杂度:* 最好情况:O(logN)* 最坏情况:O(N)* @param key* @return*/public TreeNode search(int key) {TreeNode cur = root;while(cur != null) {if(cur.val == key) {return cur;}else if(cur.val > key) {cur = cur.left;}else {cur = cur.right;}}return null;}public void remove(int key) {TreeNode cur = root;TreeNode parent = null;while(cur != null) {if(key < cur.val) {parent = cur;cur = cur.left;}else if(key > cur.val) {parent = cur;cur = cur.right;}else {removeNode(parent,cur);return;}}}private void removeNode(TreeNode parent, TreeNode cur) {if(cur.left == null) {if(cur == root) {root = root.right;}else if(cur == parent.left) {parent.left = cur.right;}else {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 {parent.right = cur.left;}}else {//第一种:找左边最大值/*TreeNode target = cur.left;TreeNode targetParent = cur;while(target.right != null) {targetParent = target;target = target.right;}cur.val = target.val;if(targetParent.left == target) {targetParent.right = target.left;}else {targetParent.left = target.left;}*///第二种:找右边最小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;}}}
}
public static void main1(String[] args) {BinarySearchTree bst = new BinarySearchTree();bst.insert(14);bst.insert(5);bst.insert(1);bst.insert(9);bst.insert(17);bst.insert(12);bst.insert(7);bst.insert(6);bst.insert(10);BinarySearchTree.TreeNode ret = bst.search(9);System.out.println(ret.val);bst.remove(9);}
1.3 性能分析
插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。
对有n个节点的二叉树,若每个元素查找元素的概率相等,则二叉搜索树平均查找时间是节点在二叉搜索树的深度的函数,即节点越深,则比较的次数越多。
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
最优情况下,即二叉搜索树为完全叉树,其平均比较次数为: log₂N
最差情况下,即二叉搜索树为单只树,其平均比较次数为: N/2
所以,为了解决二叉搜索树出现单只树的情况,出现了按照次序插入关键码,直接找到对应的元素,为搜索。
1.4 和Java类集的关系
TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set;实际上用的是红黑树,而红黑树是一棵近似平衡的 二叉搜索树,即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证。
2. 搜索
2.1 概念
Map和set是一种专门用来进行搜索的容器或者数据结构,其搜索的效率与其具体的实例化子类有关。
之前常用的搜索方法有:
- 直接遍历,时间复杂度为O(N),元素如果比较多,效率就会非常慢
- 二分查找,时间复杂度为,但搜索前必须要求序列是有序的
上述排序比较适合静态类型的查找,即一般不会对区间进行插入和删除操作了,而现实中的查找比如:
- 根据姓名查询考试成绩
- 通讯录,即根据姓名查询联系方式
- 不重复集合,即需要先搜索关键字是否已经在集合中
可能在查找时进行一些插入和删除的操作,即动态查找,那上述两种方式就不太适合了,本节介绍的Map和Set是 一种适合动态查找的集合容器。
2.2 模型
一般把搜索的数据称为关键字(Key),和关键字对应的称为值(Value),将其称之为Key-value的键值对,所以 模型会有两种:
1. 纯 key 模型,比如:
- 有一个英文词典,快速查找一个单词是否在词典中
- 快速查找某个名字在不在通讯录中
2. Key-Value 模型,比如:
- 统计文件中每个单词出现的次数,统计结果是每个单词都有与其对应的次数: <单词单词出现的次数>
- 梁山好汉的江湖绰号:每个好汉都有自己的江湖绰号
而Map中存储的就是key-value的键值对,Set中只存储了Key。
3. Map的使用
Map是一个接口类,该类没有继承Collection,该类中存储的是<K,V>结构的键值对,并且K一定是唯一的,不能重复的。
3.1 Map的常用方法
3.1.1 V put(K key, V value)
设置 key 对应的 value
Map<String,Integer> treeMap = new TreeMap<>();treeMap.put("hello",3);treeMap.put("world",2);treeMap.put("beautiful",4);treeMap.put("bird",1);System.out.println("treeMap:" + treeMap);
运行结果:
3.1.2 V get(Object key)
返回 key 对应的 value
// 如果key存在,返回key所对应的value
// 如果key不存在,返回null
System.out.println(treeMap.get("bird"));
运行结果:
3.1.3 V getOrDefault(Object key, V defaultValue)
返回 key 对应的 value,key 不存在,返回默认值
//如果key存在,返回与key所对应的value,如果key不存在,返回一个默认值
System.out.println(treeMap.getOrDefault("milk", 20));
运行结果:
3.1.4 V remove(Object key)
删除 key 对应的映射关系
//删除key对应的映射关系
System.out.println("删除前的treeMap:" + treeMap);
Integer value = treeMap.remove("beautiful");
System.out.println(value);
System.out.println("删除key='beautiful'后的treeMap:" + treeMap);
运行结果:
3.1.5 Set keySet()
返回所有 key 的不重复集合
//keySet是将map中的key放在Set中返回的
for(String str : treeMap.keySet()) {System.out.print(str + " ");
}
System.out.println();
System.out.println("keys:" + treeMap.keySet());
运行结果:
3.1.6 Collection values()
返回所有 value 的可重复集合
//values()是将map中的value放在collect的一个集合中返回的
for(Integer num : treeMap.values()) {System.out.print(num + " ");
}
System.out.println();
System.out.println("values:" + treeMap.values());
运行结果:
3.1.7 boolean containsKey(Object key)
判断是否包含 key
System.out.println(treeMap.containsKey("bird"));
运行结果:
3.1.8 boolean containsValue(Object value)
判断是否包含 value
System.out.println(treeMap.containsValue(3));
运行结果:
3.1.9 Set<Map.Entry<K,V>>entrySet()
返回所有的 key-value 映射关系 学习3.2
3.2 Map.Entry<K,V>
Map.Entry<K,V>是Map内部用来实现存放<K,V>键值对映射关系的内部类,其方法如下:
其中前三个是最常使用到的方法。需要注意的是Map.Entry<K,V>中没有提供设置Key的方法。
// entrySet(): 将Map中的键值对放在Set中返回了
Set<Map.Entry<String,Integer>> entrySet = treeMap.entrySet();
for(Map.Entry<String,Integer> entry : entrySet ) {System.out.println(entry.getKey() + "-->" + entry.getValue());}
System.out.println("key/value映射:" + treeMap.entrySet());
运行结果:
需要我们注意的是:
- Map是一个接口,不能直接实例化对象,如果要实例化对象只能实例化其实现类TreeMap或者HashMap。
- Map中存放的键值对的key是唯一的,value可以重复
- TreeMap中插入键值对时,Key不能为空,否则会抛出NullPointerException异常,value值可以为空;HashMap中插入键值对时,Key和value都可以为空。
- Map中Key可以分离出来,存储在Set中进行访问,因为Key是不能重复的
- Map中的value可以分离出来存储到collection的任何一个集合中,因为value可能有重复的
- Map中的Key不能直接修改,只能将Key删除,再重新插入,value修改可以直接在原来的基础上进行覆盖。
3.4 TreeMap和HashMap的区别
Map底层结构 | TreeMap | HashMap |
---|---|---|
底层结构 | 红黑树 | 哈希桶 |
插入/删除/查找时间复杂度 | O(log₂N) | O(1) |
是否有序 | 关于Key有序 | 无序 |
线程安全 | 不安全 | 不安全 |
插入/删除/查找区别 | 需要进行元素之间的比较 | 通过哈希函数计算出哈希地址 |
比较与覆写 | key必须是可比较的,不然会抛出ClassCastException异常 | 自定义类型需要重写equals和HashCode方法 |
应用场景 | 需要key有序的情况下 | key是否有序不关心,需要更高的时间性能 |
3.5 TreeMap的使用
import java.util.TreeMap;import java.util.Map;public static void TestMap(){Map<String, String> m = new TreeMap<>();// put(key, value):插入key-value的键值对// 如果key不存在,会将key-value的键值对插入到map中,返回nullm.put("林冲", "豹子头");m.put("鲁智深", "花和尚");m.put("武松", "行者");m.put("宋江", "及时雨");String str = m.put("李逵", "黑旋风");System.out.println(m.size());System.out.println(m);// put(key,value): 注意key不能为空,但是value可以为空// key如果为空,会抛出空指针异常//m.put(null, "花名");str = m.put("无名", null);System.out.println(m.size());// put(key, value):// 如果key存在,会使用value替换原来key所对应的value,返回旧valuestr = m.put("李逵", "铁牛");// get(key): 返回key所对应的value// 如果key存在,返回key所对应的value// 如果key不存在,返回nullSystem.out.println(m.get("鲁智深"));System.out.println(m.get("史进"));//GetOrDefault(): 如果key存在,返回与key所对应的value,如果key不存在,返回一个默认值System.out.println(m.getOrDefault("李逵", "铁牛"));System.out.println(m.getOrDefault("史进", "九纹龙"));System.out.println(m.size());//containKey(key):检测key是否包含在Map中,时间复杂度:O(logN)// 按照红黑树的性质来进行查找// 找到返回true,否则返回falseSystem.out.println(m.containsKey("林冲"));System.out.println(m.containsKey("史进"));// containValue(value): 检测value是否包含在Map中,时间复杂度: O(N)// 找到返回true,否则返回falseSystem.out.println(m.containsValue("豹子头"));System.out.println(m.containsValue("九纹龙"));// 打印所有的key// keySet是将map中的key防止在Set中返回的for(String s : m.keySet()){System.out.print(s + " ");}System.out.println();// 打印所有的value// values()是将map中的value放在collect的一个集合中返回的for(String s : m.values()){System.out.print(s + " ");}System.out.println();// 打印所有的键值对// entrySet(): 将Map中的键值对放在Set中返回了for(Map.Entry<String, String> entry : m.entrySet()){System.out.println(entry.getKey() + "--->" + entry.getValue());}System.out.println();}
4. Set的使用
根据上图可以发现,Map中存储了key-value的键值对,Set是继承自Collection的接口类,Set中只存储了Key。
4.1 常用方法说明
4.1.1 boolean add(E e)
添加元素,但重复元素不会被添加成功
Set<String> treeSet = new TreeSet<>();
treeSet.add("windows");
treeSet.add("unix");
treeSet.add("Linux");
System.out.println("treeSet:" + treeSet);
运行结果:
4.1.2 boolean addAll(Collection<? extends E> c)
将集合c中的元素添加到set中,可以达到去重的效果
Set<String> set = new TreeSet<>();
set.add("mac OS");
System.out.println("set添加之前:" + set);
set.addAll(treeSet);
System.out.println("set添加之后:" + set);
运行结果:
4.1.3 boolean containsAll(Collection<?> c)
集合c中的元素是否在set中全部存在,是返回true,否则返回 false
System.out.println("set中是否包含treeSet中的所有元素: "+set.containsAll(treeSet));
运行结果:
4.1.4 boolean contains(Object o)
判断 o 是否在集合中
boolean res = set.contains("Linux");
System.out.println(res);
运行结果:
4.1.5 boolean remove(Object o)
删除集合中的 o
boolean rm = set.remove("mac OS");
System.out.println("是否删除mac Os:" + rm);
System.out.println("set删除mac Os之后" + set);
运行结果:
4.1.6 int size()
返回set中元素的个数
System.out.println(set.size());
运行结果:
4.1.7 void clear()
清空集合
treeSet.clear();
System.out.println("set清理之后:" + treeSet);
运行结果:
4.1.8 boolean isEmpty()
检测set是否为空,空返回true,否则返回false
System.out.println(treeSet.isEmpty());
运行结果:
我们需要注意是:
- Set是继承了Collection的一个接口类
- Set中只存储了Key,并要求Key唯一
- TreeSet的底层是使用Map来实现的,其使用key与Object的一个默认对象作为键值对插入到Map中的
- Set最大的功能就是对集合中的元素进行去重
- 实现Set接口的常用类有TreeSet和HashSet,还有一个LinkedHashSet,LinkedHashSet是在HashSet的基础 上维护了一个双向链表来记录元素的插入次序。
- Set中的Key不能修改,如果要修改,先将原来的删除掉,然后再重新插入
- TreeSet中不能插入null的key,HashSet可以。
4.2 TreeSet和HashSet的区别
Set底层结构 | TreeSet | HashSet |
---|---|---|
底层结构 | 红黑树 | 哈希桶 |
插入/删除/查找时间复杂度 | O(log₂N) | O(1) |
是否有序 | 关于Key有序 | 无序 |
线程安全 | 不安全 | 不安全 |
插入/删除/查找区别 | 按照红黑树的特性进行插入和删除 | 先计算Key的哈希地址,然后进行插入和删除 |
比较与覆写 | Key必须是能够比较的,否则会抛出ClassCastException异常 | 自定义类型需要重写equals和hashCode方法 |
应用场景 | 需要Key有序情境下 | Key否有序无关,但需要更高的时间性能 |
4.3 TreeSet的使用
4.3.1 key为String类型
import java.util.TreeSet;import java.util.Iterator;import java.util.Set;public static void TestSet(){Set<String> s = new TreeSet<>();// add(key): 如果key不存在,则插入,返回ture// 如果key存在,返回falseboolean isIn = s.add("apple");s.add("orange");s.add("peach");s.add("banana");System.out.println(s.size());System.out.println(s);isIn = s.add("apple");// add(key): key如果是空,抛出空指针异常//s.add(null);// contains(key): 如果key存在,返回true,否则返回falseSystem.out.println(s.contains("apple"));System.out.println(s.contains("watermelen"));// remove(key): key存在,删除成功返回true//key不存在,删除失败返回false//key为空,抛出空指针异常s.remove("apple");System.out.println(s);s.remove("watermelen");System.out.println(s);Iterator<String> it = s.iterator();while(it.hasNext()){System.out.print(it.next() + " ");}System.out.println();}
4.3.2 key为自定义类型
class Student implements Comparable<Student> {public String name;public int age;public Student(String name, int age) {this.name = name;this.age = age;}@Overridepublic int compareTo(Student o) {return this.name.compareTo(o.name);}
}public class Test {public static void main(String[] args) {Set<Student> set = new TreeSet<>();set.add(new Student("zhangsan",3));set.add(new Student("wangwu",4));set.add(new Student("lisi",5));Student[] arr = set.toArray(new Student[set.size()]);System.out.println("Elements in array:");for(Student stu : arr) {System.out.println(stu.name + " " + stu.age);}Set<String> s = new TreeSet<>();s.add("hello");s.add("world");s.add("bird");Iterator<String> iterator = s.iterator();while(iterator.hasNext()) {System.out.print(iterator.next() + " ");}System.out.println();}
}
运行结果: