1， Splay Tree

Splay Tree 定义：在一颗BBST中，某节点被访问，则随后将其移送至根节点。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
  • 数据局部性

逐层伸展 vs.双层伸展

  • 精髓在于双层伸展（可减弱最坏情况的影响）

算法实现：

  • 《数据结构》学习笔记 第8章 高级搜索树 (Splay，RB，B-Tree） 随笔 第1张

  • 重点包含了Splay，search，insert，remove四种操作。 

  • Splay算法
    • 四种情况，使用3+4统一算法；
  • Search算法：不再属于静态操作，调用了Splay算法。
    • 返回命中节点，或者（未命中）邻近节点。
  • Insert算法
    • 《数据结构》学习笔记 第8章 高级搜索树 (Splay，RB，B-Tree） 随笔 第2张

  • Remove算法

    • 《数据结构》学习笔记 第8章 高级搜索树 (Splay，RB，B-Tree） 随笔 第3张

  • 综合评价：

    • 《数据结构》学习笔记 第8章 高级搜索树 (Splay，RB，B-Tree） 随笔 第4张

    • 典型应用：电脑操作系统。 

2，B-Tree

  •  多路查找树，功能上等效于BST；目的：弥补不同存储级别之间巨大的访问速度差异；
  • 存储器容量与访问速度的矛盾；解决方法；分级存储。
    • 《数据结构》学习笔记 第8章 高级搜索树 (Splay，RB，B-Tree） 随笔 第5张

    • 《数据结构》学习笔记 第8章 高级搜索树 (Splay，RB，B-Tree） 随笔 第6张

  • B树设计思路及定义： 

    • 《数据结构》学习笔记 第8章 高级搜索树 (Splay，RB，B-Tree） 随笔 第7张

    • 《数据结构》学习笔记 第8章 高级搜索树 (Splay，RB，B-Tree） 随笔 第8张

    • 定义需注意：外部节点与叶节点区别，深度统一，阶次含义，及其紧凑表示。 

      • （2,4）B树与红黑树渊源很深。

  • B树的实现：

    • BTNode及BTree

      • 《数据结构》学习笔记 第8章 高级搜索树 (Splay，RB，B-Tree） 随笔 第9张

      • 《数据结构》学习笔记 第8章 高级搜索树 (Splay，RB，B-Tree） 随笔 第10张

    • 查找算法

      • 《数据结构》学习笔记 第8章 高级搜索树 (Splay，RB，B-Tree） 随笔 第11张 
      • 性能分析（复杂度）：取决于两方面
        • 1）节点载入内存，和 2）节点内的查找。
          • 鉴于内存，外存速度的巨大差异，后者可忽略。前者次数直接取决于树高。
        • 为了与I/O操作的延迟相匹配，每个节点大小设计为与I/O兑换的页面的大小相匹配。
          • 大小通常为KB，几百个。
        • 树高：最大：log[m]N，若m=256，则为BST高度的1/7. 最小：logmN，若m=256，则为BST高度的1/8.
    • 插入算法

    • 删除算法

3， Red-Black Tree

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