devbox
天景科技苑
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java集合--TreeMap完全解析_treemap sizes

作者：天景科技苑 | 2024-08-19 19:07:18

赞

踩

treemap sizes

https://www.jianshu.com/p/2dcff3634326

4 TreeMap

上一篇，介绍了集合框架中的HashMap对象，主要讲述了HashMap的底层实现和基本操作。本篇，让我们继续来学习Map集合，今天的主角是TreeMap。

相比于HashMap来说，TreeMap理解起来更为复杂，你做好准备了吗？

4.1 TreeMap

在Map集合框架中，除了HashMap以外，TreeMap也是我们工作中常用到的集合对象之一。

与HashMap相比，TreeMap是一个能比较元素大小的Map集合，会对传入的key进行了大小排序。其中，可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序；

不同于HashMap的哈希映射，TreeMap底层实现了树形结构，至于具体形态，你可以简单的理解为一颗倒过来的树---根在上--叶在下。如果用计算机术语来说的话，TreeMap实现了红黑树的结构，形成了一颗二叉树。

至于什么是二叉树，什么是红黑树，我们后面再谈，你现在只需要记住它是一颗倒过来的树，就OK了。

TreeMap继承于AbstractMap，实现了Map, Cloneable, NavigableMap, Serializable接口。

(1)TreeMap 继承于AbstractMap，而AbstractMap实现了Map接口，并实现了Map接口中定义的方法，减少了其子类继承的复杂度；

(2)TreeMap 实现了Map接口，成为Map框架中的一员，可以包含着key--value形式的元素；

(3)TreeMap 实现了NavigableMap接口，意味着拥有了更强的元素搜索能力；

(4)TreeMap 实现了Cloneable接口，实现了clone()方法，可以被克隆；

(5)TreeMap 实现了Java.io.Serializable接口，支持序列化操作，可通过Hessian协议进行传输；

对于Cloneable, Serializable来说，我们再熟悉不过，基本上Java集合框架中的每一个类都会实现这2个接口，而NavigableMap接口是干什么的，它定义了什么样的功能？接下来，我们就通过NavigableMap的源码来看下！

根据上面的截图，我们首先介绍下NavigableMap体系中的SortedMap接口：

对于SortedMap来说，该类是TreeMap体系中的父接口，也是区别于HashMap体系最关键的一个接口。

主要原因就是SortedMap接口中定义的第一个方法---Comparator<? super K> comparator()；

该方法决定了TreeMap体系的走向，有了比较器，就可以对插入的元素进行排序了；

  1. public interface SortedMap<K,V> extends Map<K,V> {
  2.     
  3.     //返回元素比较器。如果是自然顺序，则返回null；
  4.     Comparator<? super K> comparator();
  5.     
  6.     //返回从fromKey到toKey的集合：含头不含尾
  7.     java.util.SortedMap<K,V> subMap(K fromKey, K toKey);
  8.  
  9.     //返回从头到toKey的集合：不包含toKey
  10.     java.util.SortedMap<K,V> headMap(K toKey);
  11.  
  12.     //返回从fromKey到结尾的集合：包含fromKey
  13.     java.util.SortedMap<K,V> tailMap(K fromKey);
  14.     
  15.     //返回集合中的第一个元素：
  16.     K firstKey();
  17.    
  18.     //返回集合中的最后一个元素：
  19.     K lastKey();
  20.     
  21.     //返回集合中所有key的集合：
  22.     Set<K> keySet();
  23.     
  24.     //返回集合中所有value的集合：
  25.     Collection<V> values();
  26.     
  27.     //返回集合中的元素映射：
  28.     Set<Map.Entry<K, V>> entrySet();
  29. }

上面介绍了SortedMap接口，而NavigableMap接口又是对SortedMap进一步的扩展：主要增加了对集合内元素的搜索获取操作，例如：返回集合中某一区间内的元素、返回小于大于某一值的元素等类似操作。

  1. public interface NavigableMap<K,V> extends SortedMap<K,V> {
  2.  
  3.     //返回小于key的第一个元素：
  4.     Map.Entry<K,V> lowerEntry(K key);
  5.  
  6.     //返回小于key的第一个键：
  7.     K lowerKey(K key);
  8.  
  9.     //返回小于等于key的第一个元素：
  10.     Map.Entry<K,V> floorEntry(K key);
  11.  
  12.     //返回小于等于key的第一个键：
  13.     K floorKey(K key);
  14.  
  15.     //返回大于或者等于key的第一个元素：
  16.     Map.Entry<K,V> ceilingEntry(K key);
  17.  
  18.     //返回大于或者等于key的第一个键：
  19.     K ceilingKey(K key);
  20.  
  21.     //返回大于key的第一个元素：
  22.     Map.Entry<K,V> higherEntry(K key);
  23.  
  24.     //返回大于key的第一个键：
  25.     K higherKey(K key);
  26.  
  27.     //返回集合中第一个元素：
  28.     Map.Entry<K,V> firstEntry();
  29.  
  30.     //返回集合中最后一个元素：
  31.     Map.Entry<K,V> lastEntry();
  32.  
  33.     //返回集合中第一个元素，并从集合中删除：
  34.     Map.Entry<K,V> pollFirstEntry();
  35.  
  36.     //返回集合中最后一个元素，并从集合中删除：
  37.     Map.Entry<K,V> pollLastEntry();
  38.  
  39.     //返回倒序的Map集合：
  40.     java.util.NavigableMap<K,V> descendingMap();
  41.  
  42.     NavigableSet<K> navigableKeySet();
  43.  
  44.     //返回Map集合中倒序的Key组成的Set集合：
  45.     NavigableSet<K> descendingKeySet();
  46.  
  47.     java.util.NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
  48.                                        K toKey, boolean toInclusive);
  49.  
  50.     java.util.NavigableMap<K,V> headMap(K toKey, boolean inclusive);
  51.  
  52.     java.util.NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
  53.  
  54.     SortedMap<K,V> subMap(K fromKey, K toKey);
  55.  
  56.     SortedMap<K,V> headMap(K toKey);
  57.  
  58.     SortedMap<K,V> tailMap(K fromKey);
  59. }

