《恋上数据结构与算法》笔记（十四）：集合 (Set) 和 映射 (Map)、TreeSet、TreeMap实现

刺骨的言语ヽ痛彻心扉 2022-12-27 07:43 37阅读 0赞

目录

具体代码在 : set-map, 欢迎star

  • 一、集合（Set）
  • 二、集合的接口设计

  • 三、集合的实现

    • 1、通过链表实现集合 (ListSet)
    • 2、通过红黑树实现集合 (TreeSet)
    • 3、通过链表和红黑树实现的Set, 性能对比
  • 四、映射（Map）
  • 五、映射的接口设计

  • 六、映射的实现（TreeMap）

    • 1、声明节点
    • 2、put函数实现
    • 3、get函数实现
    • 4、remove函数实现
    • 5、contains函数实现
    • 6、traversal函数实现
    • 7、旋转代码
    • 8、寻找节点的前驱和后继
    • 9、红黑树辅助方法
    • 10、测试
  • 七、TreeMap代码(完整)

一、集合（Set）

特点: 不存放重复的元素, 元素唯一。

  • 常用于去重

    • 存放新增IP，统计新增IP量
    • 存放词汇，统计词汇量

  • 集合(Set)的内部实现能使用哪些数据结构？

    • 动态数组
    • 链表
    • 二叉搜索树（AVL树，红黑树）

二、集合的接口设计

  1. /** * Description: Set集合 * * 这里为Set集合, 提供了遍历集合的接口, 为什么我们之前的动态数组,链表没有提供呢, 因为它们有索引的概念, 可以通过for就可以遍历。 * 然而Set集合, 没有索引的概念, 所以要提供遍历接口。 * * @author guizy * @date 2020/12/8 22:27 */
  2. public interface Set<E> { 
  3.     int size();
  4.     boolean isEmpty();
  5.     void clear();
  6.     boolean contains(E element);
  7.     void add(E element);
  8.     void remove(E element);
  9.     void traversal(Visitor<E> visitor); //遍历集合
  11.     public static abstract class Visitor<E> { 
  12.         boolean stop;
  13.         public abstract boolean visit(E element);
  14.     }
  15. }

三、集合的实现

1、通过链表来实现 (ListSet)

  • 我们要使用之前实现过的链表相关的代码, 所以需要之前写的List, AbstractList,DoubleLinkedList. 请参考 小码哥《恋上数据结构与算法》笔记（二）：链表

    具体代码在 LinkedList , 欢迎 star
    在这里插入图片描述

  • 复杂度为O(n)

    /* Description: 使用双向链表实现Set @author guizy @date 2020/12/8 22:32 /
    public class ListSet implements Set { 

    1. private List<E> list = new DoubleLinkedList<>();
    3. @Override
    4. public int size() { 
    5.     return list.size();
    6. }
    8. @Override
    9. public boolean isEmpty() { 
    10.     return list.inEmpty();
    11. }
    13. @Override
    14. public void clear() { 
    15.     list.clear();
    16. }
    18. @Override
    19. public boolean contains(E element) { 
    20.     return list.contains(element);
    21. }
    23. @Override
    24. public void add(E element) { 
    25.     // 方式1: 不添加重复的元素
    26.     // if (list.contains(element)) return;
    27.     // list.add(element);
    29.     // 方式2: 新元素覆盖掉旧的
    30.     int index = list.indexOf(element);
    31.     if (index != list.ELEMENT_NOT_FOUNT) {   // 存在就覆盖
    32.         list.set(index, element);
    33.     } else {  // 不存在就添加
    34.         list.add(element);
    35.     }
    36. }
    38. @Override
    39. public void remove(E element) { 
    40.     int index = list.indexOf(element);
    41.     if (index != list.ELEMENT_NOT_FOUNT) { 
    42.         list.remove(index);
    43.     }
    44. }
    46. @Override
    47. public void traversal(Visitor<E> visitor) { 
    48.     if (visitor == null) return;
    50.     int size = list.size();
    51.     for (int i = 0; i < size; i++) { 
    52.         if (visitor.visit(list.get(i))) return;
    53.     }
    54. }

    }

2、通过红黑树来实现 (TreeSet)

  • 我们要使用之前实现过的红黑树相关的代码, 所以需要之前写的BinaryTree, BST,BBST,RBTree. 请参考 《恋上数据结构与算法》笔记（十三）：红黑树

    具体代码在 : RBTree, 欢迎star
    在这里插入图片描述

  • 复杂度为O(logn)

  • 元素必须具备可比较性，否则只能使用哈希表

    /* Description: 使用红黑树实现Set @author guizy @date 2020/12/8 23:33 /
    public class TreeSet implements Set { 

    1. private RBTree<E> tree;
    3. public TreeSet() { 
    4.     this(null);
    5. }
    7. public TreeSet(Comparator<E> comparator) { 
    8.     tree = new RBTree<>(comparator);
    9. }
    11. @Override
    12. public int size() { 
    13.     return tree.size();
    14. }
    16. @Override
    17. public boolean isEmpty() { 
    18.     return tree.isEmpty();
    19. }
    21. @Override
    22. public void clear() { 
    23.     tree.clear();
    24. }
    26. @Override
    27. public boolean contains(E element) { 
    28.     return tree.contains(element);
    29. }
    31. @Override
    32. public void add(E element) { 
    33.     // RBTree中默认就是去重的
    34.     tree.add(element);
    35. }
    37. @Override
    38. public void remove(E element) { 
    39.     tree.remove(element);
    40. }
    42. @Override
    43. public void traversal(Visitor<E> visitor) { 
    44.     // 中序遍历
    45.     tree.inorderTraversal(new BinaryTree.Visitor<E>() { 
    46.         @Override
    47.         public boolean visit(E element) { 
    48.             return visitor.visit(element);
    49.         }
    50.     });
    51. }

    }

3、通过链表和红黑树实现的Set, 性能对比

  • 通过添加、搜索、删除 大批量数据来测试, 将jdk中源码src目录下的文件遍历, 通过单词量, 代码量, 文件数目多维度来检测两者性能; 这里不提供工具类代码, 具体看文章开篇提供的源码。
  • 对比ListSet, TreeSet遍历查询src/java/util的单词量, 代码量, 文件数

  • 测试代码如下

    public void testSet(Set set, String[] words) { 

    1. for (int i = 0; i < words.length; i++) { 
    2.     set.add(words[i]);
    3. }
    4. for (int i = 0; i < words.length; i++) { 
    5.     set.contains(words[i]);
    6. }
    7. for (int i = 0; i < words.length; i++) { 
    8.     set.remove(words[i]);
    9. }

    }

    @Test
    public void testSrcWords() { 

    1. FileInfo fileInfo = Files.read("C:\\Users\\guizy1\\Desktop\\src\\java\\util", new String[]{ "java"});
    2. System.out.println("文件数量：" + fileInfo.getFiles());
    3. System.out.println("代码行数：" + fileInfo.getLines());
    4. String[] words = fileInfo.words();
    5. System.out.println("单词数量：" + words.length);
    7. // 使用链表实现的ListSet来测试
    8. Times.test("ListSet", new Times.Task() { 
    9.     @Override
    10.     public void execute() { 
    11.         testSet(new ListSet<>(), words);
    12.     }
    13. });
    15. // 使用红黑树实现的TreeSet来测试
    16. // Times.test("TreeSet", () -> testSet(new TreeSet<>(), words));

    }

  • 使用ListSet测试的结果信息

    文件数量：364
    代码行数：211670
    单词数量：875925
    【ListSet】
    开始：10:23:01.699
    结束：10:24:03.611

    耗时：61.911秒

  • 使用TreeSet测试的结果信息

    文件数量：364
    代码行数：211670
    单词数量：875925
    【TreeSet】
    开始：10:30:00.465
    结束：10:30:01.006

    耗时：0.541秒

  • 可以发现使用红黑树实现的Set, 和使用链表实现的Set, 它们的性能差的非常多; 同样也证明了红黑树的效率是非常快的

  • 所以在JDK集合中的HashMap, TreeMap, TreeSet底层都是使用的红黑树来实现。

四、映射（Map）

  • Map在有些编程语言中也叫做字典(dictionary), 比如 Python, Objective-C, Swift 等
  • Map的每一个key是唯一的
    在这里插入图片描述
  • 类似Set，Map可以直接利用之前学习的链表，二叉搜索树（AVL树，红黑树）等数据结构来实现。
  • 使用链表 : 添加，删除，搜索的时间复杂度是O(n)
  • 使用红黑树: 添加，删除，搜索的时间复杂度是O(logn)

  • 特点

    • key必须具备可比较性。
    • 元素的分布是有顺序的（key大的在右边，小的在左边）。

  • 在实际应用中：

    • map中的存储的元素不需要讲究顺序。
    • map中的key一般不需要具备可比较性。
  • 不考虑顺序和key的可比较性，map有更优的实现方案，平均时间复杂度可达到O(1)，那就是采取哈希表来实现map。

五、映射的接口设计

  1. /** * Description: Map接口 * * @author guizy * @date 2020/12/9 15:38 */
  2. public interface Map<K, V> { 
  3.     int size();
  4.     boolean isEmpty();
  5.     void clear();
  6.     V put(K key, V value); //添加元素
  7.     V get(K key);
  8.     V remove(K key);
  9.     boolean containsKey(K key); //查找key是否存在
  10.     boolean containsValue(V value); //查找value是否存在
  11.     void traversal(Visitor<K, V> visitor); //元素遍历
  13.     public static abstract class Visitor<K, V> { 
  14.         boolean stop;
  15.         public abstract boolean visit(K key, V value);
  16.     }
  17. }

