数据结构常见问题系列(二) 柔情只为你懂 2022-11-22 10:22 119阅读 0赞 ### 文章目录 ### * * 1. 常用数据结构 * 2. 什么是链表、队列、栈 * 3. 什么是树(平衡二叉树、二叉排序树、B树、B+树、R树、红黑树) ## 1. 常用数据结构 ## 1). 数组:顺序存储,随机访问。 链表:链表存储,顺序访问。 2). 栈:分为栈顶和栈底,遵循先进后出的原则。 3). 队列: 先进先出原则(类比成排队一样)。 4). 树:二叉树、平衡二叉树、大、小顶堆等。 5). 图:最短路径,关键路径。 -------------------- ## 2. 什么是链表、队列、栈 ## **链表:** 当需要存储多个相同数据类型的时候,可以使用数组存储,数组可以通过下标直接访问,但数组有个缺点就是无法动态的插入或删除其中的元素(特别是操作第一个位置上的元素),而链表弥补了这个缺陷,对于元素的插入和删除操作是很方便的,不过访问元素的“性能”就差很多了。 所谓单链表,即只有一个指针,指向下一个元素(结点)的地址,只要知道单链表的首地址,就可以遍历整个链表了。由于链表结点是在堆区动态申请的,其地址并不是连续的,因此无法进行随机访问,只有通过前一结点的next指针才能定位到下一个结点的指针。 单链表只能向后遍历,不能逆序遍历,所以有了使用更广泛的双链表。即结点多了一个存储前一个结点地址的prev指针。双链表可以双向遍历,但也只能按顺序访问。 **队列:** 队列就像我们平时排队一样,按照数据到达的顺序进行排队,每次新插入的一个结点排在队尾,删除一个结点只能从头才能出队。简言之,对元素的到达顺序,按照“先进先出”的原则。由于队列频繁的插入和删除,一般为了高效,使用固定长度的数组实现,并且可循环使用数组空间,在操作之前要判断处理的队列是否已满或为空。如果要动态长度,可以用链表实现,只要同时记住链表的首地址(队头front)和尾地址(队尾rear)。 **栈:** 栈的特点正好与队列相反,按照数据进栈的逆序出栈,即“先进后出”,每次入栈将元素放在栈顶,出栈时也只能从栈顶出栈,与队列类似,一般用定长数组存储栈元素,而不是动态的申请结点空间。进栈一般被叫做压栈,出栈被叫做弹栈。 由于压栈弹栈都在栈顶,所以只需要一个size字段存储当前栈的大小,初始化size为0,每次压栈时,size+1,注意栈是否已满,弹栈则size-1。 -------------------- ## 3. 什么是树(平衡二叉树、二叉排序树、B树、B+树、R树、红黑树) ## 为什么会有树这个概念呢?因为已有的数据结构(数组、链表)不能很好的平衡静态操作和动态操作的时间开销。 <table> <thead> <tr> <th>时间复杂度</th> <th>数组</th> <th>链表</th> </tr> </thead> <tbody> <tr> <td>静态操作(查找)</td> <td>O(1)</td> <td>O(n)</td> </tr> <tr> <td>动态操作(插入、删除)</td> <td>O(n)</td> <td>O(1)</td> </tr> </tbody> </table> 对于树这种数据结构而言,最显著的特点就是有且只能有一个根节点(空树除外),每个节点可以有多个子结点,除了根结点,其他结点只能有一个父结点。树的种类繁多,一般谈论的最多的是二叉树,每个结点有不超过两个的子结点。 **平衡二叉树&二叉排序树** 二叉排序树(Binary Search Tree,BST,也叫二叉搜索树),构造一棵二叉排序树也很简单,大于根节点的放在根节点的右子树上,小于根结点的放在根结点的左子树上(等于根结点的视情况而定)。如果写程序的话,可以采用递归的方式,而且由于不存在重叠子问题的情况,因此递归的性能已经足够好(不考虑栈溢出的情况)。 二叉排序树在通常情况下可以达到O(lgn)的静态、动态操作的时间复杂度,但是存在一种特殊情况,若输入的本来就是有序的,这时二叉树就退化成了链表。为了消除二叉树对于输入的敏感特性,引入了平衡二叉树(AVL),事实上平衡二叉树应该叫平衡二叉排序树也合理。平衡二叉树只要保证每个节点左子树和右子树的高度差小于等于1就可以了。 **B树 & B+树** 操作系统中,寄存器的访问速度和容量是此消彼涨的,速度最快的当属CPU上的寄存器,然后就是cache(高速缓存),然后是内存,再就是外部磁盘等,当两个处在不同层级的存储器(比如内存和外部磁盘)交换数据时,我们称之为I/O。而I/O相当耗时,要尽量避免使用。 B树(B-Tree,“B-树”这种翻译我不是很认同)的出现就是为了解决这个问题。B树由于是多路二叉树(根结点有两个子结点,其他结点子结点不止两个),它的高度要远低于平衡二叉树,一般来讲,二叉平衡树每下降一层就执行一次磁盘I/O操作,以1GB数据为例,平均需要30次磁盘I/O才能读取到数据,而B树每下降一层,每个结点都会读入多个关键码,因此B树适用于实现磁盘的读写逻辑。 B 树是为了磁盘或其它存储设备而设计的一种多叉(相对于二叉树,B树每个内结点有多个分支,即多叉平衡排序树。与下面要介绍的红黑树很相似,但在降低磁盘I/O操作方面要更好一些。许多数据库系统都一般使用B树或者B树的变形结构(如B+树)来存储信息。 **R树** 处理空间存储问题,R树在数据库等领域做出的功绩是非常显著的。它很好的解决了在高维空间搜索等问题。举个R树在现实领域中能够解决的例子:查找20英里以内所有的餐厅。如果没有R树你会怎么解决?一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中,一个字段记录经度,另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息,然后计算是否满足要求。如果一个地区有100家餐厅的话,我们就要进行100次位置计算操作了,如果应用到谷歌地图这种超大数据库中,这种方法便必定不可行了。 R树就很好的解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间,采用了B树分割空间的思想,并在添加、删除操作时采用合并、分解结点的方法,保证树的平衡性。因此,R树就是一棵用来存储高维数据的平衡树。 每个R树的叶子结点包含了多个指向不同数据的指针,这些数据可以是存放在硬盘中的,也可以是存在内存中。根据R树的这种数据结构,当我们需要进行一个高维空间查询时,我们只需要遍历少数几个叶子结点所包含的指针,查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案,效率显著提高。 **红黑树** R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center] 红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。例如,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,需要使用动态规则的防火墙系统,使用红黑树而不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm\_area\_struct(虚拟内存)时就是采用了红黑树来维护内存块的。 对于链表、数组、树和图来说,它们每次的动态操作都会完全遗忘之前的状态,转而到达全新的状态,这种数据结构称为ephemeral structure。另一种数据结构可以记录某一历史时刻的状态,在访问时可以根据版本好+目标数据进行访问,这种数据结构称为persistent structure。事实上,红黑树可以实现这种对历史版本的记录。 B树与红黑树最大的不同在于,B树的结点可以有许多子女,从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样,一棵含n个结点的B树的高度也为O(lgn),但可能比一棵红黑树的高度小许多,因为它的分支因子比较大。所以,B树可以在O(logn)时间内,实现各种如插入(insert),删除(delete)等动态集合操作。 -------------------- **什么是堆(大根堆、小根堆)** 这里说的“堆”是一种数据结构,注意与jvm中的堆内存分开。堆必须满足以下两个条件:(1)是完全二叉树 (2)heap中存储的值是偏序(偏序只对部分元素成立关系R,全序对集合中任意两个元素都有关系R)。 大根堆:父结点的值大于等于其子结点的值;小根堆:父结点的值小于等于其子节点的值。 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/eb5fabc4328e480ead9df4b14135b15c.png
还没有评论,来说两句吧...