算法补天系列之有序表的四种实现方式——AVL树，SB树，红黑树，跳表（重点）介绍说明

有序表（MAP）：除了支持哈希表所有操作之外，是有序组织的，可以知道排序的。

其实红黑树，AVL，SB数，跳表这四种结构都可以实现有序表。时间复杂度是一个级别的。一般SB树常用一些，因为结合题目修改成SB数会容易一些。

这里跳表单论，另外三个都是平衡搜索二叉树序列。

首先，如果我们有一个搜索二叉树，如何能让他的增删改查就尽量快一些。一般默认搜索二叉树没有重复节点，因为我们可以通过增数据项存重述节点的信息。就是一个节点的信息多一些，也不重要。

假如我们现在有一棵搜索二叉树，我们要找一个数，或者找离这个数最近的节点，怎么办？
节点比这个数小，就往左，反之往右，走到相等或者不能再走

其实增查都简单，但是删改很难办。
首先，我们要找到这个节点在树上。
然后如果是叶子节点，或者左右孩子不全，那就很好办，删了就行，有孩子的话直接孩子代替他的环境既可以了。
如果孩子双全，那就麻烦了。左树最右或者右树最左的节点都可以，然后这个时候一般就是前两种情况了，这时如果这个节点有一个孩子，那我们就给到自己的父亲节点，毕竟自己被移走之后父节点一定有空指针能连到。

我们现在知道了搜索二叉树的操作，但是我们现在因为不平衡，所以我们是不能保证时间复杂度的。一旦不平衡，我们的时间复杂度可能就是O(N)

所以我们要保证平衡性。至少要满足相对的平衡性，别太离谱。

AVL树：是最最严格的平衡树
它每一个节点，左右子树高度差不超过一
为了满足这个操作，我们需要引入两个操作：左旋+右旋
左右旋表示的是头结点往哪边倒。
可以通过下图理解一下：

左右旋最大的意义就是为了让树变的更加平衡

而AVL发生不平衡的时候
首先，我们要意识到一件事，就是，我们要怎么意识到我们不平衡了。
为了满足AVL变态的平衡要求，我们要从改动发生的节点开始一步步往上走，看这一路的节点，是否平衡，不平衡了，就旋一下。

AVL中平衡性被破坏有四种情况：
LL,LR,RL,RR
（某边的某子树导致不平衡）
LL:一次右旋就行
RR：一次左旋就行
LR，RL：就是叫叶子结点走到头部就行了
先第一个字母旋，再第二个字母旋。

这四种的处理，其实都是常数级别的。所以调整的整体代价一定是logn级别的。

（红黑树和SB树）与AVL树的区别只在于和AVL的节点平衡性判定标准不一样，别的都一样。处理平衡的方式也是左右旋。

SB树：要求每一棵字树的大小，不小于自己兄弟节点的最大的孩子节点的子树的大小。或者说，每一个节点为根的子树，要比他所有的侄子树的节点大。这样可以确保logn的基本盘，可能有一些常数的问题。
Size-Balance树也是有四种不平衡情况：
LL，LR，RL，RR
LL：就是左孩子的左孩子的子树大于右子树。第一步，右旋，而在这一步完成之后，我们还需要递归一下，就是所有在这次右旋中改动了孩子的节点，进行判断。一般是右旋中的头结点和自己的左节点。
转法都是一样的。
不过SB树所有变的节点都要多递归一下

红黑树是最变态的：
平衡性标准：每一个节点不是红，就是黑，规定头和叶子结点（这里有大病，他的叶子结点是没有孩子的节点往下一层的空的那一层）必须为黑，任何两个红节点不能相邻。从当前头结点，到叶子结点每一条路径要求黑节点个数一样。
他想要保证的就是从头到底的路径最多不超过2倍。
目前没有什么应用的地方了，实现和修改实在是太麻烦了。
（听说华为内部考这个，员工学了两个月，学这个真的点。。。）

最后，来一个高端的——跳表
• 用户随便给，相当随意，本身是一个多链表。
• 一开始，我们默认有一个节点，我们默认这个节点拥有全局最小的key，有一个往外指的指针。
• 然后来了一个新的节点，我们扔色子（没错，你没听错），来决定这个节点有多高，来决定这个结点有多少个往外指的指针。0-1五五开，是1就表示多了一条往外指的指针，并且还要继续扔色子。然后这个节点可能层数就比较大了。
• 然后我们默认节点开始扩充。也编程同样高的层数。（只有默认节点可以，并且一直跟着对高层的节点扩充）。
• 这时候，我们又有了一个新的节点进来，层数更高，那我们先扩充默认节点，并且，开始连指针（毕竟我们是链表）怎么连呢？找到小于这个节点的最右的节点，指向这个节点。
• 类似我们这个图的效果，先3后5
•

• 假如说，我们又来了一个四，假如说4的层数是2.那我们就从最高层开始找，找完了发现4没有这一层，往下走，找到层数，大小都对的位置，插入。
•

• 我们来看这个插入，首先，我们来到20，因为70没有这一层，所有内部下移到第四层，然后右移到50，然后继续下移，到70有的一层，插入进去。
• 感觉到了吗？我们利用高度的优势，减少了很多节点的比较步骤。

我们来看看怎么找：
永远从高层出发，从上往下一层层走到不大于这个数的最右的节点
时间复杂度怎么看：
因为层数五五开扔色子，所以底层是N个，第一层接近N/2，第二层 接近N/4，一层层以此类推。
这是不是另一个变相的完全二叉树？
是的，我们通过上一层的跨步，在底层可以跨过去好多步。
所以我们说跳表在思想上就已经先进了很多，他把数据规模交给了概率，和大小解耦。