六、映射的实现（TreeMap）

  • 做法是将映射Map直接通过红黑树来实现，而不仅仅是通过红黑树存储映射的值, 而是红黑树的节点来存储一个Node<K, V>, 也就是一个键值对。
  • 下面实现的TreeMap的红黑树代码, 全部揉合在TreeMap中, 对之前BinaryTree, BST, BBST, RBTree的代码进行抽取, 放在TreeMap中

1、声明节点 Node

  1. private static class Node<K, V> { 
  2.     K key;
  3.     V value;
  4.     boolean color = RED;
  5.     Node<K, V> left;
  6.     Node<K, V> right;
  7.     Node<K, V> parent;
  9.     public Node(K key, V value, Node<K, V> parent) { 
  10.         this.key = key;
  11.         this.value = value;
  12.         this.parent = parent;
  13.     }
  15.     public boolean isLeaf() { 
  16.         return left == null && right == null;
  17.     }
  19.     public boolean hasTwoChildren() { 
  20.         return left != null && right != null;
  21.     }
  23.     public boolean isLeftChild() { 
  24.         return parent != null && this == parent.left;
  25.     }
  27.     public boolean isRightChild() { 
  28.         return parent != null && this == parent.right;
  29.     }
  31.     public Node<K, V> sibling() { 
  32.         if (isLeftChild()) { 
  33.             return parent.right;
  34.         }
  36.         if (isRightChild()) { 
  37.             return parent.left;
  38.         }
  39.         return null;
  40.     }
  41. }

