java数据结构之基于红黑树的TreeMap的使用及实现解读

一、红黑树说明

1.红黑树的结构

红黑树是一种特殊的二叉树,它有以下性质:

  • 每一个节点或着成红色,或着成红色
  • 根是黑色的
  • 如果一个节点是红色的,那么它的子节点必须是黑色的(如果这个节点是叶子节点,即没有子节点,不需要满足这个条件,这是在有子节点的情况下)
  • 从根节点到叶子节点的每一条路径必须包含相同数目的黑色节点

红黑树的结构

2.将普通二叉树变成红黑树
  • 将节点着色或改变颜色
  • 将节点进行旋转操作

二、TreeMap的使用

1.TreeMap与其他集合结构的关系以及它拥有的方法

TreeMap与其他集合结构的关系

TreeMap包含的方法

2.TreeMap的实例化
  • new TreeMap() : 直接实例化,采用默认的比较器
  • new TreeMap(Comparator comparator):通过一个指定的比较器来实例化
  • new TreeMap(Map m) : 通过一个Map对象来实例化
  • new TreeMap(SortedMap m): 通过一个SortedMap对象来实例化
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. Map<Integer, String> bookMap = new HashMap<Integer, String>(2);
  3. bookMap.put(25, "Mybatis");
  4. bookMap.put(36, "Dubbo");
  5. TreeMap<Integer, String> bookTree = new TreeMap<Integer, String>(bookMap);
  6. System.out.println(bookTree); //{25=Mybatis, 36=Dubbo}
3.containsKey:是否包含某个key
  • containsKey(Object k)
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(2, "算法");
  3. tree.put(3, "JAVA");
  4. tree.put(1, "数据结构");
  5. tree.put(100, "Docker虚拟化容器");
  6. tree.put(8, "Spring");
  7. tree.put(7, "Zookeeper");
  8. System.out.println(tree.containsKey(3)); // true
  9. System.out.println(tree.containsKey(99)); // false
4.containsValue:是否包含某个值
  • containsValue(Object v)
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(2, "算法");
  3. tree.put(3, "JAVA");
  4. System.out.println(tree.containsValue("JAVA")); //true
  5. System.out.println(tree.containsValue("Golang")); //false
5.get:获取某个key的值
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(2, "算法");
  3. tree.put(3, "JAVA");
  4. tree.put(1, "数据结构");
  5. tree.put(100, "Docker虚拟化容器");
  6. tree.put(8, "Spring");
  7. tree.put(7, "Zookeeper");
  8. System.out.println(tree.get(8)); //Spring
  9. System.out.println(tree.get(9)); //null
6.put:设置某个key的值
  • put(K key, V value)
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(2, "算法");
7.putAll:批量设置某些key对应的值
  • putAll(Map map)
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(2, "算法");
  3. tree.put(3, "JAVA");
  4. Map<Integer, String> testMap = new HashMap<Integer, String>(2);
  5. testMap.put(1, "数据结构");
  6. testMap.put(100, "Docker虚拟化容器");
  7. tree.putAll(testMap); //{1=数据结构, 2=算法, 3=JAVA, 100=Docker虚拟化容器}
8.remove:删除某个key对应的值
  • remove(Object key):通过key来删除节点
  • remove(Object key, Object value):通过键和值两个条件来删除节点(如果key或者value不满足,则删除失败)
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(2, "算法");
  3. tree.put(3, "JAVA");
  4. tree.put(1, "数据结构");
  5. tree.remove(2);
  6. tree.remove(3, "PHP"); //{1=数据结构, 3=JAVA}
9.keySet:获取树的所有节点的key集合
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(2, "算法");
  3. tree.put(3, "JAVA");
  4. tree.put(1, "数据结构");
  5. Set<Integer> keys = tree.keySet();
  6. System.out.println(keys); // [1, 2, 3]
10.entrySet:获取所有节点集合(包括键和值)
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(9, "算法");
  3. tree.put(3, "JAVA");
  4. tree.put(1, "数据结构");
  5. System.out.println(tree.entrySet()); //[1=数据结构, 3=JAVA, 9=算法]
11.values:获取所有节点的值的集合
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(9, "算法");
  3. tree.put(3, "JAVA");
  4. tree.put(1, "数据结构");
  5. System.out.println(tree.values()); //[数据结构, JAVA, 算法]
12.replace:将指定的key的值替换成新的值

它与put不同的是,当key不存在时,不会执行插入操作

  • replace(K key):替换指定key的值
  • replace(K key, V oldValue, V newValue):将指定key和oldValue的替换成新的值
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(9, "算法");
  3. tree.put(3, "JAVA");
  4. tree.put(5, "数据结构");
  5. tree.replace(3, "Golang"); //{3=Golang, 5=数据结构, 9=算法}
  6. tree.replace(1, "Python"); //{3=Golang, 5=数据结构, 9=算法}
  7. tree.replace(5, "数据结构", "Java数据结构"); //{3=Golang, 5=Java数据结构, 9=算法}
  8. tree.replace(5, "结构", "库"); //{3=Golang, 5=Java数据结构, 9=算法}
13.firstKey:获取树节点集合中的第一个键(因为它是有序的,所以也是最小的节点的键)
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(9, "算法");
  3. tree.put(3, "JAVA");
  4. tree.put(5, "数据结构");
  5. System.out.println(tree.firstKey()); //3
14.lowerKey:查找与指定键更少的一个键
  • lowerKey(K key):在所有节点中查找比key更小而且最接近的一个key
  1. TreeMap<Integer, String> tree = new TreeMap<Integer, String>();
  2. tree.put(9, "算法");
  3. tree.put(3, "JAVA");
  4. tree.put(5, "数据结构");
  5. System.out.println(tree.lowerKey(5)); //3
  6. System.out.println(tree.lowerKey(8)); //5

三、TreeMap的实现原理解读

1.TreeMap的组成

TreeMap本质上是一颗二叉树,它由0至多个树节点组成,而它与普通的二叉树的区别就是,它的节点不仅有数据,指向左子树的指针和右子树的指针,还有一个节点的颜色,并且满足红黑的一些特点

(1).TreeMap对象的组成部分
  • comparator : 元素比较器对象
  • size : 节点的数目
  • root : 根节点
(2).TreeMap节点(TreeMap.Entry对象)的特点
  • key : 节点的键
  • value : 节点的值
  • left : 节点的左子树节点
  • right : 节点的右子树节点
  • parent : 节点的父节点
  • color : 节点的颜色
2.TreeMap的实例化
  1. //通过一个指定的map来初始化,将map中的元素添加到当前树中
  2. public TreeMap(Map<? extends K, ? extends V> m) {
  3. comparator = null;
  4. //通过putAll来实现(putAll方法后面会讲解)
  5. putAll(m);
  6. }
3.TreeMap节点的插入和更新put
  • 如果是空树,即根结果为null
    • 插入的节点就为根节点
  • 如果是非空树
    • (1)对应的key是否存在,存在则更新值
    • (2)不存在,则插入值,并旋转,以满足红黑树的条件
  1. public V put(K key, V value) {
  2. //定义一个指针节点t,初始指向根节点
  3. Entry<K,V> t = root;
  4. //如果是空树,即根节点为null
  5. if (t == null) {
  6. compare(key, key); // type (and possibly null) check
  7. //插入的节点就是新的根节点
  8. root = new Entry<>(key, value, null);
  9. size = 1;
  10. modCount++;
  11. return null;
  12. }
  13. //定义一个比较方向
  14. int cmp;
  15. //父节点指针
  16. Entry<K,V> parent;
  17. // split comparator and comparable paths
  18. //比较器
  19. Comparator<? super K> cpr = comparator;
  20. //如果有指定的比较器
  21. if (cpr != null) {
  22. do {
  23. parent = t;
  24. //当前插入的key与父节点的key大小作对比
  25. cmp = cpr.compare(key, t.key);
  26. //如果比父节点的key小,则插入的节点往左子树走
  27. if (cmp < 0)
  28. t = t.left;
  29. //如果比父节点的key大,则插入的节点往右子树走
  30. else if (cmp > 0)
  31. t = t.right;
  32. //如果相等,即存在相同key的旧节点,更新其值
  33. else
  34. return t.setValue(value);
  35. } while (t != null);
  36. }
  37. else {
  38. //如果没有指定的比较器,则使用具体对象的比较方法
  39. if (key == null)
  40. throw new NullPointerException();
  41. @SuppressWarnings("unchecked")
  42. Comparable<? super K> k = (Comparable<? super K>) key;
  43. do {
  44. parent = t;
  45. cmp = k.compareTo(t.key);
  46. if (cmp < 0)
  47. t = t.left;
  48. else if (cmp > 0)
  49. t = t.right;
  50. else
  51. return t.setValue(value);
  52. } while (t != null);
  53. }
  54. //如果插入的值是新节点,那么先生成一个新节点
  55. Entry<K,V> e = new Entry<>(key, value, parent);
  56. //如果插入节点key比父节点小,则插入到父节点的左子树上
  57. if (cmp < 0)
  58. parent.left = e;
  59. else
  60. //如果插入节点key比父节点大,则插入到父节点的右子树上
  61. parent.right = e;
  62. //红黑树着色和旋转,使之成为合法的红黑树
  63. fixAfterInsertion(e);
  64. size++;
  65. modCount++;
  66. return null;
  67. }
