lastNode = findLastIndex(key);if (lastNode != null && key.compareTo(lastNode.key) == 0) {lastNode.value = http://www.kingceram.com/post/value;} else {root = add(root, key, value);}}public void remove(K key) {if (key == null) {throw new RuntimeException("invalid parameter.");}if (containsKey(key)) {root = delete(root, key);}}public K getIndexKey(int index) {if (index < 0 || index >= this.size()) {throw new RuntimeException("invalid parameter.");}return getIndex(root, index + 1).key;}public V getIndexValue(int index) {if (index < 0 || index >= this.size()) {throw new RuntimeException("invalid parameter.");}return getIndex(root, index + 1).value;}public V get(K key) {if (key == null) {throw new RuntimeException("invalid parameter.");}SBTNode lastNode = findLastIndex(key);if (lastNode != null && key.compareTo(lastNode.key) == 0) {return lastNode.value;} else {return null;}}public K firstKey() {if (root == null) {return null;}SBTNode cur = root;while (cur.l != null) {cur = cur.l;}return cur.key;}public K lastKey() {if (root == null) {return null;}SBTNode cur = root;while (cur.r != null) {cur = cur.r;}return cur.key;}public K floorKey(K key) {if (key == null) {throw new RuntimeException("invalid parameter.");}SBTNode lastNoBigNode = findLastNoBigIndex(key);return lastNoBigNode == null ? null : lastNoBigNode.key;}public K ceilingKey(K key) {if (key == null) {throw new RuntimeException("invalid parameter.");}SBTNode lastNoSmallNode = findLastNoSmallIndex(key);return lastNoSmallNode == null ? null : lastNoSmallNode.key;}}
聊聊红黑树
1）平衡性规定非常诡异
2）平衡性调整最为复杂
3）优点在于每次插入删除扰动较好，但是在今天看来这个优势也极其微弱了
原因：贪图扰动小的话，B+树、2-3-4树可能更好，还是那句话，到底图什么
4）除此之外，红黑树并不比AVL树、SB树、跳表更加优秀
5）面试上遇到，说清楚道理，不行就举报 。。。
跳表（）
1）结构上根本和搜索二叉树无关
2）利用随机概率分布来使得高层索引可以无视数据规律，做到整体性能优良
3）思想是所有有序表中最先进的
4）结构简单就是多级单链表
// 跳表的节点定义public static class SkipListNode, V> {public K key;public V val;public ArrayList> nextNodes;public SkipListNode(K k, V v) {key = k;val = v;nextNodes = new ArrayList>();}// 遍历的时候，如果是往右遍历到的null(next == null), 遍历结束// 头(null), 头节点的null，认为最小// node-> 头，node(null, "")node.isKeyLess(!null)true// node里面的key是否比otherKey小，true，不是falsepublic boolean isKeyLess(K otherKey) {//otherKey == null -> false return otherKey != null && (key == null || key.compareTo(otherKey) < 0);}public boolean isKeyEqual(K otherKey) {return (key == null && otherKey == null)|| (key != null && otherKey != null && key.compareTo(otherKey) == 0);}}public static class SkipListMap, V> {private static final double PROBABILITY = 0.5; // < 0.5 继续做，>=0.5 停private SkipListNode head;private int size;private int maxLevel;public SkipListMap() {head = new SkipListNode(null, null);head.nextNodes.add(null); // 0size = 0;maxLevel = 0;}// 从最高层开始，一路找下去，// 最终，找到第0层的 mostRightLessNodeInTree(K key) {if (key == null) {return null;}int level = maxLevel;SkipListNode cur = head;while (level >= 0) { // 从上层跳下层//curlevel-> level-1cur = mostRightLessNodeInLevel(key, cur, level--);}return cur;}// 在level层里，如何往右移动// 现在来到的节点是cur，来到了cur的level层，在level层上，找到 mostRightLessNodeInLevel(K key, SkipListNode cur, int level) {SkipListNode next = cur.nextNodes.get(level);while (next != null && next.isKeyLess(key)) {cur = next;next = cur.nextNodes.get(level);}return cur;}public boolean containsKey(K key) {if (key == null) {return false;}SkipListNode