聊聊红黑树和跳表
前言
在咱们聊红黑树之前，我们不妨先思考一个问题，在一组数中如何最快查找存在某个数呢？
- 笔者第一反应是构造hash表一个你乐意插多少插多少，O(1)大法好。
那么如果需要构造有序列表后再查呢？
- 那么咱们用二分法，O(logN)还是不错的
从上我们就可以引申出二叉树来实现二分查找了，对于一个完全二叉树来说，查找一个数是O(logN)，插入或删除同样是O(logN)，但是现实会这么美好么？
二叉树的退化
对于一个构造好的二叉树，我们不断的插入一组组顺序的数据，很容易就会使树变的不平衡，极端的会退化一个O(N)的链表。
如何让我们构造的查找树平衡呢？二三树的办法是：
- 用不同类型的节点来标记，比如三节点就有退化的味道
- 坏味道堆积会使三节点向根移动
- 根会因三节点而移动从而达到平衡
二三树
二三树有两种节点，二节点就像普通二叉树一样，存放一个数据，其左分支下皆小该值，其右分支皆大于该值，三节点内存放两个数据，其左分支下皆小于该节点内数值，其右分支下皆大于该节点内右数值，其中间分支下值位于左数值与右数值间。
我们从构造一个二三树来了解他是怎么维持平衡的：
上图描绘了一个四个数值的二三树的构造过程，虚线框内表示稳定结构树（即插入完成的树状态）。
我们继续向二三树中插入顺序的值：
可以发现，在将三节点不断的拆分和向根部递推后构造形成的树总是稳定的，我们可以认为二三树构造的二分查找树是颗平衡树，即在动态的构造过程中，我们依旧可以维持稳定的O(logN)的查询效率。
红黑树
当你理解了二三树就理解了红黑树，将二三树图中的红色数据理解为红节点，并将其右侧的值用指针链接就构造了一颗红黑树。
跳表
这是一个类似二分查找的算法，我们可以简单的理解为是链表+多级索引。
构造
咱们先从构造一个链表开始
显而易见，查询插入和删除都是O(n)
那咱们再为这个链表添加一级索引呢？
比如咱们要找其中的某个数n（非索引节点），一个一个跳着找是趋向于n/2次找到，虽然复杂度还是O(n)，但是不是比刚才好点了呢？
那咱们再为这个链表加一级索引
同样我们去查某个数n（非索引节点），二级索引命中区间使用了n/4次，一级索引找到该数使用了1次
一鼓作气，再加一级!
去查某个数n（非索引节点），三级索引命中区间使用了n/8次
同样的，我们不断的向上加索引，加至顶层索引只有两个节点
这时我们去查找某个点时，是不是发现我们好像用索引构造了一个二分树？
对了，现在查询已经O(logN)了。
插入
对于红黑树而言，插入是个无比痛苦的事情，大概步骤如下：
- 找到插入位置
- 判断插入后是否影响平衡，影响平衡后分裂
- 分裂后向上插入，回到2
而跳表使用随机级数策略，只要保证随机的级数符合全索引内出现的概率即可，什么意思呢？
我有一个18个点跳表，跳数2（索引间有一个节点），最高级数4, 此时插入一个数
首先我们要计算各级数索引在全部索引中的概率：
- 4级: 2/(2^4 + 2^3 + 2^2 + 2) = 1/15
- 3级: 2^2/(2^4 + 2^3 + 2^2 + 2) = 2/15
- 2级: 2^3/(2^4 + 2^3 + 2^2 + 2) = 4/15
- 1级: 2^4/(2^4 + 2^3 + 2^2 + 2) = 8/15
插入一个节点的步骤：
- 找到插入位置
- 按上述概率随机生成级数，修改查询路径记录的索引并插入
学过概率论的同学应该知道，这样生成的跳表分布基本上是均匀的，那么咱们就可以认为这样生成的跳表查询复杂度就是O(logN)。
为什么用跳表
红黑树真好，但是跳表真香。
为什么跳表香？
- 好实现
- 索引便利，可以快速找到区间中批量数据，更方便做批操作。
至于为啥说好实现、好做批量操作，自己手写个跳表直观感受一下就好了呀。
为什么不用跳表
- 如果数量级少，索引级数小的情况下，随机构建插入节点存在偶发的低效。
- 高度扩容后顺序大量插入数据会导致扩容前数据索引不会被高级索引cover