logo资料库

18个高级数据结构整理归纳.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：1.79M 资料格式：pdf 举报 版权申诉
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
资料共19页，剩余部分请下载后查看
    Data  Structure Data  Structure ⼀一.数据结构的基本问题 数据在计算机系统中的表⽰示和组织，但是有约束 内存结构：⼆二叉树-平衡-近似平衡-不平衡 优化 时间 外存结构：B+树、R树、希尔伯特树 优化 I/O次数 云存储结构：分布式散列表（巨⼤大规模） Compact（紧缩）存储：哈夫曼编码、FP树（前缀、trie树）、 Lossy-Counting（有损计数） 区间树、k-d 树、红⿊黑树、红⿊黑树的拓展（应⽤用） 数据压缩 算法：搜索、排序、匹配（matching） ⼆二.基本思想基本⽅方法 A)空间换时间 跳表 树节点增加更多指针 B)困难： (1)访问的次线性 O(logn) 线性的困难在于扫描整个数据集 (2)数据 a)规模 访问的规模 巨⼤大规模 b)动态性 c)复杂性（链值、结构化数据、⾮非结构化数据） d)安全性 (3)外存的访问模式（如何减⼩小 I/O 次数） (4)存储体系/平台/介质 a)内存：树（平衡树 近似平衡树 不平衡树） 访问 O(logn) b)外存：B+树（⼀一维）、R 树（⼀一维到⼆二维）、Hilbert树（⼆二维到⼀一维） c)分布式：CAN 散列表、CHORD 链表、BATON B+树 C)具体⽅方法：希尔排序（初等数论、数逆序）、数学期望（和的期望等于期望的 和）、分形 有哪些数据结构 应⽤用场景 解决什么问题 是怎么做的 背后原理 为什么这么做 如 何改进 相互关系 哪些情况会让问题变得困难 如何解决 对数据结构的整理分类⾃自⼰己的理解 关键技术的基本思想 简短清晰表达 重点突出 总分结构 表达能⼒力是评价的因素
    例题： 1.写出BST/红⿊黑树/B+/Spaly树之间的区别和应⽤用场景 2.⼀一致哈希表在分布式⺴⽹网络中的应⽤用和性能优化 分布式哈希(DHT) 两个关键点：每个节点只维护⼀一部分路由；每个节点只存储⼀一部分数据。从⽽而实现整个⺴⽹网络 中的寻址和存储。 ⼀一致性哈希： DHT的⼀一种实现。本质还是⼀一个哈希算法。 四个概念和原则： a)balance：哈希结果尽可能的平均分散到各个节点上，使得每个节点都能得到充分利⽤用。 b)Monotonicity：上⾯面也说了，如果是⽤用签名取模算法，节点变更会使得整个⺴⽹网络的映射关 系更改。如果是carp，会使得1/n的映射关系更改。⼀一致性哈希的⺫⽬目标，是节点变更，不会 改变⺴⽹网络的映射关系。 c)spread：同⼀一份数据，存储到不同的节点上，换⾔言之就是系统冗余。⼀一致性哈希致⼒力于降 低系统冗度。 d)load：负载分散，和balance其实是差不多的意思，不过这⾥里更多是指数据存储的均 衡，balance是指访的均衡。 ⼀一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的⺴⽹网络拓扑中分布存储 和路由。每个节点仅需维护少量相邻节点的信息，并且在节点加⼊入/退出系统时，仅有相关 的少量节点参与到拓扑的维护中。所有这⼀一切使得⼀一致性哈希成为第⼀一个实⽤用的DHT算法。 (O(N)表⽰示与N成正⽐比关系，N代表系统内的节点总数)才能到达被查询的节点。不难想象，当 系统规模⾮非常⼤大时，节点数量可能超过百万，这样的查询效率显然难以满⾜足使⽤用的需要。换 个⾓角度来看，即使⽤用户能够忍受漫⻓长的时延，查询过程中产⽣生的⼤大量消息也会给⺴⽹网络带来不 必要的负荷。 但是⼀一致性哈希的路由算法尚有不⾜足之处。在查询过程中，查询消息要经过O(N)步 3.内存/外存对于数据结构选择的影响？ 内存指的就是主板上的存储部件，CPU直接与之沟通，并⽤用其存储数据的部件，存放当前正 在使⽤用的（即执⾏行中的）数据和程序，它的物理实质就是⼀一组或多组具备数据输⼊入输出和数 据存储功能的集成电路，内存只⽤用于暂时存放程序和数据，⼀一旦关闭电源或发⽣生断电，其中 的程序和数据就会丢失。外存包括软盘、硬盘和光盘，存放在其中的数据靠磁来维持，因此 可永久保存数据。 特点：内存处理速度快、存储容量⼩小、断电后信息丢失；外存处理速度慢、存储容量⼤大、信 息永久保存 4.R树在地图/打⻋车软件中的应⽤用和性能分析
    数据结构 本质：Data Structure == ( Data Set, Pointer ) == (存储结构，指针) 定义：A particular way to organize data in the operation system to access data efficiently. 内容：(1)数据的各种逻辑结构和物理结构，以及他们之间的相应关系 (2)并对每种结构定义相适应的各种运算 (3)设计出相应的算法 分析算法的效率 逻辑结构：线性（栈、队列） ⾮非线性（树、图） 数据的存储结构：线性连续的存储单元 数据操作的集合：查询、更新和聚集 什么是好的数据结构：(1) O(logn)时空复杂度 (2)合理的内存开销 (3)正确性 (4)易编程、易读 ⾼高级数据结构 对于数据密集型（⼤大数据）的应⽤用，能够设计出⼀一种数据结构，让我们的算法有 很好的响应性 算法 定义：解题⽅方案的准确⽽而完整的描述，是⼀一系列解决问题的清晰指令，对⼀一系列 规范的输⼊入，在有序的时间内获得所要求的输出；有基本运算及规定的运算顺序 所构成的完整的解题步骤。按照要求设计好的有限的确切的计算序列，并且这样 的步骤和序列可以解决⼀一类问题。 内容：排序、分治法（divide and conquer）、随机算法、数据结构的算法、动 态规划、贪⼼心算法、图算法、数论算法 三.具体数据结构及关系 Skiplist 跳表 1.为什么选择跳表？ 跳表是⼀一种随机化的数据结构，它的效率和红⿊黑树以及 AVL 树不相上下，跳表的原理相当 简单，只要能熟练操作链表，就能轻松实现⼀一个 SkipList。
    有序数组，如果数据量不断变化，有序数组很难能够⾼高效的进⾏行写⼊入。 链表是⼀一种最容易处理数据不断增加结构的有序数据结构，并且链表对于并发的⽀支持度是⾮非 常好的，然⽽而链表却不能够进⾏行⼆二分查找，因为⽆无法取到任意⼦子集的中值。 树，如平衡有序⼆二叉树。不过，⽆无论是AVL还是红⿊黑树，这个预先找到中值并写⼊入到⽗父节点 的操作的都是⾮非常复杂的，对于复杂的操作来说，想使⽤用常⻅见的⽆无锁操作就⼏几乎不可能了。 所以，跳表是⼀一种满⾜足这样条件的很好的数据结构。 2.定义： 是⼀一种随机化数据结构，基于并联的链表，其效率可⽐比拟于⼆二叉查找树（对于⼤大多数操作需 要O(log n)平均时间） 跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的⽅方式进⾏行的，所以在列 表中的查找可以快速的跳过部分列表。所有操作都以对数随机化的时间进⾏行O(logn)。 3.描述： 跳跃列表是按层建造的。底层是⼀一个普通的有序链表。每个更⾼高层都充当下⾯面列表的“快速 跑道”，这⾥里在层 i 中的元素按某个固定的概率 p (通常为0.5或0.25)出现在层 i+1 中。平均起 来，每个元素都在 1/(1-p) 个列表中出现，⽽而最⾼高层的元素（通常是在跳跃列表前端的⼀一个 特殊的头元素）在 O(log1/p n) 个列表中出现。 每个节点包含2个指针。⼀一个指向同⼀一层中下⼀一元素，另⼀一个指向下⼀一层元素。 要查找⼀一个⺫⽬目标元素，起步于头元素和顶层列表，并沿着每个链表搜索，直到到达⼩小于或着 等于⺫⽬目标的最后⼀一个元素。通过跟踪起⾃自⺫⽬目标直到到达在更⾼高列表中出现的元素的反向查找 路径，在每个链表中预期的步数显⽽而易⻅见是 1/p。所以查找的总体代价是 O((log1/p n) / p)， 当p 是常数时是 O(log n)。通过选择不同 p 值，就可以在查找代价和存储代价之间作出权 衡。 插⼊入时被插⼊入元素的层数也是随机化得到。 跳跃列表不像某些传统平衡树数据结构那样提供绝对的最坏情况性能保证，因为⽤用来建造跳 跃列表的扔硬币⽅方法(随机的)总有可能（尽管概率很⼩小）⽣生成⼀一个糟糕的不平衡结构。但是 在实际中它⼯工作的很好，随机化平衡⽅方案⽐比在平衡⼆二叉查找树中⽤用的确定性平衡⽅方案容易实 现。跳跃列表在并⾏行计算中也很有⽤用，这⾥里的插⼊入可以在跳跃列表不同的部分并⾏行的进⾏行， ⽽而不⽤用全局的数据结构重新平衡。 4.核⼼心思想：空间换取时间，在每个节点中增加向前的指针，提⾼高查找的效率 5.优点： 2*log2n a)⽀支持范围查找 因为是有序结构，所以能够很好的⽀支持范围查找。截取中间⼦子集只需两次定位。耗时 b)能够随着数据的增⻓长⽽而⾃自动扩展。核⼼心数据结构是链表，可以很好的⽀支持数据的不断增⻓长 c)读写性好 因为从宏观上可以做到⼀一次排除⼀一半的数据，并且在写⼊入时也没有进⾏行其他额外的数据查找
    性 ⼯工作，所以对于skiplist来说，其读写的时间复杂度都是O(log2n) d)并⾏行度⾼高 只要不是在同⼀一个⺫⽬目标插⼊入点插⼊入数据，所有插⼊入都可以并⾏行进⾏行，⽽而就算在同⼀一个插⼊入 点，插⼊入本⾝身也可以使⽤用⽆无锁⾃自旋来提升写⼊入效率。 因此skiplist是个并⾏行度⾮非常⾼高的数据结构。 e)内存占⽤用：因为每个结点期望是2层，所以储存占⽤用空间⼤大概为2N，与平衡⼆二叉树的内存 消耗基本⼀一致。 6.改进 a)若不采⽤用随机产⽣生层数⽅方法还可采⽤用⼆二分的⽅方法建⽴立初始SkipList，估计复杂度仍然 是O(log n)，系数会更⼩小。 b)进⾏行随机数的运算本⾝身也是个很消耗cpu的操作，所以，如果在插⼊入的时候就能直接算出 这个数据应该往⾼高层推的总次数，那么就不需要算那么多次随机数了，每次写⼊入只需要算⼀一 次就⾏行了。 c)实现⼀一个⾼高性能的随机数算法。 树的分类： (1)BST：⼆二叉查找/搜索/排序树 (2)AVL 树：平衡⼆二叉查找树 (3)红⿊黑树：基本平衡⼆二叉查查找树 (4)Splay 树：伸展树/分裂树 (5)B 树：多路平衡查查找树 (6)B+树 (7)R 树 最基本：BST ⼆二叉搜索树 不平衡 定义：⼆二叉排序树或者是⼀一棵空树，或者是具有下列性质的⼆二叉树： （1）若左⼦子树不空，则左⼦子树上所有结点的值均⼩小于它的根结点的值； （2）若右⼦子树不空，则右⼦子树上所有结点的值均⼤大于或等于它的根结点的值； （3）左、右⼦子树也分别为⼆二叉排序树； （4）没有键值相等的节点。 操作：查询（时间复杂度 O(logn)）、插⼊入、删除 应⽤用：⽀支持多种动态集合操作、表⽰示有序集合、建⽴立索引或优先队列 缺点：作⽤用于⼆二叉查找树上的基本操作的时间是与树的⾼高度成正⽐比的。对⼀一个含n各节点的 完全⼆二叉树，这些操作的最坏情况运⾏行时间为O(log n)。但如果树是含n个节点的线性链，则 这些操作的最坏情况运⾏行时间为O(n)。⽽而有些⼆二叉查找树的变形，其基本操作在最坏情况下 性能依然很好，⽐比如红⿊黑树、AVL树等等。
    BST 的改进：Splay Tree 拓展树 不平衡 1.什么是 Splay Tree? 核⼼心思想：通过 Splay操作进⾏行⾃自我调整，获得平摊较低的时间复杂度 ⼀一种⼆二叉查找树，它能在O(log n)内完成插⼊入、查找和删除操作。 在伸展树上的⼀一般操作都基于伸展操作：假设想要对⼀一个⼆二叉查找树执⾏行⼀一系列的查找操 作，为了使整个查找时间更⼩小，被查频率⾼高的那些条⺫⽬目就应当经常处于靠近树根的位置。于 是想到设计⼀一个简单⽅方法， 在每次查找之后对树进⾏行重构，把被查找的条⺫⽬目搬移到离树根 近⼀一些的地⽅方。伸展树应运⽽而⽣生。伸展树是⼀一种⾃自调整形式的⼆二叉查找树，它会沿着从某个 节点到树根之间的路径，通过⼀一系列的旋转把这个节点搬移到树根去。 它的优势在于不需要记录⽤用于平衡树的冗余信息。 2.与 BST 的关系 是对⼆二叉查找树的⼀一种改进，虽然它并不能保证树⼀一直是“平衡”的，但对于伸展树的⼀一系列 操作，我们可以证明其每⼀一步操作的平摊复杂度都是O(log n)。所以从某种意义上说，伸展 树也是⼀一种平衡的⼆二叉查找树。⽽而在各种树状数据结构中，伸展树的空间要求与编程复杂度 也都是很优秀的。和 BST ⼀一样，是有序的（左⼩小右⼤大）。 3.优点： 可靠的性能——它的平均效率不输于其他平衡树 存储所需的内存少——伸展树⽆无需记录额外的什么值来维护树的信息，相对于其他平衡树， 内存占⽤用要⼩小。 ⽀支持可持久化——可以将其改造成可持久化伸展树。可持久化数据结构允许查询修改之前数 据结构的信息，对于⼀一般的数据结构，每次操作都有可能移除⼀一些信息，⽽而可持久化的数据 结构允许在任何时间查询到之前某个版本的信息。可持久化这⼀一特性在函数式编程当中⾮非常 有⽤用。另外，可持久化伸展树每次⼀一般操作的均摊复杂度是O(log n) 4.缺点： 伸展树最显著的缺点是它有可能会变成⼀一条链。这种情况可能发⽣生在以⾮非降顺序访问n个元 素之后。然⽽而均摊的最坏情况是对数级的——O(log n)
    BST 的改进：RB Tree 红⿊黑树 近似平衡 1.什么是红⿊黑树？ 红⿊黑树是⼀一种⾃自平衡⼆二叉查找树，典型的⽤用途是实现关联数组。它是复杂的，但它的操 作有着良好的最坏情况运⾏行时间，并且在实践中是⾼高效的: 它可以在O(log n)时间内做查找， 插⼊入和删除，这⾥里的n是树中元素的数⺫⽬目。 如何保持平衡？通过对任何⼀一条从根到叶⼦子的简单路径上的各个结点的性质进⾏行约束，确保 没有⼀一条路径会⽐比其他路径⻓长出两倍，因⽽而近似于平衡。红⿊黑树不追求完全平衡，降低了对 选择的要求，从⽽而提⾼高了性能。 结点属性：树中每个结点包含5个属性：color, key, left, right 和 p 。视叶结点（外部结点） 属性值为NIL，⽽而把带关键字的结点视为树的内部结点。 ⿊黑⾼高（black height）：从这棵红⿊黑树的根结点（但不包括这个根结点）到叶结点的任意⼀一 条简单路径上包含的⿊黑⾊色结点个数（注意，包括叶结点），记为bh(x)。另外规定叶结点的⿊黑 ⾼高度为0。 树的旋转：当我们在对红⿊黑树进⾏行插⼊入和删除等操作时，对树做了修改，那么可能会违背红 ⿊黑树的性质。为了保持红⿊黑树的性质，我们可以通过对树进⾏行旋转，即修改树种某些结点的 颜⾊色及指针结构，以达到对红⿊黑树进⾏行插⼊入、删除结点等操作时，红⿊黑树依然能保持它特有 的性质。 2.⽤用途和好处 红⿊黑树和AVL树⼀一样都对插⼊入时间、删除时间和查找时间提供了最好可能的最坏情况担 保。这不只是使它们在时间敏感的应⽤用如实时应⽤用（real time application）中有价值，⽽而且 使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算⼏几何中 使⽤用的很多数据结构都可以基于红⿊黑树。红⿊黑树和 AVL 树时间复杂度相同，但红⿊黑树统计 性能更好。 红⿊黑树在函数式编程中也特别有⽤用，在这⾥里它们是最常⽤用的持久数据结构（persistent data structure）之⼀一，它们⽤用来构造关联数组和集合，每次插⼊入、删除之后它们能保持为 以前的版本。除了O(log n)的时间之外，红⿊黑树的持久版本对每次插⼊入或删除需要O(log n)的 空间。 3.性质：
    红⿊黑树是每个节点都带有颜⾊色属性的⼆二叉查找树，颜⾊色为红⾊色或⿊黑⾊色。 性质1. 节点是红⾊色或⿊黑⾊色。 性质2. 根是⿊黑⾊色。 性质3. 所有叶⼦子都是⿊黑⾊色（叶⼦子是NIL节点）。 性质4. 每个红⾊色节点必须有两个⿊黑⾊色的⼦子节点。(从每个叶⼦子到根的所有路径上不能有两个 连续的红⾊色节点。) 性质5. 从任⼀一节点到其每个叶⼦子的所有简单路径都包含相同数⺫⽬目的⿊黑⾊色节点。 B Tree / B+ Tree 平衡多叉树 1.为什么需要 B 树？ 动态查找树主要有：⼆二叉查找树，平衡⼆二叉查找树，红⿊黑树，B-tree/B+-tree。前三者是典 型的⼆二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度⾃自 然会提⾼高查找效率。 但是咱们⾯面对这样⼀一个实际问题：就是⼤大规模数据存储中，实现索引查询这样⼀一个实际背景 下，树节点存储的元素数量是有限的（如果元素数量⾮非常多的话，查找就退化成节点内部的 线性查找了），这样导致⼆二叉查找树结构由于树的深度过⼤大⽽而造成磁盘I/O读写过于频繁， 进⽽而导致查询效率低下（为什么会出现这种情况，待会在外部存储器-磁盘中有所解释）， 那么如何减少树的深度（当然是不能减少查询的数据量），⼀一个基本的想法就是：采⽤用多叉 树结构（由于树节点元素数量是有限的，⾃自然该节点的⼦子树数量也就是有限的）。 这样我们就提出了⼀一个新的查找树结构——多路查找树。根据平衡⼆二叉树的启发，⾃自然就想 到平衡多路查找树结构，也就是这篇⽂文章所要阐述的第⼀一个主题B~tree，B树的各种操作能 使B树保持较低的⾼高度，从⽽而达到有效避免磁盘过于频繁的查找存取操作，从⽽而有效提⾼高查 找效率。 磁盘读取数据是以盘块(block)为基本单位的。位于同⼀一盘块中的所有数据都能被⼀一次性全部 读取出来。⽽而磁盘IO代价主要花费在查找时间Ts上。因此我们应该尽量将相关信息存放在同 ⼀一盘块，同⼀一磁道中。或者⾄至少放在同⼀一柱⾯面或相邻柱⾯面上，以求在读/写信息时尽量减少 磁头来回移动的次数，避免过多的查找时间Ts。 所以，在⼤大规模数据存储⽅方⾯面，⼤大量数据存储在外存磁盘中，⽽而在外存磁盘中读取/写⼊入块 (block)中某数据时，⾸首先需要定位到磁盘中的某块，如何有效地查找磁盘中的数据，需要⼀一 种合理⾼高效的外存数据结构，即B-tree结构，以及相关的变种结构：B+-tree结构。 2.B 树与红⿊黑树的关系 B树与红⿊黑树最⼤大的不同在于，B树的结点可以有许多⼦子⼥女，从⼏几个到⼏几千个。那为什么⼜又 说B树与红⿊黑树很相似呢?因为与红⿊黑树⼀一样，⼀一棵含n个结点的B树的⾼高度也为O（lgn）， 但可能⽐比⼀一棵红⿊黑树的⾼高度⼩小许多，应为它的分⽀支因⼦子⽐比较⼤大。所以，B树可以在 O（logn）时间内，实现各种如插⼊入（insert），删除（delete）等动态集合操作。 3.B 树与 B+树的关系 ⼆二叉树提供了良好的性能，但是当数据有序插⼊入时会失去平衡，2-3-4树和2-3树是⼀一种平衡 树,是多路的，⽽而红-⿊黑树是⼀一种⼆二叉平衡树，通过严格的红⿊黑规则保持平衡。B树是⼀一种平
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料