精华内容
下载资源
问答
  • 红黑树和哈希表

    2019-11-17 09:53:55
    一、哈希表和红黑树的数据结构分析 前言: hashmap是一种很常用的数据结构,其使用方便快捷,接下来笔者将给大家深入解析这个数据结构,让大家能在用的时候知其然,也知其所以然。 一.Map 首先,从最基本的讲起,...

    一、哈希表和红黑树的数据结构分析

    前言:

    hashmap是一种很常用的数据结构,其使用方便快捷,接下来笔者将给大家深入解析这个数据结构,让大家能在用的时候知其然,也知其所以然。

    一.Map

    首先,从最基本的讲起,我们先来认识一下map是个什么东西。在我们写程序的时候经常会遇到数据检索等操作,对于几百个数据的小程序而言,数据的存储方式或是检索策略没有太大影响,但对于大数据,效率就会差很远。我们来讨论一下这个问题。

    1.线性检索:

    线性检索是最为直白的方法,把所有数据都遍历一遍,然后找到你所需要的数据。其对应的数据结构就是数组,链表等线性结构,这种方式对于大数据而言效率极低,其时间复杂度为O(n)。

    2.二分搜索:

    二分搜索算是对线性搜索的一个改进,比如说对于【1,2,3,4,5,6,7,8】,我要搜索一个数(假设是2),我先将这个数与4(这个数一般选中位数比较好)比较,小于4则在4的左边【1,2,3】中查找,再与2比较,相等,就成功找到了,这种检索方式好处在于可以省去很多不必要的检索,每次只用查找集合中一半的元素。其时间复杂度为O(logn)。但其也有限制,他的数排列本身就需要是有序的。

    3.Hash表中的查找:

    好了,重点来了,Hash表闪亮登场,这是一种时间复杂度为O(1)的检索,就是说不管你数据有多少只需要查一次就可以找到目标数据。是不是很神奇??好吧其实很弱智。大家请看下图。

    大家可以看到这个数组中的值就等于其下标,比如说我要存11,我就把它存在a[11]里面,这样我要找某个数字的时候就直接对应其下标就可以了。这其实是一种牺牲空间换时间的方法,这样会对内存占用比较大,但检索速度极快,只需要搜索一次就能查到目标数据。

    4.Hash表的改变

    看了上面的Hash表你肯定想问,如果我只存一个数10000,那我不是要存在a[10000],这样其他空间不是白白浪废了吗,好吧,不存在的。Hash表已经有了其应对方法,那就是Hash函数。Hash表的本质在于可以通过value本身的特征定位到查找集合的元素下标,从而快速查找。一般的Hash函数为:要存入的数 mod(求余) Hash数组长度。比如说对于上面那个长度为9的数组,12的位置为12 mod 9=3,即存在a3,通过这种方式就可以安放比较大的数据了。

    5.Hash冲突解决策略

    看了上面的讲解,机智的你们肯定已经发现了一个问题,通过求余数得到的地址可能是一样的。这种我们称为Hash冲突,如果数据量比较大而Hash桶比较小,这种冲突就很严重。我们采取如下方式解决冲突问题。

    我们可以看到12和0的位置冲突了,然后我们把该数组的每一个元素变成了一个链表头,冲突的元素放在了链表中,这样在找到对应的链表头之后会顺着链表找下去,至于为什么采用链表,是为了节省空间,链表在内存中并不是连续存储,所以我们可以更充分地使用内存。

    Java之HashMap

    上面讲了那么多,那跟我们今天的主题HashMap有什么关系呢??好了盆友们不要方,进入正题。我们知道HashMap中的值都是key,value对吧,其实这里的存储与上面的很像,key会被映射成数据所在的地址,而value就在以这个地址为头的链表中,这种数据结构在获取的时候就很快。但这里存在的问题就是如果hash桶较小,数据量较大,就会导致链表非常的长。比如说上面的长为11的空间我要放1000个数,无论Hash函数如何精妙,后面跟的链表都会非常的长,这样Hash表的优势就不复存在了,反而倾向于线性检索。好了,红黑树闪亮登场。

    红黑树

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

    avl树

    要了解红黑树,先要知道avl树,要知道avl树,首先要知道二叉树,其实很简单,二叉树就是每个父节点下面有零个一个或两个子节点,大致如下图。

    我们在向二叉树中存放数据的时候将比父节点大的数放在右节点,将比父节点小的数放在左节点,这样之后我们在查找某个数的时候只需要将其与父节点比较,大则进入右边并递归调用,小则进入左边递归。但其存在不足,如果运气很不好我的数据本身就是有序的,比如【1,2,3,4,5,6,7】,这样就会导致树的不平衡,二叉树就会退化成为链表。所以我们推出了avl树。

    avl树即平衡树,他对二叉树做了改进,在我们每插入一个节点的时候,必须保证每个节点对应的左子树和右子树的树高度差不超过1。如果超过了就对其进行调平衡,具体的调平衡操作就不在这里讲了,无非就是四个操作——左旋,左旋再右旋,右旋再左旋。最终可以是二叉树左右两边的树高相近,这样我们在查找的时候就可以按照二分查找来检索,也不会出现退化成链表的情况。

    二三树

    网上有很多讲解红黑树的文章,有各种各样的讲解方式,但博主喜欢把红黑树与二三树放在一起。先来看一下什么是二三树。

    注:该图来自百度

    其实很好理解,二三树与普通二叉树的不同点在于他有二节点和三节点。二节点下面有两个子节点,二节点里面可以容纳一个值,而三节点下面有三个子节点,三节点里面可以容纳两个值。下面来说一下二三数的构建。

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

    红黑树

    红黑树和二三树很相像,基本上就是二三树的一个变形。
    红黑树比较传统的定义是需要满足以下五个特征:
    (1)每个节点或者是黑色,或者是红色。
    (2)根节点是黑色。
    (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
    (4)如果一个节点是红色的,则它的子节点必须是黑色的。
    (5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
    其特点在于给数的每一个节点加上了颜色属性,在插入的过程中通过颜色变换和节点旋转调平衡。其实博主不是很喜欢上面的定义,还有一种视角就是将它与二三树比较。

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

    红黑树的优势

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

    总结

    HashMap在里面就是链表加上红黑树的一种结构,这样利用了链表对内存的使用率以及红黑树的高效检索,是一种很happy的数据结构。

    二、优缺点对比、使用场景
    Hash与Map的区别
    权衡三个因素: 查找速度, 数据量, 内存使用,可扩展性,有序性。
    总体来说,hash查找速度会比RB树快,而且查找速度基本和数据量大小无关,属于常数级别;而RB树的查找速度是log(n)级别。并不一定常数就比log(n) 小,因为hash还有hash函数的耗时。当元素达到一定数量级时,考虑hash。但若你对内存使用特别严格, 希望程序尽可能少消耗内存,那么hash可能会让你陷入尴尬,特别是当你的hash对象特别多时,你就更无法控制了,而且 hash的构造速度较慢。

    红黑树并不适应所有应用树的领域。如果数据基本上是静态的,那么让他们待在他们能够插入,并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的,例如,做一个哈希表,性能可能会更好一些。

    在实际的系统中,例如,需要使用动态规则的防火墙系统,使用红黑树而不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。

    总结:

    红黑树是有序的,Hash是无序的,根据需求来选择。

    红黑树占用的内存更小(仅需要为其存在的节点分配内存),而Hash事先就应该分配足够的内存存储散列表(即使有些槽可能遭弃用)。

    红黑树查找和删除的时间复杂度都是O(logn),Hash查找和删除的时间复杂度都是O(1)。

    补充:

    如果只需要判断Map中某个值是否存在之类的操作,当然是Hash实现的要更加高效。

    如果是需要将两个Map求并集交集差集等大量比较操作,就是红黑树实现的Map更加高效。

    展开全文
  • 以下红黑树资料源于百科: 性质1. 节点是红色或黑色。 性质2. 根节点是黑色。 性质3.所有叶子都是黑色。(叶子是NUIL节点) 性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个...

    以下红黑树资料源于百科:

    性质1. 节点是红色或黑色。
    性质2. 根节点是黑色。 
    性质3.所有叶子都是黑色。(叶子是NUIL节点) 
    性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 
    这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。 
    

    首先从插入删除查找性能来讲:

    红黑树的插入删除查找性能都是O(logN)而哈希表的插入删除查找性能理论上都是O(1),在这个对比上来看,红黑树性能远没有哈希表优秀。但是值得一提的是红黑树从上面介绍的资料来看,他是相对于稳定的,最差情况下都是高效的。而相对于哈希表这个数据结构来讲,哈希表的插入删除操作的理论上时间复杂度是常数时间的,这有个前提就是哈希表不发生数据碰撞。在发生碰撞的最坏的情况下,哈希表的插入和删除时间复杂度最坏能达到O(n)。而在一般情况下,如果在实际应用中,当然一个相对稳定且快速的数据结构是比较理想的选择。

    这里贴一张图 [From https://www.bigocheatsheet.com/]:
    From https://www.bigocheatsheet.com/

    从结构特性来讲:

    红黑树是基于链表的结构,插入删除操作很方便,并且他是一种自动有序的数据结构,插入删除节点会进行自旋,保持当前红黑树节点的有序。而哈希表是基于数组+链表的数据结构,它是无序的。这就是为什么在STL中map与set容器底层是由红黑树实现的,而unordered_map和unordered_set容器底层是由哈希表实现的原因。在C++的STL中 map和set是一种很好用的数据结构,他们是算法题中的常客 也是解题利器,因为它们的底层是是红黑树实现的, 所以他们会根据键值自动排序,这种特性在一定场景下是一个非常有力的工具。

    在STL中,哈希表在插入元素发生碰撞到达一定阈值的时候会进行rehash操作,这个大型操作就十分费时了,它需要增大bucket容量,然后将原有的元素拷贝至新地址中。哈希表的底层应该是使用动态数组,我猜应该是vector之类的容器,而vector的size到达最大容量capacity的时候会进行resize,在大部分编译器中会增大到原来容量的两倍,在少部分编译器中扩大至原来的1.5倍,然后将原有元素拷贝至新分配的地址中,在容器中的元素越多,该操作越费时。

    如果考虑哈希表发生碰撞次数过多的情况,那么哈希表中的几个发生碰撞过多的桶后面链接的链表长度就会很长,这个时候查询和删除元素就需要遍历这几个链表,此时插入删除查询的时间复杂度退化为O(n)。

    所以说hash_map插入查询删除虽然是O(1)的,但是想要达到这个最佳情况,需要保证不发生数据碰撞,或者发生很少的数据碰撞,在这个理想情况下我们需要给哈希表分配大量的空间才可以实现。而从这个方面来讲,基于链表实现的红黑树就拥有很大的优势了。

    所以总的来说哈希表虽然理想情况下的插入删除查询操作都是最佳的,但是它十分消耗空间,并且碰撞达到一定次数会进行rehash,严重影响效率,除非分配非常大的空间,才能缓解碰撞带来的开销(在理论情况下,如果数据量是N,则分配4N的bucket可以做到插入删除的时间复杂度为O(1)。)。而红黑树相对稳定,虽然插入删除查询时间复杂度相对于哈希表来说稍逊一筹,但是还是优于大部分数据结构,并且空间的消耗远低于哈希表,还有最重要的一个特性就是,红黑树是自动有序的。而哈希表无法做到。如何选取这两种数据结构就要在不同场景下进行具体分析了。

    谈一下对于数据结构的理解:

    数据结构没有一种是十分完美的,如果一种结构的时间复杂度十分高效,那么他的空间复杂度就一定相对较高,并且在脱离了特定条件下,他的复杂度就并不一定和原来一样了。所以说如何选取适合的数据结构就要根据特性场景来仔细分析。

    就拿哈希表来举例,在刚学数据结构的时候,最基本的数据结构是数组,他拥有随机访问元素的能力,但是元素的存储是紧挨着的,这就导致他的插入和删除的时间复杂度较高,因为添加删除一个位置的元素需要将后面的所有元素移动,这样开销就很大。而第二个基本的数据结构是链表,他也有自己的优点和缺点。他的优点主要是链式存储,元素的存储并不是连续的,所以删除和插入操作只需要在O(1)的时间复杂度内就能完成(只需要改变链表的后继节点的指向),但是他并不提供随机访问的功能,需要访问特定位置的元素就必须遍历整个链表,这种操作的时间复杂度是O(n),而哈希表就是基于数组和链表来实现的。它的每一个bucket在理想状况下都只存储一个元素,如果发生了数据碰撞,一个bucket就会存储多个元素,这些元素的存储就是采用链表,链表连接在数组的特定位置的元素之后,所以说哈希表就是由数组+链表来实现的。哈希表这种结构很好的结合了数组和链表这两种数据结构的优点,他提供元素的相对随机访问能力,如果不发生数据碰撞(即理想状况下,则访问每个元素的时间复杂度都是O(1),这是利用了数组的优点。并且在理想状况下增加删除元素的时间复杂度也是O(1),这就是利用了链表的优点。

    哈希表的出现就可以带给我们一种思路,这种思路可以用来解决特定的实际问题,就比如说我们可以将数组和链表组合成一种新的数据结构,那么我们也可以将某些数据结构进行组合,合理应用他们的优点来解决实际问题。

    再拿链表来举例,我们知道链表并不能提供随机访问的能力,所以需要访问链表中的任意元素,平均的复杂度是O(n),但是在实际情况下我们不想接受这种遍历的开销。在某些情况下如果只用访问头尾元素,添加一个尾节点就可以让这种访问的时间复杂度为O(1),而如果我们想访问中间节点元素的值,我们再增加一个中节点,就可以让这种访问操作的时间复杂度为O(1)。按照这种思路,我们就可以增加多个节点来作为索引。redis的跳表就是基于这种思想来实现的,通过添加多级索引来降低访问元素的时间复杂度,有兴趣的可以了解一下这种经典的数据结构。

    所以我们学习数据结构可以适当发散自己的思想,举一反三,对症下药,才能选出最佳解决问题的数据结构!

    展开全文
  • 哈希表红黑树的特点及区别

    千次阅读 2018-09-27 22:36:00
    什么是Hash Hash,也可以称为“散列”,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。这是一种压缩映射,也就是,散列值的空间通常远小于输入...而哈希表就是利用数组这个能够快...

    什么是Hash

    Hash,也可以称为“散列”,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。这是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出(也就是多对一的关系)。

    哈希表的构造

    在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。

    "数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一 个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标 的数组空间里,而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分 利用到数组的定位性能进行数据定位。

     

    通过关键字除以槽数m将关键字映射到槽里的方法。哈希函数是H(k)=k Mod m。
    	举个例子,m=12,k=100,H(100)=4。
    	而如果m=2k,那么无论k是什么,H(K)的值都是一个0和奇数,也即是说只要奇数槽和0槽被占用,其他的偶数槽都是浪费掉了。如果m=2^r,那么H(k)的值就是k的低r位(化成二进制)。这样造成的后果是某一个槽有很多的关键字。所以来说一般的m取值尽量不要接近2的整数幂,而且还要是质数。

    虽然我们不希望发生冲突(同一个key有多个value),但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度,而且事先并不知道关键字的具体取值时。冲突就难免会发生。另外,当关键字的实际取值大于哈希表的长度时,而且表中已装满了记录,如果插入一个新记录,不仅发生冲突,而且还会发生溢出。因此,处理冲突和溢出是哈希技术中的两个重要问题。一般有开放地址法、链地址法。

    适用范围   

    快速查找,删除的基本数据结构,通常需要总数据量可以放入内存。

    什么是Map

    Map是c++标准库STL提供的一类关联式容器,提供key-value的存储和查找功能。

    Map是基于红黑树的(同样set也是),那么它的查找速度是log(n)级别的。

    它的优点是占用内存小。

    Hash与Map的区别

    权衡三个因素: 查找速度, 数据量, 内存使用,可扩展性,有序性。
    总体来说,hash查找速度会比RB树快,而且查找速度基本和数据量大小无关,属于常数级别;而RB树的查找速度是log(n)级别。并不一定常数就比log(n) 小,因为hash还有hash函数的耗时。当元素达到一定数量级时,考虑hash。但若你对内存使用特别严格, 希望程序尽可能少消耗内存,那么hash可能会让你陷入尴尬,特别是当你的hash对象特别多时,你就更无法控制了,而且 hash的构造速度较慢。

    红黑树并不适应所有应用树的领域。如果数据基本上是静态的,那么让他们待在他们能够插入,并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的,例如,做一个哈希表,性能可能会更好一些。

    在实际的系统中,例如,需要使用动态规则的防火墙系统,使用红黑树而不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。

    总结:

    红黑树是有序的,Hash是无序的,根据需求来选择。

    红黑树占用的内存更小(仅需要为其存在的节点分配内存),而Hash事先就应该分配足够的内存存储散列表(即使有些槽可能遭弃用)。

    红黑树查找和删除的时间复杂度都是O(logn),Hash查找和删除的时间复杂度都是O(1)。

    补充:

    如果只需要判断Map中某个值是否存在之类的操作,当然是Hash实现的要更加高效。

    如果是需要将两个Map求并集交集差集等大量比较操作,就是红黑树实现的Map更加高效。

    --------------------- 本文来自 ljlstart 的CSDN 博客 ,全文地址请点击:https://blog.csdn.net/ljlstart/article/details/51335687?utm_source=copy

    关于红黑树的介绍,发现一篇文图文并茂的文章 
    https://www.sohu.com/a/201923614_466939 
    多读两遍,相信会有不小的收获

    展开全文
  • 哈希表和红黑树的对比

    万次阅读 2019-06-06 21:48:33
    哈希表 表: 存储数据 key –> value; 用表来存储数据结构的困难:查找困难。一个一个key去比较去查找,效率不高。因此有了Hash算法加快查找。 哈希表(Hash table,也叫散列表),是根据键值(Key)而直接...

    哈希表

              表: 存储数据 key –> value;

                                      

        用表来存储数据结构的困难: 查找困难。一个一个key去比较去查找,效率不高。因此有了Hash算法加快查找。

           哈希表(Hash table,也叫散列表),是根据键值(Key)而直接进行访问的数据结构。也就是说,它通过把键值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

          散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key),adr = f(key)。查找时,根据这个确定的对应关系找到给定值key的映射f(key),若查找集合中存在这个记录,则必定在f(key)的位置上。我们把这种对应关系f称为散列函数,又称为哈希函数(Hash).按这个思想,采用散列技术将记录存储在一块连续的存储空间中,这块连续的存储空间称为散列表或哈希表(Hash table)。关键字对应的记录存储位置称为散列地址。

         哈希表的做法其实很简单,就是把Key通过一 个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标 的数组空间里,而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。

    除留余数法

     最常用的构造散列函数的方法。对于散列表长为m的散列函数公式为:f(key) = key mod p(p≤m)这种方法不仅可以对关键字直接取模,也可在折叠、平方取中后再取模。**散列表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。

          举个例子,哈希函数是H(k)=k Mod m。m=12,k=100,H(100)=4。
          而如果m=2k,那么无论k是什么,H(K)的值都是一个0和奇数,也即是说只要奇数槽和0槽被占用,其他的偶数槽都是浪费掉了。如果m=2^r,那么H(k)的值就是k的低r位(化成二进制)。这样造成的后果是某一个槽有很多的关键字。所以来说一般的m取值尽量不要接近2的整数幂,而且还要是质数。

         虽然我们不希望发生冲突(同一个key有多个value),但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度,而且事先并不知道关键字的具体取值时。冲突就难免会发生。另外,当关键字的实际取值大于哈希表的长度时,而且表中已装满了记录,如果插入一个新记录,不仅发生冲突,而且还会发生溢出。因此,处理冲突和溢出是哈希技术中的两个重要问题。一般有开放地址法、链地址法。    

         链地址法:将所有关键字为同义词的记录存储在一个单链表中,这种链表叫做同义词子表,使用除留余数法,就不存在冲突的问题了,只是在链表中增加一个结点。

                                                              

    红黑树:

        Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn)(二叉树最大查找次数等于树的深度),效率非常之高。例如,Java集合中的TreeSetTreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。

    红黑树的特性:
    (1)每个节点或者是黑色,或者是红色。
    (2)根节点是黑色。
    (3)每个叶节点是黑色。 [注意:这里叶节点,是指为空(NIL或NULL)的叶子节点!]
    (4)如果一个节点是红色的,则它的子节点必须是黑色的,红色节点的孩子和父亲都不能是红色
    (5)任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

    注意:特性(3)中的叶子节点,是只为空(NIL或null)的节点。
               特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对接近平衡的二叉树,并不是一个完美平衡二叉查找树。红黑树示意图如下:

    预备知识

          当查找树的结构发生改变时,红黑树的条件可能被破坏。

    什么情况下会破坏红黑树的规则,什么情况下不会破坏规则呢?我们举两个简单的栗子:

    1.向原红黑树插入值为14的新节点:

                     

    2.向原红黑树插入值为21的新节点:

                       

        由于父节点22是红色节点,因此这种情况打破了红黑树的规则4(每个红色节点的两个子节点都是黑色),必须进行调整,使之重新符合红黑树的规则。

    旋转

          需要通过调整使得查找树重新满足红黑树的条件。调整可以分为两类:一类是颜色调整,即改变某个节点的颜色;另一类是结构调整,集改变检索树的结构关系。结构调整过程包含两个基本操作:左旋(Rotate Left),右旋(RotateRight)

    左旋:左旋的过程是将x的右子树绕x逆时针旋转,使得x的右子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

    右旋:右旋的过程是将x的左子树绕x顺时针旋转,使得x的左子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

    变色

         为了重新符合红黑树的规则,尝试把红色节点变为黑色,或者把黑色节点变为红色。下图所表示的是红黑树的一部分,需要注意节点25并非根节点。因为节点21和节点22连续出现了红色,不符合规则4,所以把节点22从红色变成黑色:

                       

    但这样并不算完,因为凭空多出的黑色节点打破了规则5,所以发生连锁反应,需要继续把节点25从黑色变成红色:

                   

    此时仍然没有结束,因为节点25和节点27又形成了两个连续的红色节点,需要继续把节点27从红色变成黑色:

                  


    我们以刚才插入节点21的情况为例:

                  

        将插入的节点着色为红色,不会违背"特性(5):从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点"!少违背一条特性,就意味着我们需要处理的情况越少。接下来,就要努力的让这棵树满足其它性质即可;满足了的话,它就又是一颗红黑树了。
           将插入节点着色为"红色"之后,不会违背"特性(5)"。那它到底会违背哪些特性呢?
           对于"特性:每个节点或者是黑色,或者是红色",显然不会违背了。因为我们已经将它涂成红色了。
           对于"特性:根节点是黑色",显然也不会违背,插入操作不会改变根节点。所以,根节点仍然是黑色。
           对于"特性:每个叶子节点(NIL)是黑色",这里的叶子节点是指的空叶子节点,插入非空节点并不会对它们造成影响。
           对于"特性:如果一个节点是红色的,则它的子节点必须是黑色的",是有可能违背的!

    from:https://www.cnblogs.com/skywang12345/p/3245399.html
    那接下来,想办法使之"满足特性(4)",就可以将树重新构造成红黑树了。首先,我们需要做的是变色,把节点25及其下方的节点变色:

    当前节点(25)的父节点是红色,叔叔节点15是黑色,且当前节点是其父节点的右孩子

    处理策略
    (01) 将“父节点”作为“新的当前节点”。
    (02) 以“新的当前节点”为支点进行左旋。

     我们把节点13看做X,把节点17看做Y,像刚才的示意图那样进行左旋转:

    由于根节点必须是黑色节点,所以需要变色,变色结果如下:

    这样就结束了吗?并没有。因为其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4,其他路径的黑色节点个数是3,不符合规则5。这时候我们需要把节点13看做X,节点8看做Y,像刚才的示意图那样进行右旋转:

                           

    最后根据规则来进行变色:

                             

    如此一来,我们的红黑树变得重新符合规则。这一个例子的调整过程比较复杂,经历了如下步骤:

    变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色

    关键要懂得红黑树自平衡调整的主体思想。

    from:https://www.sohu.com/a/201923614_466939

    Hash与红黑树的区别:

    权衡三个因素: 查找速度, 数据量, 内存使用,可扩展性,有序性。

         hash查找速度会比RB树快,而且查找速度基本和数据量大小无关,属于常数级别;而RB树的查找速度是log(n)级别。并不一定常数就比log(n) 小,因为hash还有hash函数的耗时。当元素达到一定数量级时,考虑hash。但若你对内存使用特别严格, 希望程序尽可能少消耗内存,那么hash可能会让你陷入尴尬,特别是当你的hash对象特别多时,你就更无法控制了,而且 hash的构造速度较慢。

    1. 红黑树是有序的,Hash是无序的,根据需求来选择。
    2. 红黑树占用的内存更小(仅需要为其存在的节点分配内存),而Hash事先应该分配足够的内存存储散列表,即使有些槽可能弃用
    3. 红黑树查找和删除的时间复杂度都是O(logn),Hash查找和删除的时间复杂度都是O(1)。
    展开全文
  • 一、AVL(平衡):带有平衡条件的查找(特殊的二叉查找) 1.要求:空或左右子树高度相差小于等于1,且左右子树均为平衡。 2.经过插入、删除(不考虑)操作会导致左右子树高度差大于1,即失去平衡。 3.可...
  • 二叉树 红黑树 B树 B+树的优缺点

    千次阅读 2021-04-09 09:47:58
    本文将从最普通的二叉查找开始,逐步说明各种解决的问题以及面临的新问题,从而说明MySQL为什么选择B+作为索引结构。 一、二叉查找(BST):不平衡 二叉查找(BST,Binary Search Tree),也叫二叉排序,...
  • 二叉树(binary tree)和哈希表(hash table)都是很基本的数据结构,但是我们要怎么从两者之间进行选择呢?他们的不同是什么?优缺点分别是什么? 回答这个问题不是一两句话可以说清楚的,原因是在不同的情况下,选择的...
  • 一、哈希表 也叫散列表,是根据关键码值而直接进行数据访问的数据结构。(把关键码值映射到表中一个位置来访问记录)映射函数叫做散列函数,存放记录的数组叫做散列表。 散列查找过程分为两步: (1)在存储时通过...
  • 哈希表红黑树

    2019-11-09 11:15:28
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • 哈希表 散列 取模计算,等值查询,范围查询不能用 缺点: 利用hash存储的话需要将所有数据文件添加到内存,比较高飞内存空间; 如果所有的查询都是等值查询,那么hash确实很快,但是实际工作中范围查找的数据更...
  • 主要内容:集合List接口及实现类ArrayListLinkedListSet接口及实现类HashSetLinkedHashSetEnumSetSortedSetTreeSet底层实现数组、链表、哈希表和红黑树方法的分类数组链表哈希表和红黑树 集合 定义:是一组类似于...
  • 链接: ...   线性表,插入的时间复杂度为O(1),但是因内部无法保证有序,...所以如果输入结合确定,所需要的就是查询,则可以考虑使用哈希表,如果输入集合不确定,则考虑使用平衡二叉树/红黑树,保证达到最大效率
  • Hash和红黑树是两种数据存储的方式。除了这两种存储方式,最常用的是线性结构存储,比如数组链表List等线性结构。 对于线性存储的数据,如果想检索一个数据,需要把所有数据都遍历一遍,然后找
  • 哈希表的介绍

    2021-06-15 16:46:58
    前言 该篇文章,主要带我们认识什么哈希表和树,为我们在研究各个数据结构的实现及扩展算法,有个基本的认识。
  • 红黑树与跳表

    2020-04-12 09:46:13
    先分析一波红黑树吧。。 根节点到任意一个叶子节点所经过的节点数量是相同的 每个节点或者是红色,或者是黑色(定义) 根节点一定是黑色的(对应2-3树的2节点3节点) 空节点是黑色的 如果一个节点是红色的,...
  • 红黑树 B树系列(B B+) 树的遍历 散列 一,AVL树(带有平衡条件的查找树) 平衡树 定义:左右子树高度不大于1 通过插入会导致不平衡 删除(不考虑) 单旋转:左旋右旋 双旋转:先局部,再整体 (先左后右...
  • 红黑树和链表对比(如果查找第1000个数据): 链表:需要查询1000次才能查找到 红黑树:每次都是两个两个找,查找的次数:log 2 1000 = 9次 (2 10 =1024) 也就是寻找的力度越大,查找的速度就会越快 二...
  • 哈希和红黑树的详细教程很多,本文就不重复了,但初学者往往云里雾里,不知道实战项目该用谁,今天笔者就从结合himqtt的源码,从物联网安全角度来对比一下哈希数据结构和红黑树的应用场景。 一、哈希和红黑树基本...
  • 二叉树、红黑树、B树、B+树、哈希索引、为什么Mysql选择B+树? ???? 哈希索引: 哈希索引的查询速度是非常快的 缺点 但为什么没有用它呢,因为哈希索引的哈希值是无序的,是无法进行排序操作的,也不能做范围查询...
  • 二叉查找(Binary Search Tree)很显然,二叉查找的发现完全是因为静态查找结构在动态插入,删除结点所表现出来的无能为力(需要付出极大的代价)。BST 的操作代价分析: (1) 查找代价: 任何一个数据的查找过程都...
  • 哈希函数和哈希表

    2021-09-06 21:35:28
    哈希表 主要作用:加快查找速度。可以近似看成O(1). 哈希函数特点: 1.其输入无限,输出有限。 2.每次相同的输入一定得到相同的输出。不同的输入也可能产生相同的输出。(哈希碰撞) 3.输出分布是绝对离散的,不会...
  • 一、简介为了解决线性探构造哈希表所出现的大量哈希冲突,我们采用了另外一种方法,便是开链法。而在SGI版本的STL中调用的也正是哈希桶的实现方法。注意:开链法实现哈希表的时候会出现很多很多的错误,比如各种模板...
  • 原文链接https://blog.csdn.net/yang_yulei/article/details/26066409我们会用三种经典的数据类型来实现高效的符号:二叉查找数、红黑树、散列表。二分查找我们使用有序数组存储键,经典的二分查找能够根据数组的...
  • 也就是拉链特别长的时候,有什么好办法能够解决的吗?主要是为了解决查询的效率问题,我想过把拉链变为一棵红黑树,除了这个办法以外还有什么好办法吗?
  • stl:即标准模板库,该库包含了诸多在计算机科学领域里所常用的基本数据结构基本算法 六大组件: 容器、迭代器、算法、仿函数、空间配置器、迭代适配器   迭代器:迭代器(iterator)是一种抽象的设计理念,通过...
  • 红黑树详解以及与BSTAVL树的比较

    千次阅读 2017-10-17 21:04:21
    1.stl中的set底层用的什么数据结构? 红黑树 2.红黑树的数据结构怎么定义? [cpp] view plain copy     enum Color  {   
  • B树、B+树、红黑树、二叉树、顺序表、哈希表详解 为什么MySQL要采用B+树来存储数据? 本文将详细分析各种存储结构的优缺点,以此来说明为什么MySQL采用B+树 众所周知 常见的存储结构有 顺序表 哈希表 搜索二叉树 ...
  • 21 | 哈希算法(上):如何防止数据库中的用户信息被脱库? 1.哈希算法要满足什么条件? (1)从哈希值不能反向推导出原始数据 (2)原始数据只修改了一个 Bit,最后得到的哈希值也不相同 (3)散列冲突的概率要很小 ...
  • 二叉树的递归定义为:二叉树是一棵空,或者是一棵由一个根节点两棵互不相交的,分别称作根的左子树右子组成的非空;左子树右子又同样都是二叉树 。 没有父节点的节点叫做根节点,图中F为根节点,C为A...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,853
精华内容 5,141
关键字:

红黑树和哈希表优缺点