2、put方法实现

  1. private void keyNotNullCheck(K key) { 
  2.     if (key == null) { 
  3.         // 手动抛出异常对象
  4.         throw new IllegalArgumentException("key must not be null");
  5.     }
  6. }
  8. /** * 想TreeMap中添加一个结点 * * @param key 键 * @param value 值 * @return 返回之前被覆盖的值 */
  9. @Override
  10. public V put(K key, V value) { 
  11.     keyNotNullCheck(key);
  13.     // 添加第一个节点
  14.     if (root == null) { 
  15.         // 给根节点赋值,且根节点没有父节点
  16.         root = new Node<>(key, value, null);
  17.         size++;
  19.         // 添加节点之后的处理
  20.         afterPut(root);
  21.         return null;
  22.     }
  24.     // 添加的不是第一个节点
  25.     Node<K, V> parent = root; // 这个是第一次比较的父节点
  26.     Node<K, V> node = root;
  27.     int cmp = 0;
  28.     while (node != null) { 
  29.         cmp = compare(key, node.key);   // 两者具体比较的方法
  30.         parent = node; // 记录其每一次比较的父节点
  31.         if (cmp > 0) { 
  32.             // 插入的元素大于根节点的元素,插入到根节点的右边
  33.             node = node.right;
  34.         } else if (cmp < 0) { 
  35.             // 插入的元素小于根节点的元素,插入到根节点的左边
  36.             node = node.left;
  37.         } else {  // 相等
  38.             node.key = key;
  39.             V oldValue = node.value;
  40.             node.value = value;
  41.             return oldValue; // 返回之前node的value
  42.         }
  43.     }
  44.     // 看看插入到父节点的哪个位置
  45.     Node<K, V> newNode = new Node<>(key, value, parent);
  46.     if (cmp > 0) { 
  47.         parent.right = newNode;
  48.     } else { 
  49.         parent.left = newNode;
  50.     }
  51.     size++;
  53.     // 添加节点之后的逻辑
  54.     afterPut(newNode);
  55.     // 这里的key是第一次加进去的, 之前没有值, 所以返回null
  56.     return null;
  57. }
  59. // --------------------------------------------
  61. private void afterPut(Node<K, V> node) { 
  62.     Node<K, V> parent = node.parent;
  64.     // 添加的是根节点(染成黑色)
  65.     if (parent == null) { 
  66.         black(node);
  67.         return;
  68.     }
  70.     // ------------- 一共 12 种情况--------------
  71.     // 不需要处理的4种情况: 如果父节点是黑色, 直接返回
  72.     if (isBlack(parent)) return;
  74.     // 根据uncle节点的颜色来判断其他的各4种情况
  75.     Node<K, V> uncle = parent.sibling();
  76.     // 祖父节点
  77.     Node<K, V> grand = parent.parent;
  79.     // 需要处理的4种情况: 叔父节点是红色
  80.     if (isRed(uncle)) { 
  81.         black(parent);
  82.         black(uncle);
  83.         // 把祖父节点染成红色, 当做新添加的节点处理(递归调用afterAdd)
  84.         afterPut(red(grand));
  85.         return;
  86.     }
  88.     /* 因为这4种情况, RBTree需要对节点进行旋转操作; 此时就需要使用到AVLTree中的旋转代码, 因为AVLTree和RBTree都是平衡二叉搜索树(BalanceBinarySearchTree),BBST在BST的基础上增加了旋转功能; 为了程序的拓展性, 我们在创建一个BBST 继承 BST, AVLTree和RBTree再 继承 BBST */
  89.     // 需要处理的4种情况: 叔父节点不是红色(叔父节点为空)
  90.     if (parent.isLeftChild()) {  // L
  91.         // LL,LR, grand都要染成红色
  92.         red(grand);
  93.         if (node.isLeftChild()) {  // LL
  94.             black(parent);
  95.         } else {  // LR
  96.             black(node);
  97.             rotateLeft(parent);
  98.         }
  99.         // LL,LR, grand最后都要右旋转
  100.         rotateRight(grand);
  101.     } else {  // R
  102.         red(grand);
  103.         if (node.isLeftChild()) {  // RL
  104.             black(node);
  105.             rotateRight(parent);
  106.         } else {  // RR
  107.             black(parent);
  108.         }
  109.         rotateLeft(grand);
  110.     }
  111. }
  113. /** * @return 返回值等于0, 代表e1=e2 * 大于0,代表e1>e2 * 小于0,代表e1<e2 */
  114. private int compare(K k1, K k2) { 
  115.     if (comparator != null) {  // 这里表示传入了比较器
  116.         // 优先使用比较器
  117.         return comparator.compare(k1, k2);
  118.     }
  119.     // 这里表示没有使用比较器,此时再强制将传入的元素实现Comparable接口,并重写接口中的方法
  120.     //return ((Comparable<E>) k1).compareTo(k2);
  121.     return ((Comparable<K>) k1).compareTo(k2);
  122. }

3、get方法实现

  • 通过key先找到node节点，然后再返回节点的值。

    @Override
    public V get(K key) { 

    1. Node<K, V> node = node(key);
    2. return node != null ? node.value : null;

    }

