谈谈对红黑树的理解

发布于:2021-10-22 18:35:57

? ?上节说了,HashMap存储的时候,如果链表的长度过长,就会将链表转换成红黑树,那么对红黑树有什么理解呢?


1.每个节点非红即黑。


2.根节点总是黑色的。


3.如果节点是红色的,那么它的子节点必须是黑色的(反之不一定)。


4.每个叶子节点都是黑色的空节点(NIL节点)。


5.从根节点到叶节点或空节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)。


想到这里,又有了问题,既然使用红黑树是可行的,为什么不一直使用红黑树呢?


? ? ? ?我们知道,红黑树属于*衡二叉树,为了保持*衡是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以长度大于8的时候会使用红黑树,而当链表长度很短时,遍历链表的速度要更快一点,所以为了效率的提高,不会一直使用红黑树。


那么,拉链法导致的链表过深,为什么不适用二叉树来代替呢?


? ? ? ?这是因为二叉查找树有缺陷:二叉查找树在特殊情况下会变成一条线性结构,遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋,变色这些操作来保持*衡,而我们是为了解决链表查询深度的问题,引入红黑树就是为了查找数据快,因此选择红黑树来替换过长的链表。


?



转载于:https://www.cnblogs.com/liushaojie/p/10273679.html

相关推荐

最新更新

猜你喜欢