博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
TreeMap
阅读量:5862 次
发布时间:2019-06-19

本文共 9422 字,大约阅读时间需要 31 分钟。

TreeMap

TreeMap 的实现是红黑树算法的实现,所以要了解 TreeMap 就必须对红黑树有一定的了解。

其实这篇博文的名字叫做:根据红黑树的算法来分析 TreeMap 的实现,但是为了与 Java 提高篇系列博文保持一致还是叫做 TreeMap 比较好。通过这篇博文你可以获得如下知识点:

  • 1、红黑树的基本概念。

  • 2、红黑树增加节点、删除节点的实现过程。

  • 3、红黑树左旋转、右旋转的复杂过程。

  • 4、Java 中 TreeMap 是如何通过 put、deleteEntry 两个来实现红黑树增加、删除节点的。

我想通过这篇博文你对 TreeMap 一定有了更深的认识。好了,下面先简单普及红黑树知识。

红黑树简介

红黑树又称红-黑二叉树,它首先是一颗二叉树,它具体二叉树所有的特性。同时红黑树更是一颗自平衡的排序二叉树。

我们知道一颗基本的二叉树他们都需要满足一个基本性质–即树中的任何节点的值大于它的左子节点,且小于它的右子节点。

按照这个基本性质使得树的检索效率大大提高。我们知道在生成二叉树的过程是非常容易失衡的,最坏的情况就是一边倒(只有右/左子树),这样势必会导致二叉树的检索效率大大降低(O(n)),所以为了维持二叉树的平衡,大牛们提出了各种实现的算法,如:AVL,SBT,伸展树,TREAP ,红黑树等等。

平衡二叉树必须具备如下特性:它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1,并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个等等子节点,其左右子树的高度都相近。

红黑树顾名思义就是节点是红色或者黑色的平衡二叉树,它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树二叉树而言我们必须增加如下规则:

  • 1、每个节点都只能是红色或者黑色

  • 2、根节点是黑色

  • 3、每个叶节点(NIL 节点,空节点)是黑色的。

  • 4、如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

  • 5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。所以红黑树它是复杂而高效的,其检索效率 O(log n)。下图为一颗典型的红黑二叉树。

对于红黑二叉树而言它主要包括三大基本操作:左旋、右旋、着色。

注:由于本文主要是讲解 Java 中 TreeMap,所以并没有对红黑树进行非常深入的了解和研究,如果诸位想对其进行更加深入的研究Lz提供几篇较好的博文:

1、

2、

3、

二、TreeMap 数据结构

public class TreeMap
extends AbstractMap
implements NavigableMap
, Cloneable, java.io.Serializable复制代码

TreeMap 继承 AbstractMap,实现 NavigableMap、Cloneable、Serializable 三个接口。其中 AbstractMap 表明 TreeMap 为一个 Map 即支持 key-value 的集合,NavigableMap(更多)则意味着它支持一系列的导航方法,具备针对给定搜索目标返回最接近匹配项的导航方法 。

TreeMap 中同时也包含了如下几个重要的属性:

//比较器,因为TreeMap是有序的,通过comparator接口我们可以对TreeMap的内部排序进行精密的控制        private final Comparator
comparator; //TreeMap红-黑节点,为TreeMap的内部类 private transient Entry
root = null; //容器大小 private transient int size = 0; //TreeMap修改次数 private transient int modCount = 0; //红黑树的节点颜色--红色 private static final boolean RED = false; //红黑树的节点颜色--黑色 private static final boolean BLACK = true;复制代码

对于叶子节点 Entry 是 TreeMap 的内部类,它有几个重要的属性:

//键            K key;            //值            V value;            //左孩子            Entry
left = null; //右孩子 Entry
right = null; //父亲 Entry
parent; //颜色 boolean color = BLACK;复制代码

注:前面只是开胃菜,下面是本篇博文的重中之重,在下面两节我将重点讲解 treeMap 的 put()、delete() 方法。通过这两个方法我们会了解红黑树增加、删除节点的核心算法。

TreeMap put() 方法

在了解 TreeMap 的 put() 方法之前,我们先了解红黑树增加节点的算法。

红黑树增加节点

红黑树在新增节点过程中比较复杂,复杂归复杂它同样必须要依据上面提到的五点规范,同时由于规则 1、2、3 基本都会满足,下面我们主要讨论规则 4、5。假设我们这里有一棵最简单的树,我们规定新增的节点为 N、它的父节点为 P、P 的兄弟节点为 U、P 的父节点为 G。

新增N 父节点P P的兄弟U P的父节点G

  • 插入新节点总为红色
  • 如果插入节点的父节点是黑色,能维持性质
  • 如果插入节点的父节点是红色,破坏了性质。插入算法着色或旋转