4.TreeMap节点的删除remove
  1. public V remove(Object key) {
  2. //1.通过key查找到相应的节点
  3. Entry<K,V> p = getEntry(key);
  4. //2.如果节点不存在,则直接返回
  5. if (p == null)
  6. return null;
  7. //3.获取删除节点的旧值
  8. V oldValue = p.value;
  9. //4.删除节点(通过找到前序后继节点来替换和红黑树重新着色与扭转)
  10. deleteEntry(p);
  11. return oldValue;
  12. }
5.TreeMap节点的查找get
  • 通过二叉树查找方法进行查找
    • 从根节点开始查找比较,如果比当前节点小,则进入左子树查找比较
    • 如果比当前节点大,则进入右子树进行查找比较,直到找到对应的key为止
  1. public V get(Object key) {
  2. /*------------------------------------------------------------
  3. final Entry<K,V> getEntry(Object key) {
  4. //如果有指定的比较器,则使用比较器来查找元素节点
  5. if (comparator != null)
  6. return getEntryUsingComparator(key);
  7. if (key == null)
  8. throw new NullPointerException();
  9. @SuppressWarnings("unchecked")
  10. //使用key对应的具体的数据类型的比较方法来比较
  11.  Comparable<? super K> k = (Comparable<? super K>) key;
  12.  //从根节点开始查找
  13. Entry<K,V> p = root;
  14. while (p != null) {
  15. int cmp = k.compareTo(p.key);
  16. if (cmp < 0)
  17. p = p.left;
  18. else if (cmp > 0)
  19. p = p.right;
  20. else
  21. return p;
  22. }
  23. return null;
  24. }
  25. -------------------------------------------------------------*/
  26. Entry<K,V> p = getEntry(key);
  27. return (p==null ? null : p.value);
  28. }
6.ContainsKey的实现解读

原理:通过key在二叉树上遍历查找到key对应的节点,如果能找到,则说明key存在,否则key不存在

  1. public boolean containsKey(Object key) {
  2. /*--------------------------------------------------------------------
  3. //通过比较器来查找节点
  4. final Entry<K,V> getEntryUsingComparator(Object key) {
  5. @SuppressWarnings("unchecked")
  6. K k = (K) key;
  7. Comparator<? super K> cpr = comparator;
  8. if (cpr != null) {
  9. //定义一个查找指针,从根节点开始查找
  10. Entry<K,V> p = root;
  11. while (p != null) {
  12. //指针遍历的对象的key与当前要查找的key进行比较
  13. int cmp = cpr.compare(k, p.key);
  14. //如果比当前指针小,则在左子树
  15. if (cmp < 0)
  16. p = p.left;
  17. //如果比当前指针大,则在右子树
  18. else if (cmp > 0)
  19. p = p.right;
  20. //如果相同,直接返回对象
  21. else
  22. return p;
  23. }
  24. }
  25. return null;
  26. }
  27. //根据某个key查找key对应的节点对象
  28. final Entry<K,V> getEntry(Object key) {
  29. // 如果在实例化的时候指定了比较器,直接使用
  30. if (comparator != null)
  31. return getEntryUsingComparator(key);
  32. if (key == null)
  33. throw new NullPointerException();
  34. @SuppressWarnings("unchecked")
  35. Comparable<? super K> k = (Comparable<? super K>) key;
  36. //定义一个用于遍历的指针,开始从根节点开始查找
  37. Entry<K,V> p = root;
  38. while (p != null) {
  39. //比较当前指针与要查找的节点的key进行对比(根据其实际的类型调用各自的compareTo方法)
  40. int cmp = k.compareTo(p.key);
  41. //如果比当前指针小,则在当前节点的左子树上
  42. if (cmp < 0)
  43. p = p.left;
  44. //如果比当前的指针大,则在当前节点的右子树上
  45. else if (cmp > 0)
  46. p = p.right;
  47. //如果相等,也直接返回
  48. else
  49. return p;
  50. }
  51. return null;
  52. }
  53. ---------------------------------------------------------------------*/
  54. return getEntry(key) != null;
  55. }