有序表
在哈希表的基础上，内部key是有序的，所有操作的时间复杂度都是O(logN)级别的
红黑树AVL树set-balance tree跳表skiplist（单链表改写）
以上都是有序表，实现原理不一样，但实现的结果操作的时间复杂度都是一样的，可能常数时间有差异，但差异很小
搜索二叉树
默认搜索二叉树上没有重复值（有重复值的话添加统计数据项即可）
添加操作
第一个进来就是头节点，然后往后进来的小的就放左边，大的放右边，每棵子树都这样操作就行
查询操作
找小于等于6的最近节点，从头节点出发，4小于6，往右树走，8大于6，往左树走，7大于6，继续往左树走，5小于6，往右树走，发现为空，返回5
删除操作
要删除的节点没有左孩子也没有右孩子，直接删掉释放掉就行
要删除的节点只有左孩子或者只有右孩子，让其孩子替代他就行
要删除的节点左右孩子都有，可以让左树上的最右节点或者右树上的最左节点来替换
比如找到右树上的最左节点，然后如果该节点有右孩子的话直接把右孩子整个给其父节点，然后把最左节点移到要删除的节点的位置
平衡性
没有平衡性没法保证以上操作时间复杂度都是O(logN)级别
狭义的平衡二叉树
左右两棵子树高度不超过1
广义的平衡二叉树
左右两棵子树的高度不相差太大即可，这样也是O(logN)的级别
AVL树严格要求左右两棵子树的高度不超过1
左旋、右旋
头节点往左倒，节点F给到节点A的右节点
右旋同理
AVL
AVL树的增删改查操作与搜索二叉树一样
但它是通过每加入、删除一个节点时，看加入节点到头节点之间每个节点是否有平衡性来检查整棵树是否有平衡性（删除的时候，如果是左右孩子都有的情况，检查是从删除节点的右子树上的最左节点一路往上）
四种没有平衡性的结构
LL与RR
左树上的左孩子过长或者右树上的右孩子过长
头节点右旋或左旋即可
LR、RL
左树上的右孩子过长或者右树上的左孩子过长
想办法把节点X转成头部
public void rebalance(AVLNode node){while(node!=null){Node parent=node.parent;int leftHeight=(node.left==null)?-1:((AVLNode)node.left).height;int rightHeight=(node.right==null)?-1:((AVLNode)node.right).height;int nodeBalance=rightHeight-leftHeight;if(nodeBalance==2){if(node.right.right!=null){node=(AVLNode)avlRotateLeft(node);//RR 旋转里面有更新高度的操作break;}else{node=(AVLNode)doubleRotateRightLeft(node);//RLbreak;}}else if(nodeBalance==-2){if(node.left.left!=null){node=(AVLNode)avlRotateRight(node);//LLbreak;}else{node=(AVLNode)doubleRotateLeftRight(node);//LRbreak;}}else{updateHeight(node);//更新高度}node=(AVLNode)parent;//node往上查是否平衡}}
AVL与红黑树、SB树的区别
红黑树和SB树的增删改查操作、检查时机都与AVL树一样
唯一的区别是具体检查每一个节点的时候的违规条件不一样以及AVL树维持的是高度信息、红黑树和SB树（节点数量、大小）维持的是其他信息
实现平衡性的方式也是通过左旋和右旋
SB树
平衡性：
每棵子树的大小，不小于其兄弟的子树大小既每棵叔叔树的大小，不小于其任何侄子树的大小
这样的话左右孩子高度差不会相差很多，最多是两倍+1
一样是四种不平衡的情况
LL、RR
假设现在L的左子树A的节点个数大于R的节点个数
让节点T右旋然后看谁的子节点发生了变化：L和T对L和T做递归判断
LR、RL
LR：L的右子树B（左孩子的右子树）的节点个数大于R的节点个数
把B搞成头节点
然后看哪些节点的左右孩子发生了变化就递归
private SBTNode<K, V> matain(SBTNode<K, V> cur) {if (cur == null) {return null;}if (cur.l != null && cur.l.l != null && cur.r != null && cur.l.l.size > cur.r.size) {cur = rightRotate(cur);cur.r = matain(cur.r);cur = matain(cur);} else if (cur.l != null && cur.l.r != null && cur.r != null && cur.l.r.size > cur.r.size) {cur.l = leftRotate(cur.l);cur = rightRotate(cur);cur.l = matain(cur.l);cur.r = matain(cur.r);cur = matain(cur);} else if (cur.r != null && cur.r.r != null && cur.l != null && cur.r.r.size > cur.l.size) {cur = leftRotate(cur);cur.l = matain(cur.l);cur = matain(cur);} else if (cur.r != null && cur.r.l != null && cur.l != null && cur.r.l.size > cur.l.size) {cur.r = rightRotate(cur.r);cur = leftRotate(cur);cur.l = matain(cur.l);cur.r = matain(cur.r);cur = matain(cur);}return cur;}
红黑树
每个节点存一个颜色信息，不是黑就是红要求头节点和叶子节点（这里的叶子节点指的是传统的叶子节点再往下一层的空节点）都是黑的红色的节点之间不相邻对任何一颗子树来说，从某一个头部cur出发到叶子节点的路径上要求黑色的节点数量一样在这样的四个要求的基础上
任何一颗子树的最长路径是红黑红黑这样特征的路径，最短的路径是全是黑的节点，而根据第四个要求可以得知，两条路径的长度相差不会超过两倍
因此能做到以上四个要求，红黑树基本上就是平衡的
跳表
加入一个节点时，先给该节点随机生成，看能生成几层（比如是0.5的概率生成，0.5的概率不生成，一直随机到不生成层数为止），然后从最高层开始往下，找到小于等于该数的最近节点，如果该节点生成的层数没到这一层，就往下，在下一层就从上一层找到的最近节点开始找小于等于的新的最近节点，直到该节点生成的层数到了，才开始挂，这样的过程，就跳过了很多实际上不需要遍历的对象，提升了有序链表的加入、查询速度
删除的过程就是先查询，看该节点是否存在，存在的话就删除，把要删除的节点的前面和后面连上就行了
第0层一定存在所有节点（第零层就是传统的单链表+有序）
时间复杂度：
每次加一个节点的时候加层数的时候概率都是0.5，即数据量大的时候，每一层的节点数量就类似一颗满二叉树
