大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 浅谈Java TreeMap

浅谈Java TreeMap(1)

关键词:JavaTreeMap  阅读(2179) 赞(12)

[摘要]本文是对Java提高篇(二七)-----TreeMap的讲解,对学习Java编程技术有所帮助,与大家分享。

TreeMap的完成是红黑树算法的完成,所以要理解TreeMap就必需对红黑树有一定的理解,其实这篇博文的名字叫做:依据红黑树的算法来剖析TreeMap的完成,但是为了与Java进步篇系列博文坚持分歧还是叫做TreeMap比拟好。经过这篇博文你可以取得如下知识点:

1、红黑树的根本概念。

2、红黑树添加节点、删除节点的完成进程。

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

4、Java 中TreeMap是如何经过put、deleteEntry两个来完成红黑树添加、删除节点的。

我想经过这篇博文你对TreeMap一定有了更深的看法。好了,上面先复杂普及红黑树知识。

一、红黑树简介

红黑树又称红-黑二叉树,它首先是一颗二叉树,它详细二叉树一切的特性。同时红黑树更是一颗自均衡的排序二叉树。

我们晓得一颗根本的二叉树他们都需求满足一个根本性质--即树中的任何节点的值大于它的左子节点,且小于它的右子节点。依照这个根本性质使得树的检索效率大大进步。我们晓得在生成二叉树的进程是十分容易失衡的,最坏的状况就是一边倒(只要右/左子树),这样势必会招致二叉树的检索效率大大降低(O(n)),所以为了维持二叉树的均衡,大牛们提出了各种完成的算法,如:AVL,SBT,伸展树,TREAP ,红黑树等等。

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

2014051700001

红黑树望文生义就是节点是白色或许黑色的均衡二叉树,它经过颜色的约束来维持着二叉树的均衡。关于一棵无效的红黑树二叉树而言我们必需添加如下规则:

1、每个节点都只能是白色或许黑色

2、根节点是黑色

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

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

5、从任一节点到其每个叶子的一切途径都包括相反数目的黑色节点。

这些约束强迫了红黑树的关键性质: 从根到叶子的最长的能够途径不多于最短的能够途径的两倍长。后果是这棵树大致上是均衡的。由于操作比方拔出、删除和查找某个值的最坏状况工夫都要求与树的高度成比例,这个在高度上的实际下限允许红黑树在最坏状况下都是高效的,而不同于普通的二叉查找树。所以红黑树它是复杂而高效的,其检索效率O(log n)。下图为一颗典型的红黑二叉树。

2014051700002

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

2014051700004                          2014051700005

左旋                                                                    右旋

(图片来自:http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html)


本节参考文献:http://baike.baidu.com/view/133754.htm?fr=aladdin-----百度百科

注:由于本文次要是解说Java中TreeMap,所以并没有对红黑树停止十分深化的理解和研讨,假如诸位想对其停止愈加深化的研讨Lz提供几篇较好的博文:

1、红黑树系列集锦

2、红黑树数据构造分析

3、红黑树

二、TreeMap数据构造

>>>>>>回归配角:TreeMap<<<<<<

TreeMap的定义如下:

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap承继AbstractMap,完成NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap标明TreeMap为一个Map即支持key-value的集合, NavigableMap(更多)则意味着它支持一系列的导航办法,具有针对给定搜索目的前往最接近婚配项的导航办法 。

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

//比拟器,由于TreeMap是有序的,经过comparator接口我们可以对TreeMap的外部排序停止精细的控制
        private final Comparator<? super K> comparator;
        //TreeMap红-黑节点,为TreeMap的外部类
        private transient Entry<K,V> 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<K,V> left = null;
        //右孩子
        Entry<K,V> right = null;
        //父亲
        Entry<K,V> parent;
        //颜色
        boolean color = BLACK;

注:后面只是开胃菜,上面是本篇博文的重中之重,在上面两节我将重点解说treeMap的put()、delete()办法。经过这两个办法我们会理解红黑树添加、删除节点的中心算法。

