搜索二叉树删除key
0）先找到key所在的节点
1）如果该节点没有左孩子、没有右孩子，直接删除即可
2）如果该节点有左孩子、没有右孩子，直接用左孩子顶替该节点
3）如果该节点没有左孩子、有右孩子，直接用右孩子顶替该节点
4）如果该节点有左孩子、有右孩子，用该节点后继节点顶替该节点
【三十三算法数据结构----有序表】搜索二叉树特别不讲究
1）基础的搜索二叉树，添加、删除时候不照顾平衡性
2）数据状况很差时，性能就很差
给搜索二叉树引入两个动作：左旋、右旋
AVL树、SB树、红黑树的共性：给搜索二叉树引入两个动作：左旋、右旋，调整平衡性
1）都是搜索二叉树
2）插入、删除、查询（一切查询）搜索二叉树怎么做，这些结构都这么做
3）使用调整的基本动作都只有左旋、右旋
4）插入、删除时，从最底层被影响到的节点开始，对往上路径的节点做平衡性检查
5）因为只对一条向上路径的每个节点做O(1)的检查和调整，所以可以做到O(logN)
AVL树、SB树、红黑树的不同
1）平衡性的约束不同
AVL树最严格、SB树稍宽松、红黑树最宽松
2）插入、删除和搜索二叉树一样，但是额外，做各自的平衡性调整 。各自的平衡性调整所使用的动作都是左旋或者右旋
AVL树
1）最严格的平衡性，任何节点左树高度和右树高度差不超过1
2）往上沿途检查每个节点时，都去检查四种违规情况：LL、RR、LR、RL
3）不同情况虽然看起来复杂，但是核心点是：
LL（做一次右旋）、RR（做一次左旋）
LR和RL（利用旋转让底层那个上到顶部）
//定义结构public static class AVLNode, V> {public K k;public V v;public AVLNode l;public AVLNode r;public int h;public AVLNode(K key, V value) {k = key;v = value;h = 1;}}public static class AVLTreeMap, V> {private AVLNode root;private int size;public AVLTreeMap() {root = null;size = 0;}//右旋private AVLNode rightRotate(AVLNode cur) {AVLNode left = cur.l;cur.l = left.r;left.r = cur;cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1;left.h = Math.max((left.l != null ? left.l.h : 0), (left.r != null ? left.r.h : 0)) + 1;return left;}//左旋private AVLNode leftRotate(AVLNode cur) {AVLNode right = cur.r;cur.r = right.l;right.l = cur;cur.h = Math.max((cur.l != null ? cur.l.h : 0), (cur.r != null ? cur.r.h : 0)) + 1;right.h = Math.max((right.l != null ? right.l.h : 0), (right.r != null ? right.r.h : 0)) + 1;return right;}//调整平衡性private AVLNode maintain(AVLNode cur) {if (cur == null) {return null;}int leftHeight = cur.l != null ? cur.l.h : 0;int rightHeight = cur.r != null ? cur.r.h : 0;if (Math.abs(leftHeight - rightHeight) > 1) {if (leftHeight > rightHeight) {int leftLeftHeight = cur.l != null && cur.l.l != null ? cur.l.l.h : 0;int leftRightHeight = cur.l != null && cur.l.r != null ? cur.l.r.h : 0;if (leftLeftHeight >= leftRightHeight) {cur = rightRotate(cur);} else {cur.l = leftRotate(cur.l);cur = rightRotate(cur);}} else {int rightLeftHeight = cur.r != null && cur.r.l != null ? cur.r.l.h : 0;int rightRightHeight = cur.r != null && cur.r.r != null ? cur.r.r.h : 0;if (rightRightHeight >= rightLeftHeight) {cur = leftRotate(cur);} else {cur.r = rightRotate(cur.r);cur = leftRotate(cur);}}}return cur;}private AVLNode findLastIndex(K key) {AVLNode pre = root;AVLNode cur = root;while (cur != null) {pre = cur;if (key.compareTo(cur.k) == 0) {break;} else if (key.compareTo(cur.k) < 0) {cur = cur.l;} else {cur = cur.r;}}return pre;}private AVLNode findLastNoSmallIndex(K key) {AVLNode