其实，NavigableMap的目的很简单、很直接，就是增强了对集合内元素的搜索、获取的功能，当子类TreeMap实现时，自然获取以上的功能；

TreeMap具有如下特点：

  • 不允许出现重复的key；

  • 可以插入null键，null值；

  • 可以对元素进行排序；

  • 无序集合（插入和遍历顺序不一致）；

4.2 TreeMap基本操作

  1. public class TreeMapTest {
  2.     public static void main(String[] agrs){
  3.         //创建TreeMap对象：
  4.         TreeMap<String,Integer> treeMap = new TreeMap<String,Integer>();
  5.         System.out.println("初始化后,TreeMap元素个数为：" + treeMap.size());
  6.  
  7.         //新增元素:
  8.         treeMap.put("hello",1);
  9.         treeMap.put("world",2);
  10.         treeMap.put("my",3);
  11.         treeMap.put("name",4);
  12.         treeMap.put("is",5);
  13.         treeMap.put("jiaboyan",6);
  14.         treeMap.put("i",6);
  15.         treeMap.put("am",6);
  16.         treeMap.put("a",6);
  17.         treeMap.put("developer",6);
  18.         System.out.println("添加元素后,TreeMap元素个数为：" + treeMap.size());
  19.  
  20.         //遍历元素：
  21.         Set<Map.Entry<String,Integer>> entrySet = treeMap.entrySet();
  22.         for(Map.Entry<String,Integer> entry : entrySet){
  23.             String key = entry.getKey();
  24.             Integer value = entry.getValue();
  25.             System.out.println("TreeMap元素的key:"+key+",value:"+value);
  26.         }
  27.  
  28.         //获取所有的key：
  29.         Set<String> keySet = treeMap.keySet();
  30.         for(String strKey:keySet){
  31.             System.out.println("TreeMap集合中的key:"+strKey);
  32.         }
  33.  
  34.         //获取所有的value:
  35.         Collection<Integer> valueList = treeMap.values();
  36.         for(Integer intValue:valueList){
  37.             System.out.println("TreeMap集合中的value:" + intValue);
  38.         }
  39.  
  40.         //获取元素：
  41.         Integer getValue = treeMap.get("jiaboyan");//获取集合内元素key为"jiaboyan"的值
  42.         String firstKey = treeMap.firstKey();//获取集合内第一个元素
  43.         String lastKey =treeMap.lastKey();//获取集合内最后一个元素
  44.         String lowerKey =treeMap.lowerKey("jiaboyan");//获取集合内的key小于"jiaboyan"的key
  45.         String ceilingKey =treeMap.ceilingKey("jiaboyan");//获取集合内的key大于等于"jiaboyan"的key
  46.         SortedMap<String,Integer> sortedMap =treeMap.subMap("a","my");//获取集合的key从"a"到"jiaboyan"的元素
  47.  
  48.         //删除元素：
  49.         Integer removeValue = treeMap.remove("jiaboyan");//删除集合中key为"jiaboyan"的元素
  50.         treeMap.clear(); //清空集合元素：
  51.  
  52.         //判断方法：
  53.         boolean isEmpty = treeMap.isEmpty();//判断集合是否为空
  54.         boolean isContain = treeMap.containsKey("jiaboyan");//判断集合的key中是否包含"jiaboyan"
  55.     }
  56. }

4.3 TreeMap排序

上一节，通过代码展示出TreeMap简单使用。而早在第一小节，笔者就说过TreeMap是一个可以对元素进行排序的集合，那么究竟怎么排序呢？

（1）使用元素自然排序

在使用自然顺序排序时候，需要区分两种情况：一种是Jdk定义的对象，一种是我们应用自己定义的对象；

  1. public class SortedTest implements Comparable<SortedTest> {
  2.     private int age;
  3.     public SortedTest(int age){
  4.         this.age = age;
  5.     }
  6.     public int getAge() {
  7.         return age;
  8.     }
  9.     public void setAge(int age) {
  10.         this.age = age;
  11.     }
  12.     //自定义对象，实现compareTo(T o)方法：
  13.     public int compareTo(SortedTest sortedTest) {
  14.         int num = this.age - sortedTest.getAge();
  15.         //为0时候，两者相同：
  16.         if(num==0){
  17.             return 0;
  18.         //大于0时，传入的参数小：
  19.         }else if(num>0){
  20.             return 1;
  21.         //小于0时，传入的参数大：
  22.         }else{
  23.             return -1;
  24.         }
  25.     }
  26. }
  27.  
  28. public class TreeMapTest {
  29.     public static void main(String[] agrs){
  30.         //自然顺序比较
  31.         naturalSort();
  32.     }
  33.      //自然排序顺序：
  34.     public static void naturalSort(){
  35.         //第一种情况：Integer对象
  36.         TreeMap<Integer,String> treeMapFirst = new TreeMap<Integer, String>();
  37.         treeMapFirst.put(1,"jiaboyan");
  38.         treeMapFirst.put(6,"jiaboyan");
  39.         treeMapFirst.put(3,"jiaboyan");
  40.         treeMapFirst.put(10,"jiaboyan");
  41.         treeMapFirst.put(7,"jiaboyan");
  42.         treeMapFirst.put(13,"jiaboyan");
  43.         System.out.println(treeMapFirst.toString());
  44.  
  45.         //第二种情况:SortedTest对象
  46.         TreeMap<SortedTest,String> treeMapSecond = new TreeMap<SortedTest, String>();
  47.         treeMapSecond.put(new SortedTest(10),"jiaboyan");
  48.         treeMapSecond.put(new SortedTest(1),"jiaboyan");
  49.         treeMapSecond.put(new SortedTest(13),"jiaboyan");
  50.         treeMapSecond.put(new SortedTest(4),"jiaboyan");
  51.         treeMapSecond.put(new SortedTest(0),"jiaboyan");
  52.         treeMapSecond.put(new SortedTest(9),"jiaboyan");
  53.         System.out.println(treeMapSecond.toString());
  54.     }
  55. }

