有序表相关知识点整理

哈希表和有序表：
哈希表的存储是无序的，哈希表的增删改查操作被认为是O(1)(实际上在增加时的调整操作还是O(logN)级别,但是常数项很小，并且对于具有虚拟机的语言可以进行离线操作，在需要调整的时候可以不占用用户时间)
有序表的存储是根据key的排列的，有序表可以由多种数据结构来实现，主要有AVL树、SB树、红黑树和跳表。但是要求对于有序表的增删改查操作O(logN).

AVL树，SB树和红黑树的数据结构是基于搜索二叉树的，他们除了在添加删除节点时的调整以外别的操作都是相同的，大量的API直接在搜索二叉树上修改即可（例如寻找<=num的最大节点，寻找第100个key等等），但是可能要注意我们增加的一些数据项需要在增删操作上进行维持（修改）。

搜索二叉树注意两点：

我们一般所说的二叉树左小右大是绝对的，并不能左边小于等于或者右边是大于等于，这是由于对二叉树的平衡性进行调整的时候使用的左旋右旋可能会出错（比如父节点3的左节点也是3，如果对父节点右旋，会出现右边等于父的情况）
所以说一般来说我们不允许同样的key，但是并不是有序表结构不能存储key相等的数据，我们可以通过对key加一个times变量（这是对于无value的类TreeSet结构，要注意它和size的区别，在大多数结构中我们说的size是不同的key的个数，例如SB树中size）；或者value使用ArrayList等结构存储多个value。

搜索二叉树：

增：给定一个element，当小于cur.key就左划，大于cur.key，就右划；直到划动到null，就挂到拥有这个null的节点下面
改：给定一个element，查找到修改即可
查：给定一个element，当小于cur.key就左划，大于cur.key，就右划；相等就返回，没有就返回null
这些都没什么好说的，时间复杂度O(logN)

删：这个主要分为四种情况：

要删除节点没有左孩子没有右孩子：直接删除即可
要删除节点有左孩子没有右孩子：左孩子替换他的位子
要删除节点没有左孩子有右孩子：右孩子去替换位子
要删除节点有左孩子有右孩子：显然我们要找到一个满足小于左树大于右树的节点来替换他，显然有两个点满足，左子树的最右节点和右子树的最左节点都可以。

搜索二叉树的平衡性：
在我们建立搜索二叉树的时候可能会一边过大一边过小，树的平衡由用户的输入来决定，这个非常影响性能，我们可能希望我们的二叉树是一个完美平衡的树，这让才能让性能更好的逼近logN水平。因此我们有左旋和右旋操作，这个的思想就是让左子节点或者右子节点来代替现在的父节点。主要就是代码问题，如何来替环境。
图片说明

AVL树：
上面我们说到，AVL、SB和红黑树都是基于搜索二叉树的，只有在增加和删除时候的调整策略不同。
AVL树的调整策略是高度信息，就是左树和右树的差值不能大于1；
对于AVL树，差值超过1只会有下面四种情况的1种出现

LL型：左树的左子树大，右旋操作
RR型：右树的右子树大，左旋操作
LR型：左树的右子树大，先对右子树左旋变为LL型再右旋。
RL型：右树的左子树大，先对左子树右旋变成RR型再左旋。

为什么我们只会存在四种情况中的一种呢?
因为我们每次添加只会增加一个节点，高度之差原来最多是1，同时左右现在的高度差最大就是2，只可能有其中的一种（要是同时满足两个情况的话，原来高度差必为2）
那么我们在添加节点和删除节点的时候哪些点需要做平衡性检查呢？
因为从你变化的点向上的结构都出现了变化，所以需要从你这个点向上到root节点都需要调整：
尤其注意的是删除情况的左右孩子都有的情况，并不是从这个删除节点向上调整，而是从右树的最左节点这个替换节点的原位置向上调整。
因为要向上调整，所以我们可以维持一个parent节点信息，当然也可以利用递归来避免使用parent信息，可以避免使用parent信息来减少代码复杂度（因为在所有的操作里，parent的信息都要去维持）

SB树：
调整策略：叔叔节点不能小于侄子节点（也就是说左右两颗子树的大小差别不会超过一倍）。
对于从下向上调整的每个节点来说，这个结构天然就会有四种情况：
LL型：LR型：RR型：RL型：
和之前的左旋右旋操作相同，但是由于我们的调整策略比较宽松，因此我们现在调整之后的子树情况并不一定满足要求，因此子树的新头节点依然要再次进行平衡性判定，同时该子树的子树的情况也发生了变化，也需要查看平衡性，（所以LL型和RR型需要再次对该子树平衡性的两个节点进行平衡性操作，LR和RL树需要三个节点的重平衡）；这样一直向下调整，因为这个往下几步并不确定，因此我们这里使用递归方法来做平衡性调整直到满足该步骤要求，但是已有研究证明，这个向下的步骤是有限的几次，因此该步的调整依然是O(1)的。
因此从下向上的整个调整过程的时间复杂度是O(logN)的。

由于这个宽松的要求使得调整过程考虑情况非常严谨，因此SB树并不需要像AVL树那样每一步都要调整精确。SB树可以不在删除阶段去调整平衡性，同时只在添加阶段去调整平衡性依然是O(logN)的复杂度。SB树的代码利用递归不需要维持parent信息，并且在删除阶段不需要进行平衡性调整，代码简洁，因此当题目需要对现有的有序表修改时，是一个常见的选择。另一个常见的选择是下面的跳表。
SB树是有序表结构中常数时间较少的结构。

SkipList：跳表

显然这个数据结构不是依赖于搜索二叉树的，而是依赖一个链表结构，这个数据结构相对先进一些。而且也比较简洁。
跳表的头节点不存储数据，可以认为是一个key=null，value=""的节点，他也是最小的节点，head的层数和最高层数保持一致；
跳表的结构就是从小到大向后串起来，但是节点和节点之间的链不一定是一个，而是随机的，我们可以想象为层数。每一个节点的层数由随机决定（连续掷色子，当小于0.5停止，掷色子的次数就是该节点向后的层数）

增：

按照上面说的方式来决定这个节点的层数；
寻找节点应该放在哪里，我们从head和最高层开始，每一层寻找小于addKey的最右节点;
如果新增节点没有这一层，直接从这个小于addKey最右节点向下；
如果新增节点有这一层，就插入到这个节点后面，依然从这个节点向下，去找下一层的小于addKey的最右节点

删：

和增加基本相同，就是在每一层找到小于这个节点的最右节点，后面是要删除的节点，就修改next信息，没有就向下走就行了
你删除的节点可能是跳表最高层的拥有者，因此每次删除要看一下这层是不是就剩下head，如果是，把这层删除掉

原理：
从上面每个节点的层数由0.5掷色子得来我们可以看到：
第0层：N个节点
第1层：N/2个节点
第2层：N/4个节点
。。。
由此我们可以看到在高层寻找该层最右节点所走过的一个节点可能在第0层已经走过了很多个节点，这个方法类似于我们利用层数来对数组进行二分，也类似在二叉树上我们选择了一条路径走了下去，这个算法的复杂度也可以显然看到O(logN)水平的。

红黑树：说实话有点复杂，这里我就不细说了，他太秀了。。。贴个帖子