三、TreeMap put()办法

在理解TreeMap的put()办法之前,我们先理解红黑树添加节点的算法。

红黑树添加节点

红黑树在新增节点进程中比拟复杂,复杂归复杂它异样必需要根据下面提到的五点标准,同时由于规则1、2、3根本都会满足,上面我们次要讨论规则4、5。假定我们这里有一棵最复杂的树,我们规则新增的节点为N、它的父节点为P、P的兄弟节点为U、P的父节点为G。

2014051700007

关于新节点的拔出有如下三个关键中央:

  • 1、拔出新节点总是白色节点 。
  • 2、假如拔出节点的父节点是黑色, 能维持性质 。
  • 3、假如拔出节点的父节点是白色, 毁坏了性质. 故拔出算法就是经过重新着色或旋转, 来维持性质 。

    为了保证上面的论述愈加明晰和依据便于参考,我这里将红黑树的五点规则再贴一遍:

  • 1、每个节点都只能是白色或许黑色

  • 2、根节点是黑色

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

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

  • 5、从任一节点到其每个叶子的一切途径都包括相反数目的黑色节点。

  • 一、为跟节点
  • 若新拔出的节点N没有父节点,则直接当做依据节点拔出即可,同时将颜色设置为黑色。(如图一(1))

    二、父节点为黑色

    这种状况新节点N异样是直接拔出,同时颜色为白色,由于依据规则四它会存在两个黑色的叶子节点,值为null。同时由于新增节点N为白色,所以经过它的子节点的途径仍然会保管着相反的黑色节点数,异样满足规则5。(如图一(2))

    2014051700008

    (图一)

    三、若父节点P和P的兄弟节点U都为白色

    关于这种状况若直接拔出一定会呈现不均衡景象。怎样处置?P、U节点变黑、G节点变红。这时由于经过节点P、U的途径都必需经过G所以在这些途径下面的黑节点数目还是相反的。但是经过下面的处置,能够G节点的父节点也是白色,这个时分我们需求将G节点当做新增节点递归处置。

    2014051700009

    四、若父节点P为白色,叔父节点U为黑色或许短少,且新增节点N为P节点的右孩子

    关于这种状况我们对新增节点N、P停止一次左旋转。这里所发生的后果其实并没有完成,还不是均衡的(违背了规则四),这是我们需求停止状况5的操作。

    20140517000010

  • 五、父节点P为白色,叔父节点U为黑色或许短少,新增节点N为父节点P左孩子

    这种状况有能够是由于状况四而发生的,也有能够不是。关于这种状况先已P节点为中心停止右旋转,在旋转后发生的树中,节点P是节点N、G的父节点。但是这棵树并不标准,它违背了规则4,所以我们将P、G节点的颜色停止交流,使之其满足标准。开端时一切的途径都需求经过G其他们的黑色节点数一样,但是如今一切的途径改为经过P,且P为整棵树的独一黑色节点,所以调整后的树异样满足标准5。

    20140517000011

    下面展现了红黑树新增节点的五种状况,这五种状况涵盖了一切的新增能够,不论这棵红黑树多么复杂,都可以依据这五种状况来停止生成。上面就来剖析Java中的TreeMap是如何来完成红黑树的。

    TreeMap put()办法完成剖析

    在TreeMap的put()的完成办法中次要分为两个步骤,第一:构建排序二叉树,第二:均衡二叉树。

  • 关于排序二叉树的创立,其添加节点的进程如下:

  • 1、以根节点为初始节点停止检索。

  • 2、与以后节点停止比对,若新增节点值较大,则以以后节点的右子节点作为新的以后节点。否则以以后节点的左子节点作为新的以后节点。

  • 3、循环递归2步骤晓得检索出适宜的叶子节点为止。

  • 4、将新增节点与3步骤中找到的节点停止比对,假如新增节点较大,则添加为右子节点;否则添加为左子节点。

  • 依照这个步骤我们就可以将一个新增节点添加到排序二叉树中适宜的地位。如下:

  • «上一页1234下一页»


    相关评论