在自然顺序比较中，需要让被比较的元素实现Comparable接口，否则在向集合里添加元素时报："java.lang.ClassCastException: com.jiaboyan.collection.map.SortedTest cannot be cast to java.lang.Comparable"异常；

这是因为在调用put()方法时，会将传入的元素转化成Comparable类型对象，所以当你传入的元素没有实现Comparable接口时，就无法转换，遍会报错；

（2）使用自定义比较器排序

使用自定义比较器排序，需要在创建TreeMap对象时，将自定义比较器对象传入到TreeMap构造方法中；

自定义比较器对象，需要实现Comparator接口，并实现比较方法compare(T o1,T o2)；

值得一提的是，使用自定义比较器排序的话，被比较的对象无需再实现Comparable接口了；

  1. public class SortedTest {
  2.     private int age;
  3.     public SortedTest(int age){
  4.         this.age = age;
  5.     }
  6.     public int getAge() {
  7.         return age;
  8.     }
  9.     public void setAge(int age) {
  10.         this.age = age;
  11.     }
  12. }
  13. public class SortedTestComparator implements Comparator<SortedTest> {
  14.     //自定义比较器：实现compare(T o1,T o2)方法：
  15.     public int compare(SortedTest sortedTest1, SortedTest sortedTest2) {
  16.         int num = sortedTest1.getAge() - sortedTest2.getAge();
  17.         if(num==0){//为0时候，两者相同：
  18.             return 0;
  19.         }else if(num>0){//大于0时，后面的参数小：
  20.             return 1;
  21.         }else{//小于0时，前面的参数小：
  22.             return -1;
  23.         }
  24.     }
  25. }
  26.  
  27. public class TreeMapTest {
  28.     public static void main(String[] agrs){
  29.         //自定义顺序比较
  30.         customSort();
  31.     }
  32.     //自定义排序顺序:
  33.     public static void customSort(){
  34.         TreeMap<SortedTest,String> treeMap = new TreeMap<SortedTest, String>(new SortedTestComparator());
  35.         treeMap.put(new SortedTest(10),"hello");
  36.         treeMap.put(new SortedTest(21),"my");
  37.         treeMap.put(new SortedTest(15),"name");
  38.         treeMap.put(new SortedTest(2),"is");
  39.         treeMap.put(new SortedTest(1),"jiaboyan");
  40.         treeMap.put(new SortedTest(7),"world");
  41.         System.out.println(treeMap.toString());
  42.     }
  43. }

4.4 树的自我介绍

在具体讲解TreeMap底层结构之前，我们有必要先来了解下树！

那么，到底什么是树呢？

树--是计算机中的一种数据结构，是一个由n（>=1）个元素组成具有层次关系的集合。因该数据结构呈现出的形状像一颗树，所以称这种数据结构叫做树，只不过这颗树是倒过来的。

在上面的截图中，简单抽象出数据结构中的树。在生活中，这样的结构比比皆是，例如：公司的组织架构、家族的族谱、计算机中的文件结构等等。只要符合上面的结构，均可以称为树；

在计算机领域中，树只是一种简称，具体的实现还是交由其子树来完成；这其中就包括：二叉树、平衡二叉树、红黑树、B树、哈夫曼树等。在本章节中，我们主要介绍其中的两种数据结构---二叉树、红黑树；

在介绍二叉树之前，还需要对树的相关术语进行理解：

举个图片来说，更加直观：(只为讲解树的概念)

节点(Nood)：树中的每一个元素都叫做节点，又或者称为结点；图中A、B、C、D等都称之为节点；

根节点(树根-Root)：在树中，最顶端的节点称之为根节点(树根-Root)；A节点就是整个树的根节点；

子树：除了根节点之外，其余节点自由组合成的树，称之为子树，子树可以是一个节点，也可以是多个节点；其中，Q节点可称之为子树，B、D、G三个节点结合也可以称之为子树；

叶子节点(叶节点)：没有孩子节点的节点，称之为叶子节点(叶节点),也就是该节点下面没有子节点了；图中D、G、Q、V称之为叶子节点；

父节点：简单来说，就是一个节点上面的节点，就是该节点的父节点；B节点是D节点的父节点，C节点是Q节点的父节点；

树的高度：从叶子节点(此时高度为1)开始自底向上逐层增加，得到的值称之为树的高度；截图中树的高度为4（V、H、C、A）;

树的深度：从根节点(此时深度为1)开始自上而下逐层增加，最终得到的值称之为树的深度；截图中树的深度为4(A、C、H、V);

4.5 二叉树

二叉树是最基础的树结构，也是树结构中的根基；

二叉树可以有多个元素，也可以只有一个元素，当然也可以一个元素也没有，它是一个元素的集合；二叉树规定了在每个节点下最多只能拥有两个子节点，一左一右；其中，左节点可以称为左子树，右节点称为右子树；但没有要求左子树中任意节点的值要小于右子树中任意节点的值。

说到这，暂时我们可以简单地将二叉树理解成链表，只不过这个链表被从中间进行了分隔，一边朝右，一边朝左，就形成了一颗二叉树。

