, V> {private SBTNode root;private SBTNode rightRotate(SBTNode cur) {SBTNode leftNode = cur.l;cur.l = leftNode.r;leftNode.r = cur;leftNode.size = cur.size;cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;return leftNode;}private SBTNode leftRotate(SBTNode cur) {SBTNode rightNode = cur.r;cur.r = rightNode.l;rightNode.l = cur;rightNode.size = cur.size;cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;return rightNode;}private SBTNode maintain(SBTNode cur) {if (cur == null) {return null;}int leftSize = cur.l != null ? cur.l.size : 0;int leftLeftSize = cur.l != null && cur.l.l != null ? cur.l.l.size : 0;int leftRightSize = cur.l != null && cur.l.r != null ? cur.l.r.size : 0;int rightSize = cur.r != null ? cur.r.size : 0;int rightLeftSize = cur.r != null && cur.r.l != null ? cur.r.l.size : 0;int rightRightSize = cur.r != null && cur.r.r != null ? cur.r.r.size : 0;if (leftLeftSize > rightSize) {cur = rightRotate(cur);cur.r = maintain(cur.r);cur = maintain(cur);} else if (leftRightSize > rightSize) {cur.l = leftRotate(cur.l);cur = rightRotate(cur);cur.l = maintain(cur.l);cur.r = maintain(cur.r);cur = maintain(cur);} else if (rightRightSize > leftSize) {cur = leftRotate(cur);cur.l = maintain(cur.l);cur = maintain(cur);} else if (rightLeftSize > leftSize) {cur.r = rightRotate(cur.r);cur = leftRotate(cur);cur.l = maintain(cur.l);cur.r = maintain(cur.r);cur = maintain(cur);}return cur;}private SBTNode findLastIndex(K key) {SBTNode pre = root;SBTNode cur = root;while (cur != null) {pre = cur;if (key.compareTo(cur.key) == 0) {break;} else if (key.compareTo(cur.key) < 0) {cur = cur.l;} else {cur = cur.r;}}return pre;}private SBTNode findLastNoSmallIndex(K key) {SBTNode ans = null;SBTNode cur = root;while (cur != null) {if (key.compareTo(cur.key) == 0) {ans = cur;break;} else if (key.compareTo(cur.key) < 0) {ans = cur;cur = cur.l;} else {cur = cur.r;}}return ans;}private SBTNode findLastNoBigIndex(K key) {SBTNode ans = null;SBTNode cur = root;while (cur != null) {if (key.compareTo(cur.key) == 0) {ans = cur;break;} else if (key.compareTo(cur.key) < 0) {cur = cur.l;} else {ans = cur;cur = cur.r;}}return ans;}// 现在，以cur为头的树上，新增，加(key, value)这样的记录// 加完之后，会对cur做检查，该调整调整// 返回，调整完之后，整棵树的新头部private SBTNode add(SBTNode cur, K key, V value) {if (cur == null) {return new SBTNode(key, value);} else {cur.size++;if (key.compareTo(cur.key) < 0) {cur.l = add(cur.l, key, value);} else {cur.r = add(cur.r, key, value);}return maintain(cur);}}// 在cur这棵树上，删掉key所代表的节点// 返回cur这棵树的新头部private SBTNode delete(SBTNode cur, K key) {cur.size--;if (key.compareTo(cur.key) > 0) {cur.r = delete(cur.r, key);} else if (key.compareTo(cur.key) < 0) {cur.l = delete(cur.l, key);} else { // 当前要删掉curif (cur.l == null && cur.r == null) {// free cur memory -> C++cur = null;} else if (cur.l == null && cur.r != null) {// free cur memory -> C++cur = cur.r;} else if (cur.l != null && cur.r == null) {// free cur memory -> C++cur = cur.l;} else { // 有左有右SBTNode pre = null;SBTNode des = cur.r;des.size--;while (des.l != null) {pre = des;des = des.l;des.size--;}if (pre != null) {pre.l = des.r;des.r = cur.r;}des.l = cur.l;des.size = des.l.size + (des.r == null ? 0 : des.r.size) + 1;// free cur memory -> C++cur = des;}}// cur = maintain(cur);return cur;}private SBTNode getIndex(SBTNode cur, int kth) {if (kth == (cur.l != null ? cur.l.size : 0) + 1) {return cur;} else if (kth <= (cur.l != null ? cur.l.size : 0)) {return getIndex(cur.l, kth);} else {return getIndex(cur.r, kth - (cur.l != null ? cur.l.size : 0) - 1);}}public int size() {return root == null ? 0 : root.size;}public boolean containsKey(K key) {if (key == null) {throw new RuntimeException("invalid parameter.");}SBTNode lastNode = findLastIndex(key);return lastNode != null && key.compareTo(lastNode.key) == 0 ? true : false;}// （key，value） put -> 有序表 新增、改valuepublic void put(K key, V value) {if (key == null) {throw new RuntimeException("invalid parameter.");}SBTNode
