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

发表于   |   分类于 左手代码 计算机基础   |   阅读(380)   |   评论(0)

一、红黑树说明

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>();
  3. Map<Integer, String> bookMap = new HashMap<Integer, String>(2);
  4. bookMap.put(25, "Mybatis");
  5. bookMap.put(36, "Dubbo");
  6. TreeMap<Integer, String> bookTree = new TreeMap<Integer, String>(bookMap);
  7. 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");
  9. System.out.println(tree.containsKey(3));   // true
  10. 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");
  5. System.out.println(tree.containsValue("JAVA"));    //true
  6. 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");
  9. System.out.println(tree.get(8));   //Spring
  10. 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, "数据结构");
  6. tree.remove(2);
  7. 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, "数据结构");
  6. Set<Integer> keys = tree.keySet();
  7. 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, "数据结构");
  6. tree.replace(3, "Golang");  //{3=Golang, 5=数据结构, 9=算法}
  7. tree.replace(1, "Python");  //{3=Golang, 5=数据结构, 9=算法}
  8. tree.replace(5, "数据结构", "Java数据结构"); //{3=Golang, 5=Java数据结构, 9=算法}
  9. 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. }

专题 更多...

分类 更多...

展开

标签 更多...

归档 更多...

展开