专栏首页FREE SOLOHashMap在jdk1.8为何引入了红黑树?

HashMap在jdk1.8为何引入了红黑树?

二叉查找树

二叉查找树,也称有序二叉树(ordered binary tree),或已排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 任意节点的左、右子树也分别为二叉查找树。 没有键值相等的节点(no duplicate nodes)。

因为一棵由n个结点随机构造的二叉查找树的高度为lgn,所以顺理成章,二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后,则这些操作最坏情况运行时间为O(n)。

avl树即平衡树,他对二叉树做了改进,在我们每插入一个节点的时候,必须保证每个节点对应的左子树和右子树的树高度差不超过1。如果超过了就对其进行调平衡,具体的调平衡操作就不在这里讲了,无非就是四个操作——左旋,左旋再右旋,右旋再左旋。

如图所示,图中M结点就是一个二节点,M左边的EJ节点是一个三节点。依然是大的数据放右边,小的数据放左边。此时我们向该树重如果该数可以直接放入二节点中,就直接进去,但如果正好需要放在三节点中,就像图中一样,Z正好要放在SX中。那么我们需要将该节点分裂成两个节点,并将中间的数提到父节点中去,就像图中将X放在了R旁边。当然如果将子节点提到父节点的时候导致了父节点里的数超过了两个,就继续向上提,直到满足了为止。

在jdk1.8版本后,java对HashMap做了改进,在链表长度大于8的时候,将后面的数据存在红黑树中,以加快检索速度,我们接下来讲一下红黑树。

红黑树虽然本质上是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。加快检索速率。

红黑树的5个性质:

1.每个结点要么是红的要么是黑的。 2.根结点是黑的。 3.每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。 4.如果一个结点是红的,那么它的两个儿子都是黑的。 5. 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

红黑树还可以描述成: ⑴红链接均为左链接。 ⑵没有任何一个结点同时和两条红链接相连。 ⑶该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同。 这里节点之间的连接分为红连接和黑连接,取代了红节点和黑节点的定义(本质是一样的),将之前的黑高度相等定义为了黑连接数相等。更为直观。 而如图所示,其实红黑树的每一步操作都对应了二三树的操作,如果是二节点就是黑连接,三节点的话里面的两个数之间就是红连接。

红黑树相比avl树,在检索的时候效率其实差不多,都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡,他允许局部很少的不完全平衡,这样对于效率影响不大,但省去了很多没有必要的调平衡操作,avl树调平衡有时候代价较大,所以效率不如红黑树。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 计算机网络中的A类、B类、C类地址的划分

    A类地址的第一组数字为1~126。注意,数字0和 127不作为A类地址,数字127保留给内部回送函数,而数字0则表示该地址是本地宿主机,不能传送。

    葆宁
  • Java集合(3)---Java集合ArrayList

    ArrayList 是一个数组队列,相当于 动态数组。与Java中的数组相比,它的容量能动态增长。它继承于AbstractList,实现了List, Rando...

    葆宁
  • JVM中的新生代和老年代

    JVM在程序运行过程当中,会创建大量的对象,这些对象,大部分是短周期的对象,小部分是长周期的对象,对于短周期的对象,需要频繁地进行垃圾回收以保证无用对象尽早被释...

    葆宁
  • 算法基础7:平衡查找树概述

    算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第7篇《平衡查找树概述》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法...

    大数据和云计算技术
  • 求助大佬:用sstap连不上是什么情况

    用xshell5弄好之后用sstap链接测试一直显示失败,端口全部开通也是不行,求助各位大佬,这个是什么情况,我已经试了一晚上了还是不行

    用户7017404
  • 数据结构 之 树总结

       特点:二叉树每个节点最多只有两个子节点, 分为左右子树, 且左子树 < 节点 < 右子树。

    菜的黑人牙膏
  • jit即使编译语言调用c++

    sofu456
  • 各种树的区别

    二叉查找树就是左结点小于根节点,右结点大于根节点的一种排序树,也叫二叉搜索树。也叫BST,英文Binary Sort Tree。

    用户1637228
  • ORA-28002的一个细节

    有一个库,由于设置了PASSWORD_LIFE_TIME,且到期未重置密码,账户被锁了,手工解锁后,登录发现报错ORA-28002,明明解锁了,为何还会报错?

    bisal
  • 「科技」新型石墨烯材料出现,未来汽车可能有夜视功能

    镁客网

扫码关注云+社区

领取腾讯云代金券