有序表

作用：支持哈希表的所有操作，key是按照有序进行组织的（哈希表是无序的）
时间复杂度：所有的操作都是O(log N)级别的
实现方式：
（1）红黑树
（2）AVL
（3）SBT
（4）跳表（skiplist）
（1），（2），（3）均属性BST（平衡搜索二叉树）

搜索二叉树

搜索二叉树中，一般没有重复项，可以在节点中增加数据项，记录节点数据出现的次数
插入：每次插入节点均从头节点，若插入节点比头节点小往左与其子节点进行比较，若比头节点大往右进行比较，重复比较，直至到空节点，将该节点插入到空节点即可
删除：
（1）叶子节点，搜索该节点，并记录该节点的父节点，修改父节点指针便可实现删除
（2）只有左 / 右节点，搜索该节点，记录其父节点与其子节点，修改父节点指针，使用子节点替换删除节点
（3）左右孩子都有：搜索该节点，使用该节点左树的最右节点 / 右树的最左节点替换删除节点，再将最右 / 最左节点的子节点与其父节点相连即可
缺点：时间复杂度受数据提供顺序的影响
改变树的平衡性：
左旋：头节点向左边倒
（1）p节点向左边倒，右孩子 x，成为头节点
（2）p成为x的左孩子
（3）将x 的左孩子给到p，成为p的右孩子

    public void leftRotate(Node cur) {
      Node right = cur.r;
      cur.r = right.l;
      right.l = cur;
    }

右旋：头节点向左边倒
（1）p节点向右边倒，左孩子 x，成为头节点
（2）p成为x的右孩子
（3）将x 的右孩子给到p，成为p的左孩子

  public Node rightRotate(Node cur) {
      Node left = cur.l;
      cur.l = left.r;
      left.r = cur;
    }

AVL

平衡性要求：左右子树均为AVL且左右子树的高度差的决定值小于等于1
平衡性的检查：
（1）增加节点：从增加节点的位置开始以及往上进行平衡性判断
（2）删除节点：从删除节点的位置开始以及往上进行平衡性判断，特殊的删除左右节点都存在的节点时，从替换该节点的父节点开始检查
平衡性被破会的四种情况：技巧，使三个节点的中间值作为头节点，进行调整
（1）LL：左树的左边破坏平衡，x为中间值，使x作头节点，就是y的右旋

（2）RR：右树的右边破坏平衡，x为中间值，使x作头节点，就是y的左旋
（3）LR：左树的右边破坏平衡，z为中间值，使z作头节点，先x左旋，再y右旋