二叉树节点实现：

  1. public class TreeNode {
  2.  
  3.     //节点的值：
  4.     private int data;
  5.     //指向左孩子的指针：
  6.     private TreeNode leftTreeNode;
  7.     //指向右孩子的指针：
  8.     private TreeNode rightTreeNode;
  9.     //指向父节点的指针
  10.     private TreeNode parentNode;
  11.  
  12.     public TreeNode(int data, TreeNode leftTreeNode,
  13.                     TreeNode rightTreeNode, TreeNode parentNode) {
  14.         this.data = data;
  15.         this.leftTreeNode = leftTreeNode;
  16.         this.rightTreeNode = rightTreeNode;
  17.         this.parentNode = parentNode;
  18.     }
  19.     public int getData() {
  20.         return data;
  21.     }
  22.     public void setData(int data) {
  23.         this.data = data;
  24.     }
  25.     public TreeNode getLeftTreeNode() {
  26.         return leftTreeNode;
  27.     }
  28.     public void setLeftTreeNode(TreeNode leftTreeNode) {
  29.         this.leftTreeNode = leftTreeNode;
  30.     }
  31.     public TreeNode getRightTreeNode() {
  32.         return rightTreeNode;
  33.     }
  34.     public void setRightTreeNode(TreeNode rightTreeNode) {
  35.         this.rightTreeNode = rightTreeNode;
  36.     }
  37.     public TreeNode getParentNode() {return parentNode;}
  38.     public void setParentNode(TreeNode parentNode) {this.parentNode = parentNode;}
  39. }

4.6 二叉查找树

说完了二叉树，下面继续说二叉查找树；相比于二叉树来说，二叉查找树的特点更加明确。

二叉查找树规定：

  1. 如果二叉查找树的左子树不为空，那么它的左子树上的任意节点的值都小于根节点的值；
  2.  
  3. 如果二叉查找树的右子树不为空，那么它的右子树上的任意节点的值都大于根节点的值；

也就是说，二叉查找树的左子树中任意节点的值都小于右子树中任意节点的值。而且，在左子树和右子树中也同样形成了二叉查找树；所以说二叉查找树的特点比二叉树更加明确。

此外，根据上面的特点，我们还可以使用二分查找在树中进行元素搜索：如果查找的元素大于根节点，则在树的右边进行搜索；如果小于根节点，则在树的左边进行搜索。如果等于根节点，则直接返回；所以二叉查找树的查询效率远远高于二叉树。

4.8 平衡二叉树（AVL树）

前几节中，笔者说过：可以将二叉树简单地理解为一个链表结构。当时，是为了能让各位能对二叉树有一个最直观的理解。

其实，在具体的实现中二叉树确实会形成一个链表结构。

试想下，如果一个二叉树的左子树为空，只有右子树，且右子树中又只有右节点（左节点），那么这个二叉树就形成了一个不折不扣的链表。对于二叉查找树来说，二分查找也就失去了原有的性能，变成了顺序查找。即元素的插入顺序是1、2、3、4、5、6的话，即可实现。

为了针对这一情况，平衡二叉树出现了（又称为AVL树），它要求左右子树的高度差的绝对值不能大于1，也就是说左右子树的高度差只能为-1、0、1。

4.7 红黑树

终于说到了今天的重中之重--红黑树，相比于之前讲过的数据结构，红黑树的难度有所增加，你要做好准备！

只要带有树字，它就远离不了二叉树的结构。

红黑树，本质上依旧一颗二叉查找树，它满足了二叉查找树的特点，即左子树任意节点的值永远小于右子树任意节点的值。

不过，二叉查找树还有一个致命的弱点，即左子树(右子树)可以为空，而插入的节点全部集中到了树的另一端，致使二叉查找树失去了平衡，二叉查找树搜索性能下降，从而失去了使用二分查找的意义。

为了维护树的平衡性，平衡二叉树（AVL树）出现了，它用左右子树的高度差来保持着树的平衡。而我们本节要介绍的红黑树，用的是节点的颜色来维持树的平衡。

那么，红黑树是怎么利用颜色来维持平衡的呢？接下来，让我们慢慢道来。

红黑树，即红颜色和黑颜色并存的二叉树，插入的元素节点会被赋为红色或者黑色，待所有元素插入完成后就形成了一颗完整的红黑树。如下图所示：

不过，你不要想当然的以为只是给二叉树的阶段随意赋为黑色或者红色，就可保证树的平衡。事情远没有你想象的那么简单。

一颗红黑树必须满足一下几点要求：

  1. 树中每个节点必须是有颜色的，要么红色，要么黑色；

  2. 树中的根节点必须是黑色的；

  3. 树中的叶节点必须是黑色的，也就是树尾的NIL节点或者为null的节点；

  4. 树中任意一个节点如果是红色的，那么它的两个子节点一点是黑色的；

  5. 任意节点到叶节点（树最下面一个节点）的每一条路径所包含的黑色节点数目一定相同；

科普：NIL节点是就是一个假想的或是无实在意义的节点，所有应该指向NULL的指针，都看成指向了NIL节点。包括叶节点的子节点指针或是根节点的父指针（均是指向null的）

除了给节点赋颜色之外，还会对节点进行左旋、右旋操作，以来维持树的平衡。那么，左旋、右旋又什么？

