红黑树

缘起

为了解决【3】中数据倾斜的问题，我们引入了足够精妙的AVL（【1】），但是AVL保持的是绝对平衡. 尽管它可以保证单次查询的速度最坏依旧在O(logn)，但是删除操作之后的重平衡可能需做多 达(logn)次旋转， 从而频繁地导致全树整体拓扑结构的大幅度变化。 于是人们引入了Splay(【2】). Splay 实现简便、无需修改节点 结构(AVL需要修改节点的bf因子)、分摊复杂度低，但可惜最坏情况下的单次操作需要O(n)时间，故难以适用于核电站、医 院等对可靠性和稳定性要求极高的场合。 有没有一种数据结构介于splay和AVL中间呢? 红黑树就此诞生了.红黑树可保证： 在每次插入或删除操作之后的重平衡过程中， 全树拓扑结构的更新仅涉及常数个节点。尽管最坏 情况下需对多达O(logn)个节点重染色，但就分摊意义而言仅为O(1)个 (所谓分摊意义就是指这种最坏情形不会每次都出现，而是多次操作之后才会出现一次，那么每次操作分摊到的时间就是O(1)). 红黑树在AVL树“绝对平衡”的基础上，进一步放宽条件。实际上，红黑树 所采用的“适度平衡”标准，可大致表述为： 任一节点左、右子树的高度，相差不得超过两倍（可以理解为下面红黑树的第四条定义）。

Read More

B/B+树

缘起

为了解决BST数据倾斜的问题，我们引入了AVL等平衡二叉树的结构. 但是对于海量数据的今天, 内存算法近乎不可能, 所以很多时候对数据进行检索的时候其实下一次要读取的数据其实尚在磁盘中. 而我们知道数据在磁盘中是以块（block）为单位存放的, 并且数据的读取要经历

柱面–>磁道–>块–>系统总线传输

上面的过程（参见【1】）. 其中前三个属于磁头定位要读取数据的过程，最为耗时（甚至可长达0.1s之久）. 所以对于海量数据的检索问题，我们必须要尽可能减少磁盘IO的次数. 因此降低树的高度势在必行——因为每次读取下一个树的节点就有可能是去磁盘通过IO文件读取数据. 所以原先的二路平衡查找拓广为多路平衡查找树势在必行. 这就是B系列的查找树（B、B+、B*）. 关于B树的前世今生以及B树的高维推广——R树（用于地图搜索）可参见【2】, 七月大神的博文.

Read More

Splay

缘起

【1】中讲解了AVL这种平衡查找树. 它的一大亮点就是不论你插入的数据倾斜程度有多么的严重, 都可以通过一系列的自旋操作将树的深度维持在O(logn). 进而使得BST哪怕在最坏情况下搜索的复杂度也维持在O(logn). 这是一种理想状态. 我们从【1】中的代码看到，仅仅是增加和删除就已经非常复杂了（可以说插入一个元素将耗费大量的CPU在自旋操作上）. 我们扪心自问——真的有必要吗? 举一个常识——你想读书看报、和周围人自由的交流，你有必要认识全部的8万个汉字吗,其实常用的汉字只有3500字而已. 这3500汉字已经足以覆盖近乎99%的中文材料了. 所以我们一个自然的想法是——舍弃绝对的平衡, 而将常用的数据离根节点近一点（因为日常用的数据符合28定律, 即80%使用频率的数据仅仅占据20%的总数据量）, 则总体而言, 搜索算法的均摊复杂度亦可以到达O(logn).

注意，不要小看离根节点近一点，在数据爆炸的今天，内存算法近乎不可能，多为外算法甚至分布式算法. 所以一次节点的跳转选择就意味着一次磁盘IO甚至网络IO, 众所周知，网络IO、磁盘IO远远低于内存读写，更远远低于CPU运算. 所以减少IO, 让常用的那80%的数据离根节点近一点成为提高算法性能的关键，而”离根节点近一点”就是这里的伸展操作. 也就是下面的模板中 splay2 函数. 所谓常用，就是本次操作的结果. 但是相比平衡查找树， 伸展树实现简便、无需修改节点 结构、分摊复杂度低，但可惜最坏情况下的单次操作需要O(n)时间，故难以适用于核电站、医院等对可靠性和稳定性要求极高的场合。反之，【1】中的AVL树尽管可以保证最坏情况下的单次操作速度，但需在节点中嵌入平衡因子等标识；更重要的是， 删除操作之后的重平衡可能需做多 达O(logn)次旋转， 从而频繁地导致全树整体拓扑结构的大幅度变化。

Read More

AVL

缘起

【1】中介绍了BST， 但是BST在数据倾斜的厉害的时候，树结构这种半线性数据结构蜕化为线性数据结构导致查询效率由理论的O(logn)降低为最坏的 O(n). 根本原因是在插入节点的时候, 没有动态维护树的结构, 导致树的高度不断变深. 所以需要引入一种平衡查找树——不论你插入的数据倾斜有多严重，树的深度一直维持在 O(logn). 这种查找树就是 AVL. AVL亦是BST. 只是高度维护的好.

Read More

二叉查找树(BST)

缘起

从现在开始，我们将讨论的重点将逐步转入查找技术。介绍各种精妙的查找结构——主要分成两类结构

  1. 查找树
  2. hash

查找树涉及比较，所以一般复杂度性能的上限由logn所制. 而hash不基于比较，而基于桶排序思想, 所以hash的性能能到线性.

对于计算机而言，查找是很重要的一种结构诶~ 你想想在海量信息爆炸的年代, 查找有多重要吧~

Read More