动力节点旗下在线教育品牌  |  咨询热线:400-8080-105 学Java全栈,上蛙课网
首页 > 文章

java JDK中的红黑树

06-16 18:33 428浏览
举报 T字号
  • 大字
  • 中字
  • 小字

要想了解Java JDK中的红黑树,我们先要弄懂什么是红黑树。红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。了解了何谓红黑树之后,再来了解Java JDK中的红黑树也就变得通俗易懂了。

红黑树除了具有一般二叉查找树的特性,红黑树还具有以下特性:

  1.每个节点要么是黑色要么是红色

  2.根节点是黑色

  3:每个叶子节点是黑色,并且为空节点(还有另外一种说法就是,每个叶子结点都带有两个空的黑色结点(被称为黑哨兵),如果一个结点n的只有一个左孩子,那么n的右孩子是一个黑哨兵;如果结点n只有一个右孩子,那么n的左孩子是一个黑哨兵。)

  4:如果一个节点是红色,则它的子节点必须是黑色

  5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

除此之外我们需要注意的是:

1.特性3中指定红黑树的每个叶子节点都是空节点,但是在Java实现中红黑树将使用null代表空节点,因此遍历红黑树时看不到黑色的叶子节点,反而见到的叶子节点是红色的

2.特性4保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍,例如黑色高度为3的红黑树,其最短路径(路径指的是根节点到叶子节点)是2(黑节点-黑节点-黑节点),其最长路径为4(黑节点-红节点-黑节点-红节点-黑节点)。

实践出真知,我们来看一个红黑树应用实例: JDK中基于红黑树实现的TreeMap.jdk8内部数据结构为数组+(链表 或 红黑树),通过key的hash值计算数据所在数组下标,多个key的hash相同或hash计算的数组下标相同,但是key值不同时,检查节点是否为树节点,是树节点则往树节点添加,如果是普通节点则往链表尾追加Entry,当链表长度大于8时,则将链表转为红黑树。

 transient Node[] table;

static class Node implements Map.Entry {

    final int hash;

    final K key;

    V value;

    Node next;

}

static final class TreeNode extends LinkedHashMap.Entry {

    TreeNode parent;  // red-black tree links

    TreeNode left;

    TreeNode right;

    TreeNode prev;    // needed to unlink next upon deletion

    boolean red;

}

//LinkedHashMap.Entry

static class Entry extends HashMap.Node {

    Entry before, after;

    Entry(int hash, K key, V value, Node next) {

        super(hash, key, value, next);

    }

}

链表转红黑树过程示意图:

1人推荐
共同学习,写下你的评论
0条评论
在天边
程序员在天边

3篇文章贡献8506字

作者相关文章更多>

推荐相关文章更多>

支付接口的幂等性设计

军哥08-05 15:18

一文梳理REST API的设计原则

军哥09-01 10:54

如何在Linux系统下开发java程序

jessy06-15 17:31

彻底解决java JDK注册表残留问题

天天天天天歌06-15 17:38

浅谈Java设计模式-之-适配器模式

调技师傅09-01 16:47

发评论

举报

0/150

取消