首先，我们先来看下在红黑树中，每一个节点的数据结构是什么样子的？

  1. public class TreeNode {
  2.     //节点的值：
  3.     private int data;
  4.     //节点的颜色：
  5.     private String color;
  6.     //指向左孩子的指针：
  7.     private TreeNode leftTreeNode;
  8.     //指向右孩子的指针：
  9.     private TreeNode rightTreeNode;
  10.     //指向父节点的指针
  11.     private TreeNode parentNode;
  12.  
  13.     public TreeNode(int data, String color, TreeNode leftTreeNode,
  14.                     TreeNode rightTreeNode, TreeNode parentNode) {
  15.         this.data = data;
  16.         this.color = color;
  17.         this.leftTreeNode = leftTreeNode;
  18.         this.rightTreeNode = rightTreeNode;
  19.         this.parentNode = parentNode;
  20.     }
  21.     public int getData() {
  22.         return data;
  23.     }
  24.     public void setData(int data) {
  25.         this.data = data;
  26.     }
  27.     public String getColor() {return color;}
  28.     public void setColor(String color) {this.color = color;}
  29.     public TreeNode getLeftTreeNode() {
  30.         return leftTreeNode;
  31.     }
  32.     public void setLeftTreeNode(TreeNode leftTreeNode) {
  33.         this.leftTreeNode = leftTreeNode;
  34.     }
  35.     public TreeNode getRightTreeNode() {
  36.         return rightTreeNode;
  37.     }
  38.     public void setRightTreeNode(TreeNode rightTreeNode) {
  39.         this.rightTreeNode = rightTreeNode;
  40.     }
  41.     public TreeNode getParentNode() {return parentNode;}
  42.     public void setParentNode(TreeNode parentNode) {this.parentNode = parentNode;}
  43. }

如果用图片来形容的话：

4.7.1 旋转

上面说过，为了维护红黑树的平衡，不只是给节点着色那么简单，还有更复杂的处理逻辑。

而这更复杂的处理逻辑就是对节点进行旋转操作，其中旋转操作又分为左旋、右旋两种；

对于树的操作，最常见的就是添加、删除而已。不过，在添加或者删除之后，红黑树发生了改变，可能就不满足以上的5点要求，也就不是一颗红黑树了。于是我们需要通过对节点的旋转，使其重新成为一颗红黑树。

  1. 左旋

左旋，顾名思义就是对节点进行向左旋转处理；

对节点X进行向左进行旋转，将其变成了一个左子节点；

这个左旋中的左，就是将被旋转的节点变成一个左节点；

其中，如果Y的的左子节点不为null，则将其赋值X的右子节点；

  1. 右旋

右旋，同理，也就是对节点进行向右旋转处理；

对节点Y进行向右进行旋转，将其变成了一个右子节点；

这个右旋中的右，就是将被旋转的节点变成一个右节点；

其中，如果X节点的右子节点不为null，则赋值给Y的左子节点；

补充：在举个例子，让大家更直观的理解：（暂时先忽略红黑树，只关注旋转）

4.7.2 红黑树节点添加

本节中，笔者就来介绍下红黑树节点的添加。

在将一个节点插入到红黑树中，首选需要将红黑树当做一颗二叉树查找树来对待，将节点进行插入。然后，为新插入的节点进行着色；最后，通过旋转和重新着色的方式来修正树的平衡，使其成为一颗红黑树；

（1）对于红黑树来说，其底层依旧是一颗二叉查找树。当我们插入新的元素时，它依旧会对该元素进行排序比较，将其送入到左子树或者是右子树中。

（2）在将新节点安置好以后，在对其进行着色处理，必须着成红色。

你此时可能会问，为什么要着成红色，而不是黑色呢？

这就需要我们重新回顾下红黑树的规范了：

  1. 1. 树中每个节点必须是有颜色的，要么红色，要么黑色；
  2.  
  3. 2. 树中的根节点必须是黑色的；
  4.  
  5. 3. 树中的叶节点必须是黑色的，也就是树尾的NIL节点或者为null的节点；
  6.  
  7. 4. 树中任意一个节点如果是红色的，那么它的两个子节点一点是黑色的；
  8.  
  9. 5. 任意节点到叶节点（树最下面一个节点）的每一条路径所包含的黑色节点数目一定相同；

通过以上的规范，我们可以分析出，当将新增节点着成红色后，我们违背以上规范的条数最少，恢复平衡起来最省事，当新增节点为红色时：

  1. 1.不会违背第五条--黑色节点数目相同；
  2.  
  3. 2.不会违背第一条--节点必须是红色，或者黑色；
  4.  
  5. 3.不会违背第二条--根节点是黑色--当树中已有元素时候，我们新增节点并不会影响根节点的颜色（若树中没有元素，新增节点会被当成根节点，此时虽被着为红色，但在最后一步中还会对其重新着色，变成黑色）；
  6.  
  7. 4.不会违背第三条--此处所指的叶节点指的是叶节点的子节点，也就是为null的元素；
  8.  
  9. 5.可能会违背第四条--任意节点为红色，其子节点一定是黑色；

如果新插入的节点的父节点是红色的话，那么第四条一定会违背，所以说我们需要对其进行旋转处理；

（3）冲突来了，解决冲突（对节点进行旋转）

  • 当被插入节点是根节点：

    新插入的节点后，如果为根节点，则直接将其变成黑色，并返回；

     

  • 当被插入节点的父节点是黑色：

    新插入的节点被着成红色后，发现其父节点是黑色，并不影响红黑树结构，所以并不需要对平衡性做处理，直接返回；

     

  • 当被插入节点的父节点是红色（最复杂）：

    新插入的节点被着成红色后，发现其父节点是红色，此时红黑树的平衡被打破，需要特别处理。

    说之前，简单的阐述下什么是该节点的祖父节点，什么是该节点的叔叔节点（画图一目了然）；

case1：叔叔节点为黑色（空节点默认为黑色）

  1. A.2是3的左子节点，3是5的左子节点；
  2.  
  3. B.17是16的右子节点，16是15的右子节点；

  1. C.17是15的右子节点，15是23的左子节点 
  2.  
  3. D.43是56的左子节点，46是41的右子节点；

其中，A、B称之为外侧插入，C、D称之为内测插入。

首先，来看A的解决方案：

将3设置为黑色，5设置为红色，再对5进行右旋，结果如下：

 

来看B的解决方案：