4、remove方法实现

  • 先通过key找到节点，然后再删除节点。

    @Override
    public V remove(K key) { 

    1. return remove(node(key));

    }

    private V remove(Node node) { 

    1. if (node == null) return null;
    2. // node 不为空, 必然要删除结点, 先size--;
    3. size--;
    5. V oldValue = node.value;
    7. // 删除node是度为2的结点
    8. if (node.hasTwoChildren()) { 
    9.     /*//1 找到后继(也可以找到前驱) Node<E> successor = successor(node); //2 用后继结点的值覆盖度为2结点的值 node.element = successor.element; //3 删除后继节点 node = successor;*/
    11.     //1、找到前驱
    12.     Node<K, V> predecessor = predecessor(node);
    13.     //2、用前驱节点的值覆盖度为2节点的值
    14.     node.key = predecessor.key;
    15.     node.value = predecessor.value;
    16.     //3、删除前驱节点
    17.     node = predecessor;
    18. }
    19. // 删除node,即删除后继节点 (node节点必然是度为1或0)
    20. // 因为node只有一个子节点/0个子节点, 如果其left!=null, 则用node.left来替代, node.left==null, 用node.right来替代,
    21. // 若node为叶子节点, 说明, node.left==null, node.right也为null, 则replacement==null;
    22. Node<K, V> replacement = node.left != null ? node.left : node.right;
    24. // 删除node是度为1的结点
    25. if (replacement != null) { 
    26.     // 更改parent
    27.     replacement.parent = node.parent;
    28.     // 更改parent的left、right的指向
    29.     if (node.parent == null) {   // node是度为1且是根节点
    30.         root = replacement;
    31.     } else if (node == node.parent.left) { 
    32.         node.parent.left = replacement;
    33.     } else if (node == node.parent.right) { 
    34.         node.parent.right = replacement;
    35.     }
    36.     // 删除结点之后的处理
    37.     afterRemove(node, replacement);
    38.     // 删除node是叶子节点, 且是根节点
    39. } else if (node.parent == null) { 
    40.     root = null;
    41.     // 删除结点之后的处理
    42.     afterRemove(node, null);
    43. } else {  // node是叶子结点, 且不是根节点
    44.     if (node == node.parent.left) { 
    45.         node.parent.left = null;
    46.     } else {   // node == node.parent.right
    47.         node.parent.right = null;
    48.     }
    49.     // 删除结点之后的处理
    50.     afterRemove(node, null);
    51. }
    52. return oldValue;

    }

    private void afterRemove(Node node, Node replacement) { 

    1. // 删除的节点, 都是叶子节点
    3. // 如果删除的节点为红色,则不需要处理
    4. if (isRed(node)) return;
    6. // 用于取代node的节点replacement为红色
    7. if (isRed(replacement)) { 
    8.     // 将替代节点染为黑色
    9.     black(replacement);
    10.     return;
    11. }
    13. // 删除的是根节点
    14. Node<K, V> parent = node.parent;
    15. if (parent == null) return;
    17. // 删除黑色的叶子节点(肯定会下溢)
    18. // 判断被删除的node是左还是右(如果直接通过sibling()方法,拿到的不准确,因为在remove方法中已经将node置为null了,然后才调用的afterRemove
    19. boolean left = parent.left == null || node.isLeftChild();
    20. Node<K, V> sibling = left ? parent.right : parent.left;
    21. if (left) {  // 被删除的节点在左边, 兄弟节点在右边
    22.     if (isRed(sibling)) { 
    23.         black(sibling);
    24.         red(parent);
    25.         rotateLeft(parent);
    26.         sibling = parent.right;
    27.     }
    28.     // 兄弟节点必然是黑色
    29.     if (isBlack(sibling.left) && isBlack(sibling.right)) {   // 表示node的黑兄弟节点的left,right子节点都是黑节点
    30.         boolean parentBlack = isBlack(parent);
    31.         black(parent);
    32.         red(sibling);
    33.         if (parentBlack) { 
    34.             afterRemove(parent, null);
    35.         }
    36.     } else {  // 表示兄弟节点至少有一个红色子节点,可以向被删除节点的位置借一个节点
    37.         if (isBlack(sibling.right)) { 
    38.             rotateRight(sibling);
    39.             sibling = parent.right;
    40.         }
    41.         color(sibling, colorOf(parent));
    42.         black(sibling.right);
    43.         black(parent);
    44.         rotateLeft(parent);
    45.     }
    46. } else {  // 被删除节点在右边, 兄弟节点在左边
    47.     if (isRed(sibling)) {  // 兄弟节点是红色
    48.         black(sibling);
    49.         red(parent);
    50.         rotateRight(parent); // 旋转之后,改变兄弟节点,然后node的兄弟节点就为黑色了
    51.         // 更换兄弟节点
    52.         sibling = parent.left;
    53.     }
    55.     // 兄弟节点必然是黑色
    56.     if (isBlack(sibling.left) && isBlack(sibling.right)) {   // 表示node的黑兄弟节点的left,right子节点都是黑节点
    57.         // 兄弟节点没有一个红色子节点(不能借一个节点给你), 父节点要向下跟node的兄弟节点合并
    58.         /* 首先这里要判断父节点parent的颜色(如果为parent为红色,则根据B树红色节点向其黑色父节点合并原则,parent向下合并,肯定不会 发生下溢; 如果parent为黑色,则说明parent向下合并后,必然也会发生下溢,这里我们当作移除一个叶子结点处理,复用afterRemove */
    59.         boolean parentBlack = isBlack(parent);
    60.         // 下面两行染色的代码,是说明parent为红色的情况
    61.         black(parent);
    62.         red(sibling);
    63.         if (parentBlack) { 
    64.             afterRemove(parent, null);
    65.         }
    67.     } else {  // 表示兄弟节点至少有一个红色子节点,可以向被删除节点的位置借一个节点
    68.         // 兄弟节点的左边是黑色, 先将兄弟节点左旋转; 旋转完之后和后面两种的处理方式相同,都是再对父节点进行右旋转
    69.         if (isBlack(sibling.left)) { 
    70.             rotateLeft(sibling);
    71.             sibling = parent.left; // 因为旋转之后,要更改node的sibling,才能复用下面的染色代码.不然出现bug
    72.         }
    73.         // 旋转之后的中心节点继承parent的颜色; 旋转之后的左右节点染为黑色
    74.         // 先染色,再旋转: 肯定要先对node的sibling先染色
    75.         color(sibling, colorOf(parent));
    76.         black(sibling.left);
    77.         black(parent);
    78.         rotateRight(parent);
    79.     }
    80. }

    }

    /* 传入key找到对应红黑树对应的结点, 然后取出k红黑树节点的value @param key @return /
    private Node node(K key) { 

    1. Node<K, V> node = root;
    2. while (node != null) { 
    3.     int cmp = compare(key, node.key);
    4.     if (cmp == 0) return node;
    5.     if (cmp > 0) {   // 说明key对应的结点, 比node的key大, 所以去它的右子树找
    6.         node = node.right;
    7.     } else { 
    8.         node = node.left;
    9.     }
    10. }
    11. return null; // 没有找到key对应的结点

    }

5、contains方法实现

  • 因为value没有可比较性，所以containsValue只有通过树的遍历来查找value是否存在。

    @Override
    public boolean containsKey(K key) { 

    1. return node(key) != null;

    }

    @Override
    public boolean containsValue(V value) { 

    1. if (root == null) return false;
    3. // 层序遍历代码
    4. Queue<Node<K, V>> queue = new LinkedList<>();
    5. queue.offer(root);
    7. while (!queue.isEmpty()) { 
    8.     Node<K, V> node = queue.poll();
    9.     if (valEquals(value, node.value))
    10.         return true; // 说明存在
    12.     if (node.left != null)
    13.         queue.offer(node.left);
    15.     if (node.right != null)
    16.         queue.offer(node.right);
    17. }
    18. return false;

    }

    private boolean valEquals(V v1, V v2) { 

    1. // 如果v1==null,说明为true, 走v2==null, v2等于null的话, 说明v1和v2相等, v2不等于空的话, 返回false
    2. // 如果v1!=null, 直接判断v1.equals(v2)是否相等
    3. return v1 == null ? v2 == null : v1.equals(v2);

    }

6、traversal方法实现

  • 中序遍历

    @Override
    public void traversal(Visitor visitor) { 

    1. if (visitor == null) return;
    2. traversal(root, visitor);

    }

    private void traversal(Node node, Visitor visitor) { 

    1. if (node == null || visitor.stop) return;
    3. traversal(node.left, visitor);
    4. if (visitor.stop) return;
    5. visitor.visit(node.key, node.value);
    6. traversal(node.right, visitor);

    }

7、旋转代码

  1. /** * 对node进行左旋转 * * @param grand */
  2. private void rotateLeft(Node<K, V> grand) { 
  3.     Node<K, V> parent = grand.right;
  4.     Node<K, V> child = parent.left;
  5.     grand.right = child;
  6.     parent.left = grand;
  8.     afterRotate(grand, parent, child);
  9. }
  11. /** * 对node进行右旋转 * * @param grand */
  12. private void rotateRight(Node<K, V> grand) { 
  13.     Node<K, V> parent = grand.left;
  14.     Node<K, V> child = parent.right;
  15.     grand.left = child;
  16.     parent.right = grand;
  18.     afterRotate(grand, parent, child);
  19. }
  21. /** * 旋转之后, 更新它们的parent; 并且更新旋转后的高度 * * @param grand * @param parent * @param child */
  22. private void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) { 
  23.     // 让parent为子树的根节点
  24.     parent.parent = grand.parent;
  25.     // 如果grand是其父节点的left, 则将grand.parent.left = parent;
  26.     if (grand.isLeftChild()) { 
  27.         grand.parent.left = parent;
  28.     } else if (grand.isRightChild()) { 
  29.         grand.parent.right = parent;
  30.         // grand是根节点
  31.     } else { 
  32.         root = parent;
  33.     }
  35.     // 更新child的parent
  36.     if (child != null)
  37.         child.parent = grand;
  39.     // 更新grand的parent
  40.     grand.parent = parent;
  41. }