public V put(K key, V value) {                //用t表示二叉树的当前节点                Entry
t = root; //t为null表示一个空树,即TreeMap中没有任何元素,直接插入 if (t == null) { compare(key, key); // type (and possibly null) check //将新的key-value键值对创建为一个Entry节点,并将该节点赋予给root root = new Entry<>(key, value, null); //容器的size = 1,表示TreeMap集合中存在一 个元素 size = 1; //修改次数 + 1 modCount++; return null; } //cmp表示key排序的返回结果 int cmp; //父节点 Entry
parent; // split comparator and comparable paths Comparator
cpr = comparator; //指定的排序算法 //如果cpr不为空,则采用既定的排序算法进行创建TreeMap集合 if (cpr != null) { //排序二叉树 do { parent = t; //parent指向上次循环后的t //比较新增节点的key和当前节点key的大小 cmp = cpr.compare(key, t.key); //cmp返回值小于0,表示新增节点的key小于当前节点的key,则以当前节点的左子节点作为新的当前节点 if (cmp < 0) t = t.left; //cmp返回值大于0,表示新增节点的key大于当前节点的key,则以当前节点的右子节点作为新的当前节点 else if (cmp > 0) t = t.right; //cmp返回值等于0,表示两个key值相等,则新值覆盖旧值,并返回新值 else return t.setValue(value); } while (t != null); } //如果cpr为空,则采用默认的排序算法进行创建 TreeMap集合 else { if (key == null) //key值为空抛出异常 throw new NullPointerException(); /* 下面处理过程和上面一样 */ Comparable
k = (Comparable
) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } //将新增节点当做parent的子节点 Entry
e = new Entry<>(key, value, parent); //如果新增节点的key小于parent的key,则当做左子节点 if (cmp < 0) parent.left = e; //如果新增节点的key大于parent的key,则当做右子节点 else parent.right = e; /* * 上面已经完成了排序二叉树的的构建,将新增节点 插入该树中的合适位置 * 下面fixAfterInsertion()方法就是对这棵树进行调整、平衡,具体过程参考上面的五种情况 */ fixAfterInsertion(e); //TreeMap元素数量 + 1 size++; //TreeMap容器修改次数 + 1 modCount++; return null; }复制代码

do{} 代码块是实现排序二叉树的核心算法,通过该算法我们可以确认新增节点在该树的正确位置。

红黑树是一棵平衡排序二叉树,普通的排序二叉树可能会出现失衡的情况,所以下一步就是要进行调整。fixAfterInsertion(e); 调整的过程务必会涉及到红黑树的左旋、右旋、着色三个基本操作。代码如下:

/**         * 新增节点后的修复操作         * x 表示新增节点         */         private void fixAfterInsertion(Entry
x) { x.color = RED; //新增节点的颜色为红色 //循环 直到 x不是根节点,且x的父节点不为红色 while (x != null && x != root && x.parent.color == RED) { //如果X的父节点(P)是其父节点的父节点(G)的左节点 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //获取X的叔节点(U) Entry
y = rightOf(parentOf (parentOf(x))); //如果X的叔节点(U) 为红色(情况三) if (colorOf(y) == RED) { //将X的父节点(P)设置为黑色 setColor(parentOf(x), BLACK); //将X的叔节点(U)设置为黑色 setColor(y, BLACK); //将X的父节点的父节点(G)设置红色 setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } //如果X的叔节点(U为黑色);这里会存在 两种情况(情况四、情况五) else { //如果X节点为其父节点(P)的右子 树,则进行左旋转(情况四) if (x == rightOf(parentOf(x))) { //将X的父节点作为X x = parentOf(x); //右旋转 rotateLeft(x); } //(情况五) //将X的父节点(P)设置为黑色 setColor(parentOf(x), BLACK); //将X的父节点的父节点(G)设置红色 setColor(parentOf(parentOf(x)), RED); //以X的父节点的父节点(G)为中心右旋转 rotateRight(parentOf(parentOf(x))); } } //如果X的父节点(P)是其父节点的父节点(G的右节点) else { //获取X的叔节点(U) Entry
y = leftOf(parentOf(parentOf(x))); //如果X的叔节点(U) 为红色(情况三) if (colorOf(y) == RED) { //将P、U设为黑色,G设为黑色 //将X的父节点(P)设置为黑色 setColor(parentOf(x), BLACK); //将X的叔节点(U)设置为黑色 setColor(y, BLACK); //将X的父节点的父节点(G)设置红色 setColor(parentOf(parentOf(x)), RED); // x = parentOf(parentOf(x)); } //如果X的叔节点(U为黑色);这里会存在两种情况(情况四、情况五) else { //如果X节点为其父节点(P)的右子树,则进行左旋转(情况四) if (x == leftOf(parentOf(x))) { //将X的父节点作为X x = parentOf(x); //右旋转 rotateRight(x); } //(情况五) //将X的父节点(P)设置为黑色 setColor(parentOf(x), BLACK); //将X的父节点的父节点(G)设置红色 setColor(parentOf(parentOf(x)), RED); //以X的父节点的父节点(G)为中心右旋转 rotateLeft(parentOf(parentOf(x))); } } } //将根节点G强制设置为黑色 root.color = BLACK; }复制代码

转载于:https://juejin.im/post/5c0fa63ce51d451f327c8d40

你可能感兴趣的文章
老生常谈一下在AD中细粒度设置密码策略
查看>>
大侠唐在飞:WIN8试用记
查看>>
MongoDB介绍
查看>>
【ZooKeeper Notes 13】ZooKeeper Watcher的事件通知类型
查看>>
WPF-003 popup实现下拉列表的问题
查看>>
WEB应用的安全的登录认证
查看>>
Apache的httpd-2.4.23 Server源文件安装
查看>>
VR+醫療MRI
查看>>
《统一沟通-微软-技巧》-19-Lync 2010如何使用智能手机中联系人
查看>>
SCCM2012SP1---分发部署软件
查看>>
活动目录长时间未复制链接丢失解决办法
查看>>
19.Azure备份Azure上的虚拟机(上)
查看>>
自定义javascript调试输出函数
查看>>
云计算让教学随需应变
查看>>
linux下用tar进行数据备份
查看>>
单臂路由实现vlan之间的通信
查看>>
AMD:“全民四核”大作战
查看>>
微信账号,欢迎一起探讨信息、知识、学习和管理!
查看>>
Puppet基础篇7-编写第一个完整测试模块puppet
查看>>
用Saltstack的returners实现批量监控和数据存储
查看>>