将16设置为黑色，15设置为红色，再对15进行左旋，结果如下：

 

来看C的解决方案：

将15进行左旋，成为17的左子节点，此时形成了A情况，再将17置为黑色，23置为红色，再对23进行右旋，结果如下：

 

来看D的解决方案：
将46进行右旋，成为41的右子节点，此时形成了B情况，再将43置为黑色，41置为红色，再对41进行左旋，结果如下：

 

case2：叔叔节点为红色

当叔叔节点为红色时，处理的逻辑较为简单，主要对元素节点的颜色进行处理，无需左旋、右旋的操作。

在A情况中，无论新插入的元素是7还是12，处理过程都是一样的；

将10和27置为黑色，23置为红色，再将23置为黑色，新插入元素7（12）保持红色不变，结束返回；

同理，在B情况中，处理26或者35的逻辑也是相同的；

将15和30置为黑色，18置为红色，再将18置为黑色，新插入元素26（35）保持红色不变，结束返回；

同上，暂不画图了；

以上，就是红黑树添加节点的处理逻辑，希望以上的图片可以让你对着色、旋转有一个清晰的认识！

有兴趣的朋友，可以参考红黑树网站进行实际操作！

4.7.3 红黑树节点删除

暂省略；

4.8 TreeMap源码讲解（基于JDK1.7.0_75）

上面，我们通过图片的形式，对红黑树进行了全面的讲解。接下来，就让我们学习下红黑树在Java中的实现--TreeMap;

  • TreeMap节点结构

TreeMap底层存储结构与HashMap基本相同，依旧是Entry对象，存储key--value键值对，子节点的引用和父节点的引用，以及默认的节点颜色（黑色）；

  1. static final class Entry<K,V> implements Map.Entry<K,V> {
  2.     //插入节点的key:
  3.     K key;
  4.  
  5.     //插入节点的value:
  6.     V value;
  7.  
  8.     //插入节点的左子节点：
  9.     java.util.TreeMap.Entry<K,V> left = null;
  10.  
  11.     //插入节点的右子节点：
  12.     java.util.TreeMap.Entry<K,V> right = null;
  13.  
  14.     //插入节点的父节点：
  15.     java.util.TreeMap.Entry<K,V> parent;
  16.  
  17.     //插入节点默认的颜色：
  18.     boolean color = BLACK;
  19.  
  20.     //Entry对象的构造函数：
  21.     Entry(K key, V value, java.util.TreeMap.Entry<K,V> parent) {
  22.         this.key = key;
  23.         this.value = value;
  24.         this.parent = parent;
  25.     }
  26.     public K getKey() {
  27.         return key;
  28.     }
  29.     public V getValue() {
  30.         return value;
  31.     }
  32.     public V setValue(V value) {
  33.         V oldValue = this.value;
  34.         this.value = value;
  35.         return oldValue;
  36.     }
  37.     public boolean equals(Object o) {
  38.         if (!(o instanceof Map.Entry))
  39.             return false;
  40.         Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  41.         return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
  42.     }
  43.     public int hashCode() {
  44.         int keyHash = (key==null ? 0 : key.hashCode());
  45.         int valueHash = (value==null ? 0 : value.hashCode());
  46.         return keyHash ^ valueHash;
  47.     }
  48.     public String toString() {
  49.         return key + "=" + value;
  50.     }
  51. }
  • TreeMap构造函数

与HashMap不同，TreeMap底层不是数组结构，成员变量中并没有数组，而是用根节点root来替代，所有的操作都是通过根节点来进行的。

  1. public class TreeMap<K,V>
  2.         extends AbstractMap<K,V>
  3.         implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
  4.     //自定义的比较器：
  5.     private final Comparator<? super K> comparator;
  6.  
  7.     //红黑树的根节点：
  8.     private transient java.util.TreeMap.Entry<K,V> root = null;
  9.  
  10.     //集合元素数量：
  11.     private transient int size = 0;
  12.  
  13.     //对TreeMap操作的数量：
  14.     private transient int modCount = 0;
  15.  
  16.     //无参构造方法：comparator属性置为null
  17.     //代表使用key的自然顺序来维持TreeMap的顺序，这里要求key必须实现Comparable接口
  18.     public TreeMap() {
  19.         comparator = null;
  20.     }
  21.  
  22.     //带有比较器的构造方法：初始化comparator属性；
  23.     public TreeMap(Comparator<? super K> comparator) {
  24.         this.comparator = comparator;
  25.     }
  26.  
  27.     //带有map的构造方法：
  28.     //同样比较器comparator为空，使用key的自然顺序排序
  29.     public TreeMap(Map<? extends K, ? extends V> m) {
  30.         comparator = null;
  31.         putAll(m);
  32.     }
  33.  
  34.     //带有SortedMap的构造方法:
  35.     //根据SortedMap的比较器来来维持TreeMap的顺序
  36.     public TreeMap(SortedMap<K, ? extends V> m) {
  37.         comparator = m.comparator();
  38.         try {
  39.             buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
  40.         } catch (java.io.IOException cannotHappen) {
  41.         } catch (ClassNotFoundException cannotHappen) {
  42.         }
  43.     }
  44. }
  • TreeMap元素添加

将新增节点的key--value插入到TreeMap当中，在上文中我们已经通过图文的形式介绍了新增的流程，如果你还不明白，可以结合源码进行理解；