8、寻找节点的前驱和后继

  1. /** * 根据传入的节点, 返回该节点的前驱节点 (中序遍历) * * @param node * @return */
  2. private Node<K, V> predecessor(Node<K, V> node) { 
  3.     if (node == null) return node;
  5.     // (中序遍历)前驱节点在左子树当中(node.left.right.right.right...)
  6.     Node<K, V> p = node.left;
  7.     // 左子树存在
  8.     if (p != null) { 
  9.         while (p.right != null) { 
  10.             p = p.right;
  11.         }
  12.         return p;
  13.     }
  15.     // 程序走到这里说明左子树不存在; 从父节点、祖父节点中寻找前驱节点
  16.     /* * node的父节点不为空 && node是其父节点的左子树时. 就一直往上寻找它的父节点 * 因为node==node.parent.right, 说明你在你父节点的右边, 那么node.parent就是其node的前驱节点 */
  17.     while (node.parent != null && node == node.parent.left) { 
  18.         node = node.parent;
  19.     }
  21.     // 能来到这里表示: 两种情况如下
  22.     // node.parent == null 表示没有父节点(根节点),返回空 ==> return node.parent;
  23.     // node==node.parent.right 说明你在你父节点的右边, 那么node.parent就是其node的前驱节点 ==> return node.parent;
  24.     return node.parent;
  25. }
  27. /** * 根据传入的节点, 返回该节点的后驱节点 (中序遍历) * * @param node * @return */
  28. private Node<K, V> successor(Node<K, V> node) { 
  29.     if (node == null) return node;
  31.     Node<K, V> p = node.right;
  32.     if (p != null) { 
  33.         while (p.left != null) { 
  34.             p = p.left;
  35.         }
  36.         return p;
  37.     }
  39.     // node.right为空
  40.     while (node.parent != null && node == node.parent.right) { 
  41.         node = node.parent;
  42.     }
  44.     return node.parent;
  45. }

9、红黑树辅助方法

  1. /** * 将node染成color色 * * @param node 需要染色的节点 * @param color 染成的颜色 * @return 返回染色的节点 */
  2. private Node<K, V> color(Node<K, V> node, boolean color) { 
  3.     if (node == null) return node;
  4.     node.color = color;
  5.     return node;
  6. }
  8. /** * 传进来的节点染成黑色 * * @param node * @return */
  9. private Node<K, V> black(Node<K, V> node) { 
  10.     return color(node, BLACK);
  11. }
  13. /** * 传进来的节点染成红色 * * @param node * @return */
  14. private Node<K, V> red(Node<K, V> node) { 
  15.     return color(node, RED);
  16. }
  18. /** * 返回当前节点的颜色 * * @param node * @return 如果传入的节点为空, 默认为黑色 */
  19. private boolean colorOf(Node<K, V> node) { 
  20.     return node == null ? BLACK : node.color;
  21. }
  23. /** * 节点是否为黑色 * * @param node * @return */
  24. private boolean isBlack(Node<K, V> node) { 
  25.     return colorOf(node) == BLACK;
  26. }
  28. /** * 节点是否为红色 * * @param node * @return */
  29. private boolean isRed(Node<K, V> node) { 
  30.     return colorOf(node) == RED;
  31. }

10、测试

  1. /** * Description: 测试自己实现的TreeMap * * @author guizy1 * @date 2020/12/9 15:43 */
  2. public class Main { 
  4.     // 测试TreeMap来实现TreeSet
  5.     @Test
  6.     public void test3() { 
  7.         Set<Integer> treeSet = new TreeSet<>();
  8.         treeSet.add(1);
  9.         treeSet.add(7);
  10.         treeSet.add(3);
  11.         treeSet.add(7);
  12.         treeSet.add(0);
  14.         treeSet.traversal(new Set.Visitor<Integer>() { 
  15.             @Override
  16.             public boolean visit(Integer element) { 
  17.                 System.out.println(element);
  18.                 return false;
  19.             }
  20.         });
  21.     }
  23.     @Test
  24.     public void test1() { 
  25.         Map<String, Integer> map = new TreeMap<>();
  26.         map.put("c", 2);
  27.         map.put("a", 5);
  28.         map.put("b", 6);
  29.         map.put("a", 8);
  31.         map.traversal(new Map.Visitor<String, Integer>() { 
  32.             @Override
  33.             public boolean visit(String key, Integer value) { 
  34.                 System.out.println(key + "_" + value);
  35.                 return false;
  36.             }
  37.         });
  38.     }
  40.     @Test
  41.     public void test2() { 
  42.         FileInfo fileInfo = Files.read("D:\\tree-structure\\tree\\src",
  43.                 new String[]{ "java"});
  45.         System.out.println("文件数量：" + fileInfo.getFiles());
  46.         System.out.println("代码行数：" + fileInfo.getLines());
  47.         String[] words = fileInfo.words();
  48.         System.out.println("单词数量：" + words.length);
  50.         Map<String, Integer> map = new TreeMap<>();
  51.         for (int i = 0; i < words.length; i++) { 
  52.             Integer count = map.get(words[i]);
  53.             // count = count == null ? 0 : count + 1;
  54.             // map.put(words[i], count + 1);
  55.             count = (count == null) ? 1 : (count + 1);
  56.             map.put(words[i], count);
  57.         }
  59.         map.traversal(new Map.Visitor<String, Integer>() { 
  60.             public boolean visit(String key, Integer value) { 
  61.                 System.out.println(key + "_" + value);
  62.                 return false;
  63.             }
  64.         });
  65.     }
  66. }

