ordered-list

有序表时间复杂度为：$O(logN)$。默认不包含重复节点。可以通过以下四种方式实现：

• 红黑树

• AVL树

• SB树

• 跳表

  前三种可以通过平衡搜索二叉树(BST)来实现，跳表是通过链表实现的。BST是基于搜索二叉树实现的。如果不考虑性能，搜索二叉树有下面三种方法：

搜索二叉树有三个操作，分别是：

• 查找

• 新增

• 删除

  • 如果既没有左孩子也没有右孩子，直接删除就好，不过得记录父节点

  • 如果左右孩子不双全，直接让父节点接管当前待删除节点的左孩子或右孩子即可

  • 如果左右孩子双全，则找到右孩子左子树上没有左孩子的节点A，用A替换待删除节点，A的右孩子由A的父节点接管

很容易认识到搜索二叉树很容易打破$O(logN)$的复杂度，比如全是右子树的节点，而左子树没有节点。这样左右子树的节点规模差距过大。那么如果我们保证左右子树的规模差距不大，那么就实现了$O(logN)$的复杂度。AVL树、红黑树、SB树就保证了这样一个特性。左右子树的规模不会相差过大，只不过这三种树对于平衡的定义不同。并且这三种树都提供了左旋与右旋操作实现了平衡。ST与BST的概念范围如下：

• 搜索二叉树

• 带有左旋与右旋操作的搜索二叉树(但是左旋与右旋操作如何使用不知道)

• BST实现了如何使用左旋与右旋操作

• AVL树是最严格的平衡二叉树，平衡的定义为：任何一颗树的左右子树高度差不超过1

• 红黑树同样保持自己的左旋与右旋操作，有自己平衡的定义

• SB树类似

下面描述什么是左旋与右旋操作：

• 左旋：一颗子树的左旋是指该子树的头节点往左边倒，如果新的头节点有左孩子，那么就成为旧头节点的右孩子

• 右旋：子树的头节点向右边倒，同样如果有新的头节点由右孩子，就成为老头节点的左孩子

AVL树

AVL树与普通的搜索二叉树的增删查改没有任何区别，只不过在增删节点后，需要查看树是否仍保持平衡性：

• 增加节点x：增加节点后，依次查看以x为头节点的树是否有平衡性，一直向上查询父节点的所有子树是否有平衡性。如果没有平衡，那么做左旋或右旋，调整完后继续查询直至没有父节点。

• 删除节点x：删除节点时有一种情况非常特殊，就是左右孩子都全的情况，这时以x右孩子的新头节点为起点开始查平衡性，直至没有头节点

整体检查流程已经清楚了，那么在一个节点时，到底如何查询平衡性？总体分为四种情况：

• LL型：一个节点的左子树的左边过长，导致平衡性被破坏，这时只需做一次右旋

• RR型：一个节点的右子树的右边过长，导致平衡新被破坏，这时只需做一次左旋

• LR型：头节点左子树的右子树过长，这时只需考虑将左子树的右孩子设为新头节点即可，即先左旋再右旋

• RL型：头节点右子树的左子树过长，与上面一样，考虑将右子树的左孩子设为新头节点即可，即先右旋再左旋

红黑树

红黑树与AVL树唯一的差别就是平衡性的标准不同，其他全部和AVL树相同，下面介绍一下什么是红黑树：

• 一个节点不是红就是黑的

• 头节点和底层叶节点必须为黑(这里的叶节点指最底层为null的节点)

• 任何两个红节点不能相邻

• 对于任何一颗子树，从头部cur节点出发，要求到达叶节点的每一条路径，要求黑节点的数量一样

上面所有的要求只为达成一件事：一颗树左右两条路径的长度不超过一倍，因为一条路径最长只能是红黑节点交替，最短路径只能是黑节点，又因为黑节点数量一样多，所以长度不会超过一倍。

SB树

SB树的平衡性定义：如果X有侄子节点，则必须保证以X为头的节点不小于所有侄子树的大小，与AVL调整平衡性的操作略有不同

• LL型：先左旋，侄子节点成为新的头节点后，然后对字节点发生变化的节点继续递归进行调整操作

跳表

首先有一个默认节点，我们默认这个节点的key是全局最小的，比用户给的任意一个数的