首先找到新增节点的位置，其次在判断TreeMap是否处于平衡状态，若不平衡，则对节点进行着色、旋转操作；

  1. //插入key-value:
  2. public V put(K key, V value) {
  3.     //根节点赋值给t:
  4.     java.util.TreeMap.Entry<K,V> t = root;
  5.     //如果根节点为null，则创建第一个节点，根节点
  6.     if (t == null) {
  7.         //对传入的元素进行比较，若TreeMap没定义了Comparator，则验证传入的元素是否实现了Comparable接口；
  8.         compare(key, key);
  9.         //根节点赋值：
  10.         root = new java.util.TreeMap.Entry<>(key, value, null);
  11.         //长度为1：
  12.         size = 1;
  13.         //修改次数+1
  14.         modCount++;
  15.         //直接返回：此时根节点默认为黑色
  16.         return null;
  17.     }
  18.  
  19.     //如果根节点不为null:
  20.     int cmp;
  21.     java.util.TreeMap.Entry<K,V> parent;
  22.     Comparator<? super K> cpr = comparator;
  23.  
  24.     //判断TreeMap中自定义比较器comparator是否为null：
  25.     if (cpr != null) {
  26.         // do while循环，查找新插入节点的父节点：
  27.         do {
  28.             // 记录上次循环的节点t，首先将根节点赋值给parent:
  29.             parent = t;
  30.             //利用自定义比较器的比较方法：传入的key跟当前遍历节点比较：
  31.             cmp = cpr.compare(key, t.key);
  32.             //判断结果小于0，处于父节点的左边 
  33.             if (cmp < 0)
  34.                 t = t.left;
  35.             else if (cmp > 0)
  36.             //判断结果大于0，处于父节点的右边 
  37.                 t = t.right;
  38.             else
  39.             //判断结果等于0，为当前节点，覆盖原有节点处的value：
  40.                 return t.setValue(value);
  41.         // 只有当t为null，也就是找到了新节点的parent了
  42.         } while (t != null);
  43.     } else {
  44.         //没有自定义比较器：
  45.         if (key == null)
  46.             //TreeMap不允许插入key为null，抛异常：
  47.             throw new NullPointerException();
  48.         //将key转换为Comparable对象：若key没有实现Comparable接口，此处会报错
  49.         Comparable<? super K> k = (Comparable<? super K>) key;
  50.         //同上：寻找新增节点的父节点：
  51.         do {
  52.             parent = t;
  53.             cmp = k.compareTo(t.key);
  54.             if (cmp < 0)
  55.                 t = t.left;
  56.             else if (cmp > 0)
  57.                 t = t.right;
  58.             else
  59.                 return t.setValue(value);
  60.         } while (t != null);
  61.     }
  62.  
  63.     //构造新增节点对象：
  64.     java.util.TreeMap.Entry<K,V> e = new java.util.TreeMap.Entry<>(key, value, parent);
  65.  
  66.     //根据之前的比较结果，判断新增节点是在父节点的左边还是右边
  67.     if (cmp < 0)
  68.         // 如果新节点key的值小于父节点key的值，则插在父节点的左侧
  69.         parent.left = e;
  70.     else
  71.         // 如果新节点key的值大于父节点key的值，则插在父节点的右侧
  72.         parent.right = e;
  73.     //核心方法：插入新的节点后，为了保持红黑树平衡，对红黑树进行调整
  74.     fixAfterInsertion(e);
  75.     size++;
  76.     modCount++;
  77.     return null;
  78. }
  79.  
  80. //对插入的元素比较：若TreeMap没有自定义比较器，则调用调用默认自然顺序比较，要求元素必须实现Comparable接口；
  81. //若自定义比较器，则用自定义比较器对元素进行比较；
  82. final int compare(Object k1, Object k2) {
  83.     return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
  84.             : comparator.compare((K)k1, (K)k2);
  85. }
  86.  
  87. //核心方法：维护TreeMap平衡的处理逻辑；（回顾上面的图文描述）
  88. private void fixAfterInsertion(java.util.TreeMap.Entry<K,V> x) {
  89.     //首先将新插入节点的颜色设置为红色
  90.     x.color = RED;
  91.     //TreeMap是否平衡的重要判断，当不在满足循环条件时，代表树已经平衡；
  92.     //x不为null，不是根节点，父节点是红色（三者均满足才进行维护）：
  93.     while (x != null && x != root && x.parent.color == RED) {
  94.         //节点x的父节点 是 x祖父节点的左孩子：
  95.         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
  96.             //获取x节点的叔叔节点y:
  97.             java.util.TreeMap.Entry<K,V> y = rightOf(parentOf(parentOf(x)));
  98.             
  99.             //叔叔节点y是红色：
  100.             if (colorOf(y) == RED) {
  101.                 //将x的父节点设置黑色：
  102.                 setColor(parentOf(x), BLACK);  
  103.                 //将x的叔叔节点y设置成黑色：
  104.                 setColor(y, BLACK);
  105.                 //将x的祖父节点设置成红色：
  106.                 setColor(parentOf(parentOf(x)), RED);
  107.                 //将x节点的祖父节点设置成x(进入了下一次判断)：
  108.                 x = parentOf(parentOf(x));
  109.             } else {
  110.                  //叔叔节点y不为红色：
  111.                 //x为其父节点的右孩子：
  112.                 if (x == rightOf(parentOf(x))) {
  113.                     x = parentOf(x);
  114.                     rotateLeft(x);
  115.                 }
  116.                 setColor(parentOf(x), BLACK);
  117.                 setColor(parentOf(parentOf(x)), RED);
  118.                 //右旋：
  119.                 rotateRight(parentOf(parentOf(x)));
  120.             }
  121.         } else {
  122.             //节点x的父节点 是x祖父节点的右孩子：
  123.  
  124.             //获取x节点的叔叔节点y:
  125.             java.util.TreeMap.Entry<K,V> y = leftOf(parentOf(parentOf(x)));
  126.             //判断叔叔节点y是否为红色：
  127.             if (colorOf(y) == RED) {
  128.                 setColor(parentOf(x), BLACK);12
  129.                 setColor(y, BLACK);5
  130.                 setColor(parentOf(parentOf(x)), RED);10
  131.                 x = parentOf(parentOf(x));
  132.             } else {
  133.                 if (x == leftOf(parentOf(x))) {
  134.                     x = parentOf(x);
  135.                     rotateRight(x);
  136.                 }
  137.                 setColor(parentOf(x), BLACK);
  138.                 setColor(parentOf(parentOf(x)), RED);
  139.                 //左旋：
  140.                 rotateLeft(parentOf(parentOf(x)));
  141.             }
  142.         }
  143.     }
  144.     root.color = BLACK;
  145. }
  146.  
  147. //获取节点的颜色：
  148. private static <K,V> boolean colorOf(java.util.TreeMap.Entry<K,V> p) {
  149.     //节点为null,则默认为黑色；
  150.     return (p == null ? BLACK : p.color);
  151. }
  152.  
  153. //获取p节点的父节点：
  154. private static <K,V> java.util.TreeMap.Entry<K,V> parentOf(java.util.TreeMap.Entry<K,V> p) {
  155.     return (p == null ? null: p.parent);
  156. }
  157.  
  158. //对节点进行着色，TreeMap使用了boolean类型来代表颜色（true为红色，false为黑色）
  159. private static <K,V> void setColor(java.util.TreeMap.Entry<K,V> p, boolean c){
  160.     if (p != null)
  161.         p.color = c;
  162. }
  163.  
  164. //获取左子节点：
  165. private static <K,V> java.util.TreeMap.Entry<K,V> leftOf(java.util.TreeMap.Entry<K,V> p) {
  166.     return (p == null) ? null: p.left;
  167. }
  168.  
  169. //获取右子节点：
  170. private static <K,V> java.util.TreeMap.Entry<K,V> rightOf(java.util.TreeMap.Entry<K,V> p) {
  171.     return (p == null) ? null: p.right;
  172. }
  173.  
  174. //左旋：
  175. private void rotateLeft(java.util.TreeMap.Entry<K,V> p) {
  176.     if (p != null) {
  177.         java.util.TreeMap.Entry<K,V> r = p.right;
  178.         p.right = r.left;
  179.         if (r.left != null)
  180.             r.left.parent = p;
  181.         r.parent = p.parent;
  182.         if (p.parent == null)
  183.             root = r;
  184.         else if (p.parent.left == p)
  185.             p.parent.left = r;
  186.         else
  187.             p.parent.right = r;
  188.         r.left = p;
  189.         p.parent = r;
  190.     }
  191. }
  192.  
  193. //右旋：
  194. private void rotateRight(java.util.TreeMap.Entry<K,V> p) {
  195.     if (p != null) {
  196.         java.util.TreeMap.Entry<K,V> l = p.left;
  197.         p.left = l.right;
  198.         if (l.right != null) l.right.parent = p;
  199.         l.parent = p.parent;
  200.         if (p.parent == null)
  201.             root = l;
  202.         else if (p.parent.right == p)
  203.             p.parent.right = l;
  204.         else p.parent.left = l;
  205.         l.right = p;
  206.         p.parent = l;
  207.     }
  208. }
  • TreeMap元素获取

