ans = null;AVLNode cur = root;while (cur != null) {if (key.compareTo(cur.k) == 0) {ans = cur;break;} else if (key.compareTo(cur.k) < 0) {ans = cur;cur = cur.l;} else {cur = cur.r;}}return ans;}private AVLNode findLastNoBigIndex(K key) {AVLNode ans = null;AVLNode cur = root;while (cur != null) {if (key.compareTo(cur.k) == 0) {ans = cur;break;} else if (key.compareTo(cur.k) < 0) {cur = cur.l;} else {ans = cur;cur = cur.r;}}return ans;}//添加节点private AVLNode add(AVLNode cur, K key, V value) {if (cur == null) {return new AVLNode(key, value);} else {if (key.compareTo(cur.k) < 0) {cur.l = add(cur.l, key, value);} else {cur.r = add(cur.r, key, value);}cur.h = Math.max(cur.l != null ? cur.l.h : 0, cur.r != null ? cur.r.h : 0) + 1;return maintain(cur);}}// 在cur这棵树上，删掉key所代表的节点// 返回cur这棵树的新头部private AVLNode delete(AVLNode cur, K key) {if (key.compareTo(cur.k) > 0) {cur.r = delete(cur.r, key);} else if (key.compareTo(cur.k) < 0) {cur.l = delete(cur.l, key);} else {if (cur.l == null && cur.r == null) {cur = null;} else if (cur.l == null && cur.r != null) {cur = cur.r;} else if (cur.l != null && cur.r == null) {cur = cur.l;} else {AVLNode des = cur.r;while (des.l != null) {des = des.l;}cur.r = delete(cur.r, des.k);des.l = cur.l;des.r = cur.r;cur = des;}}if (cur != null) {cur.h = Math.max(cur.l != null ? cur.l.h : 0, cur.r != null ? cur.r.h : 0) + 1;}return maintain(cur);}public int size() {return size;}//是否包含某个keypublic boolean containsKey(K key) {if (key == null) {return false;}AVLNode lastNode = findLastIndex(key);return lastNode != null && key.compareTo(lastNode.k) == 0 ? true : false;}public void put(K key, V value) {if (key == null) {return;}AVLNode lastNode = findLastIndex(key);if (lastNode != null && key.compareTo(lastNode.k) == 0) {lastNode.v = value;} else {size++;root = add(root, key, value);}}public void remove(K key) {if (key == null) {return;}if (containsKey(key)) {size--;root = delete(root, key);}}public V get(K key) {if (key == null) {return null;}AVLNode lastNode = findLastIndex(key);if (lastNode != null && key.compareTo(lastNode.k) == 0) {return lastNode.v;}return null;}public K firstKey() {if (root == null) {return null;}AVLNode cur = root;while (cur.l != null) {cur = cur.l;}return cur.k;}public K lastKey() {if (root == null) {return null;}AVLNode cur = root;while (cur.r != null) {cur = cur.r;}return cur.k;}public K floorKey(K key) {if (key == null) {return null;}AVLNode lastNoBigNode = findLastNoBigIndex(key);return lastNoBigNode == null ? null : lastNoBigNode.k;}public K ceilingKey(K key) {if (key == null) {return null;}AVLNode lastNoSmallNode = findLastNoSmallIndex(key);return lastNoSmallNode == null ? null : lastNoSmallNode.k;}}
SB树（size--tree）
1）让每一个叔叔节点为头的数，节点个数都不少于其任何一个侄子节点
2）也是从底层被影响节点开始向上做路径每个节点检查
3）与AVL树非常像，也是四种违规类型：LL、RR、LR、RL
4）与AVL树非常像，核心点是：
LL（做一次右旋）、RR（做一次左旋）
LR和RL（利用旋转让底层那个上到顶部）
5）与AVL树不同的是，每轮经过调整后，谁的孩子发生变化了，谁就再查
SB树在使用时候的改进
1）删除时候可以不用检查
2）就把平衡性的调整放在插入的时候
3）因为这种只要变就递归的特性，别的树没有
4）可以在节点上封装别的数据项，来增加功能
public static class SBTNode, V> {public K key;public V value;public SBTNode l;public SBTNode r;public int size; // 不同的key的数量public SBTNode(K key, V value) {this.key = key;this.value = http://www.kingceram.com/post/value;size = 1;}}public static class SizeBalancedTreeMap