（4）RL：右树的左边破坏平衡，z为中间值，使z作头节点，先x右旋，再y左旋

  public static class AVLNode<K extends Comparable<K>, V> {
    public K k;
    public V v;
    public AVLNode<K, V> l;
    public AVLNode<K, V> r;
    public int h;
    public AVLNode(K key, V value) {
      k = key;
      v = value;
      h = 1;
    }
  }
  public static class AVLTreeMap<K extends Comparable<K>, V> {
    private AVLNode<K, V> root;
    private int size;
    public AVLTreeMap() {
      root = null;
      size = 0;
    }
    private AVLNode<K, V> rightRotate(AVLNode<K, V> cur) {
      AVLNode<K, V> 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<K, V> leftRotate(AVLNode<K, V> cur) {
      AVLNode<K, V> 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<K, V> maintain(AVLNode<K, V> 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<K, V> findLastIndex(K key) {
      AVLNode<K, V> pre = root;
      AVLNode<K, V> 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<K, V> findLastNoSmallIndex(K key) {
      AVLNode<K, V> ans = null;
      AVLNode<K, V> 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<K, V> findLastNoBigIndex(K key) {
      AVLNode<K, V> ans = null;
      AVLNode<K, V> 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<K, V> add(AVLNode<K, V> cur, K key, V value) {
      if (cur == null) {
        return new AVLNode<K, V>(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<K, V> delete(AVLNode<K, V> 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<K, V> 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;
    }
    public boolean containsKey(K key) {
      if (key == null) {
        return false;
      }
      AVLNode<K, V> 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<K, V> 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<K, V> 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<K, V> cur = root;
      while (cur.l != null) {
        cur = cur.l;
      }
      return cur.k;
    }
    public K lastKey() {
      if (root == null) {
        return null;
      }
      AVLNode<K, V> cur = root;
      while (cur.r != null) {
        cur = cur.r;
      }
      return cur.k;
    }
    public K floorKey(K key) {
      if (key == null) {
        return null;
      }
      AVLNode<K, V> lastNoBigNode = findLastNoBigIndex(key);
      return lastNoBigNode == null ? null : lastNoBigNode.k;
    }
    public K ceilingKey(K key) {
      if (key == null) {
        return null;
      }
      AVLNode<K, V> lastNoSmallNode = findLastNoSmallIndex(key);
      return lastNoSmallNode == null ? null : lastNoSmallNode.k;
    }
  }

SBT（SizeBalancedTree）

平衡性要求：每颗子树的大小，不小于其兄弟子树的大小，即每颗叔叔树的大小，不小于其任何侄子树的大小
平衡性的检查：
（1）增加节点：从增加节点的位置开始以及往上进行平衡性判断
（2）删除节点：从删除节点的位置开始以及往上进行平衡性判断，特殊的删除左右节点都存在的节点时，从替换该节点的父节点开始检查
平衡性被破会的四种情况：
（1）LL：左树的左边破坏平衡，maintain为递归函数，将子树变化过的节点再次进行m调用

（2）RR：右树的右边破坏平衡，左旋，再将子树变化的调用m函数
（3）LR：左树的右边破坏平衡，先左，再右旋，再将子树变化的调用m函数

（4）RL：右树的左边破坏平衡，先右，再左旋，再将子树变化的调用m函数

  public static class SBTNode<K extends Comparable<K>, V> {
    public K key;
    public V value;
    public SBTNode<K, V> l;
    public SBTNode<K, V> r;
    public int size; // 不同的key的数量
    public SBTNode(K key, V value) {
      this.key = key;
      this.value = value;
      size = 1;
    }
  }
  public static class SizeBalancedTreeMap<K extends Comparable<K>, V> {
    private SBTNode<K, V> root;
    private SBTNode<K, V> rightRotate(SBTNode<K, V> cur) {
      SBTNode<K, V> 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<K, V> leftRotate(SBTNode<K, V> cur) {
      SBTNode<K, V> 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<K, V> maintain(SBTNode<K, V> 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<K, V> findLastIndex(K key) {
      SBTNode<K, V> pre = root;
      SBTNode<K, V> 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<K, V> findLastNoSmallIndex(K key) {
      SBTNode<K, V> ans = null;
      SBTNode<K, V> 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<K, V> findLastNoBigIndex(K key) {
      SBTNode<K, V> ans = null;
      SBTNode<K, V> 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<K, V> add(SBTNode<K, V> cur, K key, V value) {
      if (cur == null) {
        return new SBTNode<K, V>(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<K, V> delete(SBTNode<K, V> 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 { // 当前要删掉cur
        if (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<K, V> pre = null;
          SBTNode<K, V> 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<K, V> getIndex(SBTNode<K, V> 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<K, V> lastNode = findLastIndex(key);
      return lastNode != null && key.compareTo(lastNode.key) == 0 ? true : false;
    }
    // （key，value） put -> 有序表 新增、改value
    public void put(K key, V value) {
      if (key == null) {
        throw new RuntimeException("invalid parameter.");
      }
      SBTNode<K, V> lastNode = findLastIndex(key);
      if (lastNode != null && key.compareTo(lastNode.key) == 0) {
        lastNode.value = 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<K, V> 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<K, V> cur = root;
      while (cur.l != null) {
        cur = cur.l;
      }
      return cur.key;
    }
    public K lastKey() {
      if (root == null) {
        return null;
      }
      SBTNode<K, V> 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<K, V> lastNoBigNode = findLastNoBigIndex(key);
      return lastNoBigNode == null ? null : lastNoBigNode.key;
    }
    public K ceilingKey(K key) {
      if (key == null) {
        throw new RuntimeException("invalid parameter.");
      }
      SBTNode<K, V> lastNoSmallNode = findLastNoSmallIndex(key);
      return lastNoSmallNode == null ? null : lastNoSmallNode.key;
    }
  }

红黑树

概述：
（1）每个节点不是红就是黑
（2）叶节点：不是没有左右孩子的节点，而是空节点
（3）头和叶节点，必须为黑
（4）任何两个红节点都不能相邻
（5）任意节点出发，到每一个叶节点的所有路径，经过的黑节点个数相同
效果：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的

AVL，SBT，红黑树对比

共性
（1）都是搜索二叉树
（2）插入、删除、查询（一切查询）都是基于搜索二叉树的
（3）使用调整的基本动作都只有左旋、右旋
（4）插入、删除时，从最底层被影响到的节点开始，对往上路径的节点做平衡性检查
（5）因为只对一条向上路径的每个节点做O(1)的检查和调整，所以可以做到O(logN)
不同点
（1）平衡性的约束不同：AVL树最严格、SBT树稍宽松、红黑树最宽松（平衡性：左右子树的规模大致相同）
（2）因为平衡性的约束不同，所以在插入，删除平衡性变化的调整上有常数时间的差别

跳表（skiplist）

概述：
（1）开始有一个默认节点（链表，其key是最小的） head
（2）每次出发均从head出发
（3）添加节点，该节点随机产生一个高度，若头结点的高度比其小，头结点扩充高度（只有头结点可以扩充，要保证头结点的高度最高的）
（4）将头结点中的指针向连接节点对应层连接

如图：就是一个含10个数据跳表，1产生的随机高度是4，2产生的随机高度是1……
基本操作

（1）查找：通过head找到最高层，直接通过最高层对应的元素进行比较，若最高层不行就跳到下一层，因为整体是有序的所以可以减少节点的查找
例：查找40，最高层开始是20，小于40，于是可以跳过2，10，15，下一次直接可以100，大于，从20开始到下一层50，大于，再下一层找到40
（2）插入：先生成插入元素对应的层数，通过查找，确定插入位置，使用插入层改变节点的连接
例：插入70，对应2层

（3）删除：先查找，直接将待删除节点前的节点忽略该节点与后面节点连接即可
复杂度：
（1）用空间来换时间
（2）如果一个链表有 n 个结点，如果每两个结点抽取出一个结点建立索引的话，那么第一级索引的结点数大约就是 n/2，第二级索引的结点数大约为 n/4，以此类推第 m 级索引的节点数大约为 n/(2^m)，我们可以看出来这是一个等比数列
（3）所以跳表的空间复杂度为 O(n)
（4）跳表的高度计算类似与满二叉树：整个跳表的高度就是 log(n)，跳表的查询的时间复杂度为 O(logn）

  public static class SkipListNode<K extends Comparable<K>, V> {
    public K key;
    public V val;
    public ArrayList<SkipListNode<K, V>> nextNodes;
    public SkipListNode(K k, V v) {
      key = k;
      val = v;
      nextNodes = new ArrayList<SkipListNode<K, V>>();
    }
    // 遍历的时候，如果是往右遍历到的null(next == null), 遍历结束
    // 头(null), 头节点的null，认为最小
    // node  -> 头，node(null, "")  node.isKeyLess(!null)  true
    // node里面的key是否比otherKey小，true，不是false
    public 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<K extends Comparable<K>, V> {
    private static final double PROBABILITY = 0.5; // < 0.5 继续做，>=0.5 停
    private SkipListNode<K, V> head;
    private int size;
    private int maxLevel;
    public SkipListMap() {
      head = new SkipListNode<K, V>(null, null);
      head.nextNodes.add(null); // 0
      size = 0;
      maxLevel = 0;
    }
    // 从最高层开始，一路找下去，
    // 最终，找到第0层的<key的最右的节点
    private SkipListNode<K, V> mostRightLessNodeInTree(K key) {
      if (key == null) {
        return null;
      }
      int level = maxLevel;
      SkipListNode<K, V> cur = head;
      while (level >= 0) { // 从上层跳下层
        //  cur  level  -> level-1
        cur = mostRightLessNodeInLevel(key, cur, level--);
      }
      return cur;
    }
    // 在level层里，如何往右移动
    // 现在来到的节点是cur，来到了cur的level层，在level层上，找到<key最后一个节点并返回
    private SkipListNode<K, V> mostRightLessNodeInLevel(K key, 
        SkipListNode<K, V> cur, 
        int level) {
      SkipListNode<K, V> 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<K, V> less = mostRightLessNodeInTree(key);
      SkipListNode<K, V> next = less.nextNodes.get(0);
      return next != null && next.isKeyEqual(key);
    }
    // 新增、改value
    public void put(K key, V value) {
      if (key == null) {
        return;
      }
      // 0层上，最右一个，< key 的Node -> >key
      SkipListNode<K, V> less = mostRightLessNodeInTree(key);
      SkipListNode<K, V> find = less.nextNodes.get(0);
      if (find != null && find.isKeyEqual(key)) {
        find.val = value;
      } else { // find == null   8   7   9
        size++;
        int newNodeLevel = 0;
        while (Math.random() < PROBABILITY) {
          newNodeLevel++;
        }
        // newNodeLevel
        while (newNodeLevel > maxLevel) {
          head.nextNodes.add(null);
          maxLevel++;
        }
        SkipListNode<K, V> newNode = new SkipListNode<K, V>(key, value);
        for (int i = 0; i <= newNodeLevel; i++) {
          newNode.nextNodes.add(null);
        }
        int level = maxLevel;
        SkipListNode<K, V> pre = head;
        while (level >= 0) {
          // level 层中，找到最右的 < key 的节点
          pre = mostRightLessNodeInLevel(key, pre, level);
          if (level <= newNodeLevel) {
            newNode.nextNodes.set(level, pre.nextNodes.get(level));
            pre.nextNodes.set(level, newNode);
          }
          level--;
        }
      }
    }
    public V get(K key) {
      if (key == null) {
        return null;
      }
      SkipListNode<K, V> less = mostRightLessNodeInTree(key);
      SkipListNode<K, V> next = less.nextNodes.get(0);
      return next != null && next.isKeyEqual(key) ? next.val : null;
    }
    public void remove(K key) {
      if (containsKey(key)) {
        size--;
        int level = maxLevel;
        SkipListNode<K, V> pre = head;
        while (level >= 0) {
          pre = mostRightLessNodeInLevel(key, pre, level);
          SkipListNode<K, V> next = pre.nextNodes.get(level);
          // 1）在这一层中，pre下一个就是key
          // 2）在这一层中，pre的下一个key是>要删除key
          if (next != null && next.isKeyEqual(key)) {
            // free delete node memory -> C++
            // level : pre -> next(key) -> ...
            pre.nextNodes.set(level, next.nextNodes.get(level));
          }
          // 在level层只有一个节点了，就是默认节点head
          if (level != 0 && pre == head && pre.nextNodes.get(level) == null) {
            head.nextNodes.remove(level);
            maxLevel--;
          }
          level--;
        }
      }
    }
    public K firstKey() {
      return head.nextNodes.get(0) != null ? head.nextNodes.get(0).key : null;
    }
    public K lastKey() {
      int level = maxLevel;
      SkipListNode<K, V> cur = head;
      while (level >= 0) {
        SkipListNode<K, V> next = cur.nextNodes.get(level);
        while (next != null) {
          cur = next;
          next = cur.nextNodes.get(level);
        }
        level--;
      }
      return cur.key;
    }
    public K ceilingKey(K key) {
      if (key == null) {
        return null;
      }
      SkipListNode<K, V> less = mostRightLessNodeInTree(key);
      SkipListNode<K, V> next = less.nextNodes.get(0);
      return next != null ? next.key : null;
    }
    public K floorKey(K key) {
      if (key == null) {
        return null;
      }
      SkipListNode<K, V> less = mostRightLessNodeInTree(key);
      SkipListNode<K, V> next = less.nextNodes.get(0);
      return next != null && next.isKeyEqual(key) ? next.key : less.key;
    }
    public int size() {
      return size;
    }
  }

算法设计与分析有序表

有序表

有序表

搜索二叉树

AVL

SBT（SizeBalancedTree）

红黑树

AVL，SBT，红黑树对比

跳表（skiplist）

热门文章

最新文章

相关课程

相关电子书

相关实验场景

算法设计与分析 有序表

有序表

有序表

搜索二叉树

AVL

SBT（SizeBalancedTree）

红黑树

AVL，SBT，红黑树对比

跳表（skiplist）

热门文章

最新文章

相关课程

相关电子书

相关实验场景

算法设计与分析有序表