TreeMap底层是红黑树结构，而红黑树本质是一颗二叉查找树，所以在获取节点方面，使用二分查找算法性能最高；

  1. //通过key获取对应的value：
  2. public V get(Object key) {
  3.     //获取TreeMap中对应的节点：
  4.     java.util.TreeMap.Entry<K,V> p = getEntry(key);
  5.     //获取节点的值：
  6.     return (p==null ? null : p.value);
  7. }
  8.  
  9. //通过key获取Entry对象：
  10. final java.util.TreeMap.Entry<K,V> getEntry(Object key) {
  11.     //TreeMap自定义比较器不为空，使用自定义比较器对象来获取节点：
  12.     if (comparator != null)
  13.         //获取节点：
  14.         return getEntryUsingComparator(key);
  15.  
  16.     //如果key为null，则抛出异常，TreeMap中不允许存在为null的key：
  17.     if (key == null)
  18.         throw new NullPointerException();
  19.  
  20.     //将传入的key转换成Comparable类型，传入的key必须实现Comparable接口
  21.     Comparable<? super K> k = (Comparable<? super K>) key;
  22.     //获取根节点：
  23.     java.util.TreeMap.Entry<K,V> p = root;
  24.  
  25.     // 使用二分查找方式，首先判断传入的key与根节点的key哪个大：
  26.     while (p != null) {
  27.         //传入的key与p节点的key进行大小比较：
  28.         int cmp = k.compareTo(p.key);
  29.         //传入的key小于p节点的key,则从根的左子树中搜索：
  30.         if (cmp < 0)
  31.             //左边
  32.             p = p.left;
  33.         else if (cmp > 0)
  34.             //传入的key大于p节点的key,则从根的右边子树中搜索：
  35.             //右边
  36.             p = p.right;
  37.         else
  38.             //传入的key等于p节点的key,则直接返回当前节点：
  39.             return p;
  40.     }
  41.     //以上循环没有找对对应的节点，则返回null：
  42.     return null;
  43. }
  44.  
  45. //使用自定义比较器进行元素比较，获取对节点：
  46. final java.util.TreeMap.Entry<K,V> getEntryUsingComparator(Object key) {
  47.     K k = (K) key;
  48.     Comparator<? super K> cpr = comparator;
  49.     if (cpr != null) {
  50.         java.util.TreeMap.Entry<K,V> p = root;
  51.         while (p != null) {
  52.             int cmp = cpr.compare(k, p.key);
  53.             if (cmp < 0)
  54.                 p = p.left;
  55.             else if (cmp > 0)
  56.                 p = p.right;
  57.             else
  58.                 return p;
  59.         }
  60.     }
  61.     return null;
  62. }
  • TreeMap元素删除

暂忽略；

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/1003427
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号