TreeMap源码分析(四)【循环遍历】

Scroll Down

二叉树的遍历

image

  • 前序遍历:500->300->100->200->400->800->600->700->1000->900->1100->1200根->左->右
  • 中序遍历:100->200->300->400->500->600->700->800->900->1000->1100->1200 左->根->右
  • 后序遍历:200->100->400->300->700->600->900->1200->1100->1000->800->500左->右->根

TreeMap的循环遍历

public void forEach(BiConsumer<? super K, ? super V> action) {
    Objects.requireNonNull(action);
    // 修改次数
    int expectedModCount = modCount;
    // 循环遍历
    for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
        action.accept(e.key, e.value);

        // 判断在循环时内部数据是否发生了改变
        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }
    }
}
// 获取第一个元素
final Entry<K,V> getFirstEntry() {
    // root
    Entry<K,V> p = root;
    if (p != null)
        // 一直查找左子节点
        while (p.left != null)
            p = p.left;
    return p;
}
// 获取后序节点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    // 判断是否为空
    if (t == null)
        return null;
    // 判断右子节点是否为空
    else if (t.right != null) {
        // 获取右子节点
        Entry<K,V> p = t.right;
        // 循环获取左子节点
        while (p.left != null)
            p = p.left;
        return p;
    // 右子节点为空
    } else {
        // 获取父节点
        Entry<K,V> p = t.parent;
        // 当前节点
        Entry<K,V> ch = t;
        // 当前节点是父节点的右子节点
        while (p != null && ch == p.right) {
            // 当前节点为父节点
            ch = p;
            // 父节点设置为祖父节点
            p = p.parent;
        }
        // 返回父节点
        return p;
    }
}
  1. 首先,寻找第一个元素,因为红黑树是接近平衡的二叉树,所以找最小的节点,相当于是从顶到底了,时间复杂度为O(log n);
  2. 其次,寻找后继节点,因为红黑树插入元素的时候会自动平衡,最坏的情况就是寻找右子树中最小的节点,时间复杂度为O(log k),k为右子树元素个数;
  3. 最后,需要遍历所有元素,时间复杂度为O(n);
  4. 所以,总的时间复杂度为 O(log n) + O(n * log k) ≈ O(n)。

总结

  • 红黑树特性
    1. 每个节点或者是黑色,或者是红色。
    2. 根节点是黑色。
    3. 每个叶子节点(NIL)是黑色。(注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!)
    4. 如果一个节点是红色的,则它的子节点必须是黑色的。
    5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
  • TreeMap的特性
    1. TreeMap的存储结构只有一颗红黑树;
    2. TreeMap中的元素是有序的,按key的顺序排列;
    3. TreeMap比HashMap要慢一些,因为HashMap前面还做了一层桶,寻找元素要快很多;
    4. TreeMap没有扩容的概念;
    5. TreeMap的遍历不是采用传统的递归式遍历;
    6. TreeMap可以按范围查找元素,查找最近的元素;