package skiplist;

import java.util.Random;

/**
 * 跳表的一种实现方法。
 * 跳表中存储的是正整数，并且存储的是不重复的。
 *
 * Author：ZHENG
 */
public class SkipList {

  private static final int MAX_LEVEL = 16;

  private int levelCount = 1;

  private Node head = new Node();  // 带头链表

  private Random r = new Random();

  public Node find(int value) {
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
    }

    if (p.forwards[0] != null && p.forwards[0].data == value) {
      return p.forwards[0];
    } else {
      return null;
    }
  }

  public void insert(int value) {
    int level = randomLevel();
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    Node update[] = new Node[level];
    for (int i = 0; i < level; ++i) {
      update[i] = head;
    }

    // record every level largest value which smaller than insert value in update[]
    Node p = head;
    for (int i = level - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;// use update save node in search path
    }

    // in search path node next node become new node forwords(next)
    for (int i = 0; i < level; ++i) {
      newNode.forwards[i] = update[i].forwards[i];
      update[i].forwards[i] = newNode;
    }

    // update node hight
    if (levelCount < level) levelCount = level;
  }

  public void delete(int value) {
    Node[] update = new Node[levelCount];
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;
    }

    if (p.forwards[0] != null && p.forwards[0].data == value) {
      for (int i = levelCount - 1; i >= 0; --i) {
        if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
          update[i].forwards[i] = update[i].forwards[i].forwards[i];
        }
      }
    }

    while (levelCount>1&&head.forwards[levelCount]==null){
      levelCount--;
    }

  }

  // 随机 level 次，如果是奇数层数 +1，防止伪随机
 private int randomLevel() {
    int level = 1;
    for (int i = 1; i < MAX_LEVEL; ++i) {
      if (r.nextInt() % 2 == 1) {
        level++;
      }
    }

    return level;
  }

  public void printAll() {
    Node p = head;
    while (p.forwards[0] != null) {
      System.out.print(p.forwards[0] + " ");
      p = p.forwards[0];
    }
    System.out.println();
  }

  public class Node {
    private int data = -1;
    private Node forwards[] = new Node[MAX_LEVEL];
    private int maxLevel = 0;

    @Override
    public String toString() {
      StringBuilder builder = new StringBuilder();
      builder.append("{ data: ");
      builder.append(data);
      builder.append("; levels: ");
      builder.append(maxLevel);
      builder.append(" }");

      return builder.toString();
    }
  }

}

@@ -16,33 +16,8 @@
 t;%0A%0A
-import java.util.Random;%0A
 %0A/**
@@ -105,16 +105,64 @@
 List %7B%0A%0A
+  private static final float SKIPLIST_P = 0.5f;%0A
   privat
@@ -228,16 +228,16 @@
 t = 1;%0A%0A
+
   privat
@@ -276,44 +276,8 @@
 %E9%93%BE%E8%A1%A8%0A%0A
-  private Random r = new Random();%0A%0A
   pu
@@ -2138,34 +2138,126 @@
 / %E9%9A%8F%E6%9C%BA
- level %E6%AC%A1%EF%BC%8C%E5%A6%82%E6%9E%9C%E6%98%AF%E5%A5%87%E6%95%B0%E5%B1%82%E6%95%B0 +1%EF%BC%8C%E9%98%B2%E6%AD%A2%E4%BC%AA%E9%9A%8F%E6%9C%BA%0A
+%E5%87%BD%E6%95%B0%E6%9C%9F%E6%9C%9B%E7%9A%84%E7%9B%AE%E6%A0%87%E6%98%AF 50%25 %E7%9A%84 Level1%EF%BC%8C25%25 %E7%9A%84 Level2%EF%BC%8C12.5%25 %E7%9A%84 Level3%0A  // %E4%B8%80%E7%9B%B4%E5%88%B0%E6%9C%80%E9%A1%B6%E5%B1%82%EF%BC%8C%E5%9B%A0%E4%B8%BA%E8%BF%99%E9%87%8C%E6%AF%8F%E4%B8%80%E5%B1%82%E7%9A%84%E6%99%8B%E5%8D%87%E6%A6%82%E7%8E%87%E6%98%AF SKIPLIST_P = 50%25%EF%BC%8C%E5%8F%AF%E4%BB%A5%E9%80%9A%E8%BF%87 SKIPLIST_P %E6%9D%A5%E4%BF%AE%E6%94%B9%E6%99%8B%E5%8D%87%E6%A6%82%E7%8E%87%0A 
  pri
@@ -2304,115 +2304,86 @@
  1;%0A
+%0A
     
-for (int i = 1; i %3C MAX_LEVEL; ++i) %7B%0A      if (r.nextInt() %25 2 == 1) %7B%0A        level++;%0A      %7D%0A    %7D%0A
+while (Math.random() %3C SKIPLIST_P && level %3C MAX_LEVEL)%0A      level += 1;
 %0A   

修改 randomLevel 的生成算法