专注Java教育14年 全国咨询/投诉热线:444-1124-454
星辉LOGO图
始于2009,口口相传的Java黄埔军校
首页 hot资讯 简述3种高级数据结构

简述3种高级数据结构

更新时间:2020-12-29 17:47:17 来源:星辉 浏览1190次

数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。基本的数据结构我们都接触过,总体而言还是比较简单的,本文我们就来聊一聊相对而言比较难的高级数据结构

 

下面为大家介绍3种高级数据结构分别为:跳跃表,红黑树和B树,接下来详细看一下这3种数据结构。

 

1.跳跃表

跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表。是一种随机化数据结构,基于并联的链表,其效率可比拟于红黑树和AVL树(对于大多数操作需要O(logn)平均时间),但是实现起来更容易且对并发算法友好。redis 的 sorted SET 就是用了跳跃表。

 

2.红黑树

我们对平衡二叉树的定义往往是模棱两可的,在这里大概说一下,左右子树高度差用 HB(k) 来表示,当 k=0 为完全平衡二叉树,当 k<=1 为AVL树,当k>=1 但是接近平衡的是红黑树,其它平衡的还有如Treap、替罪羊树等,总之就是高度能保持在O(logn)级别的二叉树。红黑树是一种自平衡二叉查找树,也被称为"对称二叉B树",保证树的高度在[logN,logN+1](理论上,极端的情况下可以出现RBTree的高度达到2*logN,但实际上很难遇到)。它是复杂的,但它的操作有着良好的最坏运行时间:它可以在O(logn)时间内做查找,插入和删除。

 

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,有如下额外要求:

1)节点是红色或黑色。

2)根是黑色。

3)所有叶子都是黑色(叶子是NIL节点,亦即空节点)。

4)每个红色节点的子节点必须是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5)从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

 

3.B树

B树有一种说法是二叉查找树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点。但是实际上这样翻译是一种错误,B树就是 B-tree 亦即B-树。

 

B-树(B-tree)是一种自平衡的树,能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作,都在对数时间内完成。B-树,概括来说是一个一般化的二叉查找树,可以拥有多于2个子节点(多路查找树)。与自平衡二叉查找树不同,B-树为系统大块数据的读写操作做了优化。B-树减少定位记录时所经历的中间过程,从而加快存取速度。B-树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上,比如MySQL索引就用了B+树。

 

其实,这些所谓的高级数据结构往往是一些简单的数据结构衍生出来的,我们想要学习高级的数据结构,就必须打好基本的数据结构的基础,在本站的数据结构和算法教程中有对各种基本数据结构的详细讲解,我们可以以此为根基,深入钻研数据结构这门学科。


提交申请后,顾问老师会电话与您沟通安排学习

免费课程推荐 >>
技术文档推荐 >>