请选择 进入手机版 | 继续访问电脑版

JAVA Map详解之TreeMap(红黑树)

[复制链接]
唐少琼 发表于 2021-1-1 10:30:12 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
前言

上一章的HashMap并没有提到红黑树,就是因为本章的TreeMap就是一棵红黑树。TreeMap是存储键值对(key-value结构)的自平衡二叉树,又称红黑树。TreeMap的key是有序且不可为空的,但是value是可以为空的。TreeMap的类图结构如下

TreeMap类上的注释有两个地方需要注意:
1.TreeMap是一个基于NavigableMap实现的红黑树,TreeMap的排序方式有两种:(1)基于key的自然排序(2)在创建TreeMap的时候提供一个比较器,使用哪种排序取决于你使用的哪种构造方法,也就是默认无参构造方法基于自然排序,如果key是自界说对象,要么你的自界说对象是已经实现了Comparable接口或在创建TreeMap时提供一个Comparator的实现
  1. /**A Red-Black tree based {@link NavigableMap} implementation.* The map is sorted according to the {@linkplain Comparable natural* ordering} of its keys, or by a {@link Comparator} provided at map* creation time, depending on which constructor is used.*/
复制代码
2.TreeMap的实现不是同步的,实在也就是多线程不安全的。如果多线程同时访问一个映射,而且举行了结构性的修改,那么它必须时同步的(结构性修改是指添加大概删除一个或多个映射,修改已经存在的key的值不算是结构性修改)。而且注释给出的多线程安全使用TreeMap的方式是SortedMap m = Collections.synchronizedSortedMap(new TreeMap(…));
  1. /**
  2. [b]Note that this implementation is not synchronized.[/b]* If multiple threads access a map concurrently, and at least one of the* threads modifies the map structurally, it [i]must[/i] be synchronized* externally.  (A structural modification is any operation that adds or* deletes one or more mappings; merely changing the value associated* with an existing key is not a structural modification.)  This is* typically accomplished by synchronizing on some object that naturally* encapsulates the map.*/
复制代码
红黑树TreeMap

红黑树的界说

首先红黑树是一棵特殊的二叉查找树,二叉查找树的每个节点键值大于左孩子的键值,小于或即是右孩子的键值;二叉查找树在特殊情况下所有子节点都在左边大概右边,这被称为二叉查找树的左倾或右倾,极度情况下,二叉查找树就酿成了一个有序的链表了,而红黑树呢通过对二叉查找树的着色,将二叉查找树酿成了一棵相对平衡的树,不会出现左倾或右倾的情况:
(1) 每个节点大概是黑色,大概是赤色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]
(4) 如果一个节点是赤色的,则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
TreeMap中红黑树的节点元素包含自身的键值对,左右孩子节点,父节点,节点默认黑色满足条件3

TreeMap如何添加元素

TreeMap的put方法
[code]public V put(K key, V value) {    // 取类对象实例的根节点    Entry t = root;    // 若根节点为空    if (t == null) {        // 调用比较方法,看看当前key值是否可比较,不可比较抛出ClassCastException,key为空抛出NullPointerException异常        compare(key, key); // type (and possibly null) check        // 将当前节点当作根节点        root = new Entry(key, value, null);        size = 1;        modCount++;        return null;    }    // 如果根节点不为空    int cmp;    Entry parent;    // split comparator and comparable paths    Comparator
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )