1-2-3-DeterminSkipList

1-2-3 DeterminSkipList 1-2-3确定性跳跃表（十字链接实现） 前言 在前面的章节中实现过很多可以以对数时间最坏或者摊还时间运行的自平衡或者是平衡树，其中比较重要的就是红黑树的实现，事实上红黑树已经可以说是平衡树中的最优结构了，无论是从操作的运行时间界上，还是空间复杂度上基本上很难有其他的数据结构可以超越了，但是红黑树的一个明显的确定就是实现过程太过于复杂，考虑的情况还是相对较多的，很少有人在短时间里随手就可以写一个红黑树出来，那么有什么其他相对简单的数据结构也可以相对简单的到达红黑树那样的性能呢，其实是有的，正是现在要给大家介绍的一个数据结构—确定性跳跃表，事实上除了在空间复杂度上，该结构不及红黑树（大概需要红黑树空间复杂的1.5到2倍），在操作的时间复杂度上确定性跳跃表是完全可以媲美红黑树的，甚至在某些特殊操作系统上其空间复杂度也不输红黑树

由来与其性质 首先确定性跳跃表是对基于随机化算法的跳跃表的一种变体，通过简单的条件束缚使得其期望时间界变成最坏时间界，在跳跃表中，任意K阶结点的第I阶链接的下一个结点至少具有I阶，但是具体上多少阶取决于随机数，而且这个性质并没有保证高阶结点间的低阶结点个数，所有不能保证在常数个向前链后可以保证下降到下一层，这就没办法保证其操作的最坏时间界为对数，所有在确定性跳跃表中我们附加一个条件，两个高度为h的结点间的间隙容量为高度为h-1的结点个数，且除了头尾结点外的所有结点间的间隙容量必须是1,2,3（其实1-5也可以，这样形成的确定性跳跃表就是1-5确定性跳跃表，但是目前学术上还没有证明哪个范围的更优）中的一个数，在这个条件下，我们可以很明显的判断这样形成的跳跃表操作的最坏时间界必然是对数的。

插入 在插入中唯一需要考虑的情况就是向一个间隙容量为3的结点中插入结点时的操作，其实也非常简单，只需要把其中的第二个结点个高度提升这样就形成了两个间隙容量为1的结点对，插入也就可以顺利进行了，最后一个要注意的就是记得判断header结点的高度是否需要提高，除此之外就没有别的需要讲了，事实上，正如你看到的，确定性跳跃表插入部分的代码也如我讲述部分一样少的惊人

删除 确定性跳跃表唯一的难点便是在删除部分上，同插入操作一样，我们还是自顶先下的进行删除查找，因为一个高度为h的结点在十字链表的表示中会出现h次，所以自顶向下删除也方便操作，在每一层中我们需要考虑的是在下一层的结点对的间隙容量为1的情况，只有这种情况下的删除才可能破坏确定性跳跃表的性质，主要分为两种情况，一：如果在该层中的当前结点没有前导结点时，考虑其后续结点就下一层的间隙容量，如果容量不为1，可以考虑从中借一个结点过来（具体方法就是将当前结点的高度减低，后续结点的间隙容量中的结点高度升高），如果容量也为1，那就可以将其后续结点的高度减低（具体的操作就是删除该层的后续结点）二：如果在该层中的当前结点有前导结点时，考虑其前导结点的下一层的间隙容量，同上述操作，重复上述查找到达最后一层时根据删除结点个高度分为两中情况，如果高度为1，非常简单，直接将其删除就可以了（这里有一个细节处理，将真正的删除结点转化为删除结点右结点，然后删除其右结点这样并不是多次一举，而是防止该删除结点为底层的第一个结点时删除这结点会导致链断开），如果不为1，那么还要考虑将所有的上层中的该删除结点用其最后一层的前导结点替代，然后将其删除，在上述操作完成后，还要判断是否需要降低header结点的高度，至此删除操作完成

具体细节部分可以参考代码1-2-3确定性跳跃表

                                                By: Y F
                                                2019.8.6