热搜词: 

红黑树的原理,红黑树原理讲解

发布:小编

红黑树的原理

红黑树的原理为:红黑树是一种特定类型的二叉树,它是在计算机科学中用来组织数据比如数字的块的一种结构。所有数据块都存储在节点中。这些节点中的某一个节点总是担当起始位置的功能,称之为根节点或根。

红黑树是一种自平衡二叉查找树,是计算机科学领域中的一种数据结构,典型的用途是实现关联数组,存储有序的数据。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的。它可以在O(logn)时间内做查找,插入和删除,这里的n是树的结点个数。

红黑树原理讲解

性质1: 每个节点要么是 黑色 ,要么是 红色 。

性质2: 根节点是 黑色 。

性质3: 每个叶子节点(NIL)是黑色。

性质4: 每个 红色 节点的两个子节点一定都是 黑色 。

性质5: 任意一个节点到每个叶子节点的路径都包含 数量相同 的 黑节点 。俗称: 黑高 !

从性质5又可以推出:

性质5.1: 如果一个节点存在黑子节点,那么该结点肯定有两个子节点。

插入操作包括两部分工作:

注意: 插入结点,必须为 红色 ,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。如果插入结点是黑色,那么插入位置所在的子树黑色结点总是1,必须做自平衡。

最简单的一种情景,直接把插入结点作为根结点就行

注意: 根据红黑树性质2: 根结点是黑色。还需要把插入结点设为黑色。

处理: 更新当前结点的值,为插入结点的值

由于插入的结点是红色的,当插入结点的父结点为黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。

再次回想红黑树的性质2: 根结点是黑色。如果插入结点的父结点为 红结点 ,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这一点很重要,因为后序的旋转操作肯定需要祖父结点的参与。

依据红黑树 性质4可知,红色结点不能相连===>祖父结点肯定为黑结点

因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为: 红黑红

处理:

1.将P和U结点改为黑色

2.将PP改为红色

3.将PP设置为当前结点,进行后序处理

注意: 单纯从插入前来看,叔叔结点非红即空(NIL结点),否则的话破坏了红黑树性质5,此路径比其它路径多一个黑色结点。

处理:

处理:

该情景对应情景4.2,只是方向反转,直接看图

处理:

处理:

Android面试 HashMap算法

基于hashing的原理,jdk8后采用数组+链表+红黑树的数据结构。我们通过put和get存储和获取对象。当我们给put()方法传递键和值时,先对键做一个hashCode()的计算来得到它在bucket数组中的位置来存储Entry对象。当获取对象时,通过get获取到bucket的位置,再通过键对象的equals()方法找到正确的键值对,然后在返回值对象。

当数组table的size达到阙值时即++size > load factor * capacity 时,也是在putVal函数中。

扩容需要重新分配一个新数组,新数组是老数组的2倍长,然后遍历整个老结构,把所有的元素挨个重新hash分配到新结构中去。

对key的hashCode进行hashing,与运算计算下标获取bucket位置,如果在桶的首位上就可以找到就直接返回,否则在树中找或者链表中遍历找,如果有hash冲突,则利用equals方法去遍历链表查找节点。

对key的hashCode做hash操作,与高16位做异或运算。

还有平方取中法,除留余数法,伪随机数法。

因为数组位置的确定用的是与运算,仅仅最后四位有效,设计者将key的哈希值与高16为做异或运算使得在做&运算确定数组的插入位置时,此时的低位实际是高位与低位的结合,增加了随机性,减少了哈希碰撞的次数。

会产生哈希碰撞,若key值相同则替换旧值,不然链接到链表后面,链表长度超过阙值8就转为红黑树存储。

HashCode相同,通过equals比较内容获取值对象。

超过阙值会进行扩容操作,概括的讲就是扩容后的数组大小是原数组的2倍,将原来的元素重新hashing放入到新的散列表中去。

相同点:都是存储key-value键值对的

不同点:

loadFactor表示HashMap的拥挤程度,影响hash操作到同一个数组位置的概率。默认loadFactor等于0.75,当HashMap里面容纳的元素已经达到HashMap数组长度的75%时,表示HashMap太挤了,需要扩容,在HashMap的构造器中可以定制loadFactor。

JDK 1.8 以前 HashMap 的实现是 数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表有 n 个元素,遍历的时间复杂度就是 O(n),完全失去了它的优势。针对这种情况,JDK 1.8 中引入了 红黑树(查找时间复杂度为 O(logn))来优化这个问题。但是链表大于8的概率是非常非常低的。

选择Integer,String这种不可变的类型,像对String的一切操作都是新建一个String对象,对新的对象进行拼接分割等,这些类已经很规范的覆写了hashCode()以及equals()方法。作为不可变类天生是线程安全的。如果要使用自定义类做为Key,就需要重写hashCode()以及equals()方法。红黑树在做比较的时候使用的是System.identityHashCode()方法,是不需要做特殊处理的。

更多内容戳这里(整理好的各种文集)

以上就是关于红黑树的原理,红黑树原理讲解的全部内容,以及红黑树的原理的相关内容,希望能够帮到您。

大家都在看

查看更多综合百科