0901（044天 集合框架08 树TreeMap）

0901（044天 集合框架08 树TreeMap）

每日一狗（田园犬西瓜瓜）

集合框架08 树TreeMap

1. 树

满二叉树：全都满了，只有度为0/2的节点，2^k-1

完全二叉树：除了最后一层其它层是一个满二叉树，最后一层从左往右插入

1.1 二叉搜索树

二叉搜索树BST：

定义：一个二叉树中，任意节点的值要大于等于左子树所有节点的值（左节点最小）

引入原因：为了解决双向链表的递归检索问题。

二叉树的特点

• 左 小 右 大
• 左 > 根 > 右

插入数据

平衡二叉树

二叉树在极端情况下会退化为单向链表，在此之内引入了平衡树的概念，左右子树的高度差最大为1，然后左右子树也都是一个平衡二叉树。

使用左旋右旋算法解决二叉树的不平衡问题。

1.2 红黑树：

一种近似平衡的二叉树，插入删除插入都快。

为了减少左旋右旋的代价，提出了红黑树

问：红黑树的概念

• 节点不是红就是黑
• 根节点永远是黑的
• 叶子到根节点不能有连续两个红节点
• 补全的节点到根节点的黑节点数量相同

问：特殊方法

获取特殊节点的特殊方法

• 获取第一个节点
• 获取一个比指定key节点紧邻大一点的一个节点
• 获取一个比指定key节点紧邻小一点的一个节点

问：HashMap和TreeMap的综合使用

一般就直接先用HashMap，当你需要全局顺序时在转换成TreeMap进行使用。

1.3 总结：HashMap、TreeMap和Hashtable

不同点

1. 元素特性：
2. 顺序特性：
3. 初始化和增长方式：
4. 线程安全：

2. TreeMap

根据红黑树进行实现，与哈希算法无关。元素之间的排序使用传入比较器Comparator的或者元素自身实现了Comparable可比较接口

2.1 一些方法

属性

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left; // 左子树
        Entry<K,V> right;// 右子树
        Entry<K,V> parent;// 父节点
        boolean color = BLACK; // 颜色
}
1
2
3
4
5
6
7
8

构造器

// 无参构造 没有传入比较器
public TreeMap() {
    comparator = null;
}
 传入一个比较器
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}
 传入Map
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

添加元素

使用传入的比较器或元素的比较器进行 二分定位 ，相同即修改。

定位到null时就说面该容器中没有该key值，需要添加节点数据，然后调用染色函数位节点颜色进行修正。

---

扩展小芝士

• 看源码的时候先看构造器，就可以找到一些比较重要的属性