七、TreeMap代码(完整)

  1. package com.map.
  3. import java.util.Comparator;
  4. import java.util.LinkedList;
  5. import java.util.Queue;
  7. /** * Description: TreeMap使用红黑树来实现, 红黑树的节点中存储的是key-value键值对 * * @author guizy1 * @date 2020/12/9 15:48 */
  8. @SuppressWarnings("all")
  9. public class TreeMap<K, V> implements Map<K, V> { 
  11.     private static final boolean RED = false;
  12.     private static final boolean BLACK = true;
  14.     private int size;
  16.     // 定义根节点
  17.     private Node<K, V> root;
  19.     private Comparator<K> comparator; // 定义一个比较器
  21.     public TreeMap() { 
  22.         this(null);
  23.     }
  25.     public TreeMap(Comparator<K> comparator) { 
  26.         this.comparator = comparator;
  27.     }
  29.     public int size() { 
  30.         return size;
  31.     }
  33.     public boolean isEmpty() { 
  34.         return size == 0;
  35.     }
  37.     public void clear() { 
  38.         root = null;
  39.         size = 0;
  40.     }
  42.     /** * 想TreeMap中添加一个结点 * * @param key 键 * @param value 值 * @return 返回之前被覆盖的值 */
  43.     @Override
  44.     public V put(K key, V value) { 
  45.         keyNotNullCheck(key);
  47.         // 添加第一个节点
  48.         if (root == null) { 
  49.             // 给根节点赋值,且根节点没有父节点
  50.             root = new Node<>(key, value, null);
  51.             size++;
  53.             // 添加节点之后的处理
  54.             afterPut(root);
  55.             return null;
  56.         }
  58.         // 添加的不是第一个节点
  59.         Node<K, V> parent = root; // 这个是第一次比较的父节点
  60.         Node<K, V> node = root;
  61.         int cmp = 0;
  62.         while (node != null) { 
  63.             cmp = compare(key, node.key);   // 两者具体比较的方法
  64.             parent = node; // 记录其每一次比较的父节点
  65.             if (cmp > 0) { 
  66.                 // 插入的元素大于根节点的元素,插入到根节点的右边
  67.                 node = node.right;
  68.             } else if (cmp < 0) { 
  69.                 // 插入的元素小于根节点的元素,插入到根节点的左边
  70.                 node = node.left;
  71.             } else {  // 相等
  72.                 node.key = key;
  73.                 V oldValue = node.value;
  74.                 node.value = value;
  75.                 return oldValue; // 返回之前node的value
  76.             }
  77.         }
  78.         // 看看插入到父节点的哪个位置
  79.         Node<K, V> newNode = new Node<>(key, value, parent);
  80.         if (cmp > 0) { 
  81.             parent.right = newNode;
  82.         } else { 
  83.             parent.left = newNode;
  84.         }
  85.         size++;
  87.         // 添加节点之后的逻辑
  88.         afterPut(newNode);
  89.         // 这里的key是第一次加进去的, 之前没有值, 所以返回null
  90.         return null;
  91.     }
  93.     @Override
  94.     public V get(K key) { 
  95.         Node<K, V> node = node(key);
  96.         return node != null ? node.value : null;
  97.     }
  99.     @Override
  100.     public V remove(K key) { 
  101.         return remove(node(key));
  102.     }
  104.     @Override
  105.     public boolean containsKey(K key) { 
  106.         return node(key) != null;
  107.     }
  109.     @Override
  110.     public boolean containsValue(V value) { 
  111.         if (root == null) return false;
  113.         // 层序遍历代码
  114.         Queue<Node<K, V>> queue = new LinkedList<>();
  115.         queue.offer(root);
  117.         while (!queue.isEmpty()) { 
  118.             Node<K, V> node = queue.poll();
  119.             if (valEquals(value, node.value))
  120.                 return true; // 说明存在
  122.             if (node.left != null)
  123.                 queue.offer(node.left);
  125.             if (node.right != null)
  126.                 queue.offer(node.right);
  127.         }
  128.         return false;
  129.     }
  131.     @Override
  132.     public void traversal(Visitor<K, V> visitor) { 
  133.         if (visitor == null) return;
  134.         traversal(root, visitor);
  135.     }
  137.     private void traversal(Node<K, V> node, Visitor<K, V> visitor) { 
  138.         if (node == null || visitor.stop) return;
  140.         traversal(node.left, visitor);
  141.         if (visitor.stop) return;
  142.         visitor.visit(node.key, node.value);
  143.         traversal(node.right, visitor);
  144.     }
  146.     private boolean valEquals(V v1, V v2) { 
  147.         // 如果v1==null,说明为true, 走v2==null, v2等于null的话, 说明v1和v2相等, v2不等于空的话, 返回false
  148.         // 如果v1!=null, 直接判断v1.equals(v2)是否相等
  149.         return v1 == null ? v2 == null : v1.equals(v2);
  150.     }
  152.     private void afterPut(Node<K, V> node) { 
  153.         Node<K, V> parent = node.parent;
  155.         // 添加的是根节点(染成黑色)
  156.         if (parent == null) { 
  157.             black(node);
  158.             return;
  159.         }
  161.         // ------------- 一共 12 种情况--------------
  162.         // 不需要处理的4种情况: 如果父节点是黑色, 直接返回
  163.         if (isBlack(parent)) return;
  165.         // 根据uncle节点的颜色来判断其他的各4种情况
  166.         Node<K, V> uncle = parent.sibling();
  167.         // 祖父节点
  168.         Node<K, V> grand = parent.parent;
  170.         // 需要处理的4种情况: 叔父节点是红色
  171.         if (isRed(uncle)) { 
  172.             black(parent);
  173.             black(uncle);
  174.             // 把祖父节点染成红色, 当做新添加的节点处理(递归调用afterAdd)
  175.             afterPut(red(grand));
  176.             return;
  177.         }
  179.         /* 因为这4种情况, RBTree需要对节点进行旋转操作; 此时就需要使用到AVLTree中的旋转代码, 因为AVLTree和RBTree都是平衡二叉搜索树(BalanceBinarySearchTree),BBST在BST的基础上增加了旋转功能; 为了程序的拓展性, 我们在创建一个BBST 继承 BST, AVLTree和RBTree再 继承 BBST */
  180.         // 需要处理的4种情况: 叔父节点不是红色(叔父节点为空)
  181.         if (parent.isLeftChild()) {  // L
  182.             // LL,LR, grand都要染成红色
  183.             red(grand);
  184.             if (node.isLeftChild()) {  // LL
  185.                 black(parent);
  186.             } else {  // LR
  187.                 black(node);
  188.                 rotateLeft(parent);
  189.             }
  190.             // LL,LR, grand最后都要右旋转
  191.             rotateRight(grand);
  192.         } else {  // R
  193.             red(grand);
  194.             if (node.isLeftChild()) {  // RL
  195.                 black(node);
  196.                 rotateRight(parent);
  197.             } else {  // RR
  198.                 black(parent);
  199.             }
  200.             rotateLeft(grand);
  201.         }
  203.     }
  205.     private void afterRemove(Node<K, V> node, Node<K, V> replacement) { 
  206.         // 删除的节点, 都是叶子节点
  208.         // 如果删除的节点为红色,则不需要处理
  209.         if (isRed(node)) return;
  211.         // 用于取代node的节点replacement为红色
  212.         if (isRed(replacement)) { 
  213.             // 将替代节点染为黑色
  214.             black(replacement);
  215.             return;
  216.         }
  218.         // 删除的是根节点
  219.         Node<K, V> parent = node.parent;
  220.         if (parent == null) return;
  222.         // 删除黑色的叶子节点(肯定会下溢)
  223.         // 判断被删除的node是左还是右(如果直接通过sibling()方法,拿到的不准确,因为在remove方法中已经将node置为null了,然后才调用的afterRemove
  224.         boolean left = parent.left == null || node.isLeftChild();
  225.         Node<K, V> sibling = left ? parent.right : parent.left;
  226.         if (left) {  // 被删除的节点在左边, 兄弟节点在右边
  227.             if (isRed(sibling)) { 
  228.                 black(sibling);
  229.                 red(parent);
  230.                 rotateLeft(parent);
  231.                 sibling = parent.right;
  232.             }
  233.             // 兄弟节点必然是黑色
  234.             if (isBlack(sibling.left) && isBlack(sibling.right)) {   // 表示node的黑兄弟节点的left,right子节点都是黑节点
  235.                 boolean parentBlack = isBlack(parent);
  236.                 black(parent);
  237.                 red(sibling);
  238.                 if (parentBlack) { 
  239.                     afterRemove(parent, null);
  240.                 }
  241.             } else {  // 表示兄弟节点至少有一个红色子节点,可以向被删除节点的位置借一个节点
  242.                 if (isBlack(sibling.right)) { 
  243.                     rotateRight(sibling);
  244.                     sibling = parent.right;
  245.                 }
  246.                 color(sibling, colorOf(parent));
  247.                 black(sibling.right);
  248.                 black(parent);
  249.                 rotateLeft(parent);
  250.             }
  251.         } else {  // 被删除节点在右边, 兄弟节点在左边
  252.             if (isRed(sibling)) {  // 兄弟节点是红色
  253.                 black(sibling);
  254.                 red(parent);
  255.                 rotateRight(parent); // 旋转之后,改变兄弟节点,然后node的兄弟节点就为黑色了
  256.                 // 更换兄弟节点
  257.                 sibling = parent.left;
  258.             }
  260.             // 兄弟节点必然是黑色
  261.             if (isBlack(sibling.left) && isBlack(sibling.right)) {   // 表示node的黑兄弟节点的left,right子节点都是黑节点
  262.                 // 兄弟节点没有一个红色子节点(不能借一个节点给你), 父节点要向下跟node的兄弟节点合并
  263.                 /* 首先这里要判断父节点parent的颜色(如果为parent为红色,则根据B树红色节点向其黑色父节点合并原则,parent向下合并,肯定不会 发生下溢; 如果parent为黑色,则说明parent向下合并后,必然也会发生下溢,这里我们当作移除一个叶子结点处理,复用afterRemove */
  264.                 boolean parentBlack = isBlack(parent);
  265.                 // 下面两行染色的代码,是说明parent为红色的情况
  266.                 black(parent);
  267.                 red(sibling);
  268.                 if (parentBlack) { 
  269.                     afterRemove(parent, null);
  270.                 }
  272.             } else {  // 表示兄弟节点至少有一个红色子节点,可以向被删除节点的位置借一个节点
  273.                 // 兄弟节点的左边是黑色, 先将兄弟节点左旋转; 旋转完之后和后面两种的处理方式相同,都是再对父节点进行右旋转
  274.                 if (isBlack(sibling.left)) { 
  275.                     rotateLeft(sibling);
  276.                     sibling = parent.left; // 因为旋转之后,要更改node的sibling,才能复用下面的染色代码.不然出现bug
  277.                 }
  278.                 // 旋转之后的中心节点继承parent的颜色; 旋转之后的左右节点染为黑色
  279.                 // 先染色,再旋转: 肯定要先对node的sibling先染色
  280.                 color(sibling, colorOf(parent));
  281.                 black(sibling.left);
  282.                 black(parent);
  283.                 rotateRight(parent);
  284.             }
  285.         }
  286.     }
  288.     private V remove(Node<K, V> node) { 
  289.         if (node == null) return null;
  290.         // node 不为空, 必然要删除结点, 先size--;
  291.         size--;
  293.         V oldValue = node.value;
  295.         // 删除node是度为2的结点
  296.         if (node.hasTwoChildren()) { 
  297.             /*//1 找到后继(也可以找到前驱) Node<E> successor = successor(node); //2 用后继结点的值覆盖度为2结点的值 node.element = successor.element; //3 删除后继节点 node = successor;*/
  299.             //1、找到前驱
  300.             Node<K, V> predecessor = predecessor(node);
  301.             //2、用前驱节点的值覆盖度为2节点的值
  302.             node.key = predecessor.key;
  303.             node.value = predecessor.value;
  304.             //3、删除前驱节点
  305.             node = predecessor;
  306.         }
  307.         // 删除node,即删除后继节点 (node节点必然是度为1或0)
  308.         // 因为node只有一个子节点/0个子节点, 如果其left!=null, 则用node.left来替代, node.left==null, 用node.right来替代,
  309.         // 若node为叶子节点, 说明, node.left==null, node.right也为null, 则replacement==null;
  310.         Node<K, V> replacement = node.left != null ? node.left : node.right;
  312.         // 删除node是度为1的结点
  313.         if (replacement != null) { 
  314.             // 更改parent
  315.             replacement.parent = node.parent;
  316.             // 更改parent的left、right的指向
  317.             if (node.parent == null) {   // node是度为1且是根节点
  318.                 root = replacement;
  319.             } else if (node == node.parent.left) { 
  320.                 node.parent.left = replacement;
  321.             } else if (node == node.parent.right) { 
  322.                 node.parent.right = replacement;
  323.             }
  324.             // 删除结点之后的处理
  325.             afterRemove(node, replacement);
  326.             // 删除node是叶子节点, 且是根节点
  327.         } else if (node.parent == null) { 
  328.             root = null;
  329.             // 删除结点之后的处理
  330.             afterRemove(node, null);
  331.         } else {  // node是叶子结点, 且不是根节点
  332.             if (node == node.parent.left) { 
  333.                 node.parent.left = null;
  334.             } else {   // node == node.parent.right
  335.                 node.parent.right = null;
  336.             }
  337.             // 删除结点之后的处理
  338.             afterRemove(node, null);
  339.         }
  340.         return oldValue;
  341.     }
  343.     /** * 根据传入的节点, 返回该节点的前驱节点 (中序遍历) * * @param node * @return */
  344.     private Node<K, V> predecessor(Node<K, V> node) { 
  345.         if (node == null) return node;
  347.         // (中序遍历)前驱节点在左子树当中(node.left.right.right.right...)
  348.         Node<K, V> p = node.left;
  349.         // 左子树存在
  350.         if (p != null) { 
  351.             while (p.right != null) { 
  352.                 p = p.right;
  353.             }
  354.             return p;
  355.         }
  357.         // 程序走到这里说明左子树不存在; 从父节点、祖父节点中寻找前驱节点
  358.         /* * node的父节点不为空 && node是其父节点的左子树时. 就一直往上寻找它的父节点 * 因为node==node.parent.right, 说明你在你父节点的右边, 那么node.parent就是其node的前驱节点 */
  359.         while (node.parent != null && node == node.parent.left) { 
  360.             node = node.parent;
  361.         }
  363.         // 能来到这里表示: 两种情况如下
  364.         // node.parent == null 表示没有父节点(根节点),返回空 ==> return node.parent;
  365.         // node==node.parent.right 说明你在你父节点的右边, 那么node.parent就是其node的前驱节点 ==> return node.parent;
  366.         return node.parent;
  367.     }
  369.     /** * 根据传入的节点, 返回该节点的后驱节点 (中序遍历) * * @param node * @return */
  370.     private Node<K, V> successor(Node<K, V> node) { 
  371.         if (node == null) return node;
  373.         Node<K, V> p = node.right;
  374.         if (p != null) { 
  375.             while (p.left != null) { 
  376.                 p = p.left;
  377.             }
  378.             return p;
  379.         }
  381.         // node.right为空
  382.         while (node.parent != null && node == node.parent.right) { 
  383.             node = node.parent;
  384.         }
  386.         return node.parent;
  387.     }
  390.     /** * 传入key找到对应红黑树对应的结点, 然后取出k红黑树节点的value * * @param key * @return */
  391.     private Node<K, V> node(K key) { 
  392.         Node<K, V> node = root;
  393.         while (node != null) { 
  394.             int cmp = compare(key, node.key);
  395.             if (cmp == 0) return node;
  396.             if (cmp > 0) {   // 说明key对应的结点, 比node的key大, 所以去它的右子树找
  397.                 node = node.right;
  398.             } else { 
  399.                 node = node.left;
  400.             }
  401.         }
  402.         return null; // 没有找到key对应的结点
  403.     }
  405.     /** * @return 返回值等于0, 代表e1=e2 * 大于0,代表e1>e2 * 小于0,代表e1<e2 */
  406.     private int compare(K k1, K k2) { 
  407.         if (comparator != null) {  // 这里表示传入了比较器
  408.             // 优先使用比较器
  409.             return comparator.compare(k1, k2);
  410.         }
  411.         // 这里表示没有使用比较器,此时再强制将传入的元素实现Comparable接口,并重写接口中的方法
  412.         //return ((Comparable<E>) k1).compareTo(k2);
  413.         return ((Comparable<K>) k1).compareTo(k2);
  414.     }
  416.     /** * 对node进行左旋转 * * @param grand */
  417.     private void rotateLeft(Node<K, V> grand) { 
  418.         Node<K, V> parent = grand.right;
  419.         Node<K, V> child = parent.left;
  420.         grand.right = child;
  421.         parent.left = grand;
  423.         afterRotate(grand, parent, child);
  424.     }
  426.     /** * 对node进行右旋转 * * @param grand */
  427.     private void rotateRight(Node<K, V> grand) { 
  428.         Node<K, V> parent = grand.left;
  429.         Node<K, V> child = parent.right;
  430.         grand.left = child;
  431.         parent.right = grand;
  433.         afterRotate(grand, parent, child);
  434.     }
  436.     /** * 旋转之后, 更新它们的parent; 并且更新旋转后的高度 * * @param grand * @param parent * @param child */
  437.     private void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) { 
  438.         // 让parent为子树的根节点
  439.         parent.parent = grand.parent;
  440.         // 如果grand是其父节点的left, 则将grand.parent.left = parent;
  441.         if (grand.isLeftChild()) { 
  442.             grand.parent.left = parent;
  443.         } else if (grand.isRightChild()) { 
  444.             grand.parent.right = parent;
  445.             // grand是根节点
  446.         } else { 
  447.             root = parent;
  448.         }
  450.         // 更新child的parent
  451.         if (child != null)
  452.             child.parent = grand;
  454.         // 更新grand的parent
  455.         grand.parent = parent;
  456.     }
  459.     /** * 将node染成color色 * * @param node 需要染色的节点 * @param color 染成的颜色 * @return 返回染色的节点 */
  460.     private Node<K, V> color(Node<K, V> node, boolean color) { 
  461.         if (node == null) return node;
  462.         node.color = color;
  463.         return node;
  464.     }
  466.     /** * 传进来的节点染成黑色 * * @param node * @return */
  467.     private Node<K, V> black(Node<K, V> node) { 
  468.         return color(node, BLACK);
  469.     }
  471.     /** * 传进来的节点染成红色 * * @param node * @return */
  472.     private Node<K, V> red(Node<K, V> node) { 
  473.         return color(node, RED);
  474.     }
  476.     /** * 返回当前节点的颜色 * * @param node * @return 如果传入的节点为空, 默认为黑色 */
  477.     private boolean colorOf(Node<K, V> node) { 
  478.         return node == null ? BLACK : node.color;
  479.     }
  481.     /** * 节点是否为黑色 * * @param node * @return */
  482.     private boolean isBlack(Node<K, V> node) { 
  483.         return colorOf(node) == BLACK;
  484.     }
  486.     /** * 节点是否为红色 * * @param node * @return */
  487.     private boolean isRed(Node<K, V> node) { 
  488.         return colorOf(node) == RED;
  489.     }
  491.     private void keyNotNullCheck(K key) { 
  492.         if (key == null) { 
  493.             // 手动抛出异常对象
  494.             throw new IllegalArgumentException("key must not be null");
  495.         }
  496.     }
  498.     private static class Node<K, V> { 
  499.         K key;
  500.         V value;
  501.         boolean color = RED;
  502.         Node<K, V> left;
  503.         Node<K, V> right;
  504.         Node<K, V> parent;
  506.         public Node(K key, V value, Node<K, V> parent) { 
  507.             this.key = key;
  508.             this.value = value;
  509.             this.parent = parent;
  510.         }
  512.         public boolean isLeaf() { 
  513.             return left == null && right == null;
  514.         }
  516.         public boolean hasTwoChildren() { 
  517.             return left != null && right != null;
  518.         }
  520.         public boolean isLeftChild() { 
  521.             return parent != null && this == parent.left;
  522.         }
  524.         public boolean isRightChild() { 
  525.             return parent != null && this == parent.right;
  526.         }
  528.         public Node<K, V> sibling() { 
  529.             if (isLeftChild()) { 
  530.                 return parent.right;
  531.             }
  533.             if (isRightChild()) { 
  534.                 return parent.left;
  535.             }
  536.             return null;
  537.         }
  538.     }
  539. }

发表评论

表情：
评论列表 （有 0 条评论，37人围观）

还没有评论，来说两句吧...

相关阅读