【算法基礎(chǔ)】漫畫：什么是 “跳表” ？

public?class?SkipList{

????//結(jié)點(diǎn)“晉升”的概率
????private?static?final?double?PROMOTE_RATE?=?0.5;
????private?Node?head,tail;
????private?int?maxLevel;

????public?SkipList()?{
????????head?=?new?Node(Integer.MIN_VALUE);
????????tail?=?new?Node(Integer.MAX_VALUE);
????????head.right?=?tail;
????????tail.left?=?head;
????}

????//查找結(jié)點(diǎn)
????public?Node?search(int?data){
????????Node?p=?findNode(data);
????????if(p.data?==?data){
????????????System.out.println("找到結(jié)點(diǎn)："?+?data);
????????????return?p;
????????}
????????System.out.println("未找到結(jié)點(diǎn)："?+?data);
????????return?null;
????}

????//找到值對(duì)應(yīng)的前置結(jié)點(diǎn)
????private?Node?findNode(int?data){
????????Node?node?=?head;
????????while(true){
????????????while?(node.right.data!=Integer.MAX_VALUE?&&?node.right.data<=data)?{
????????????????node?=?node.right;
????????????}
????????????if?(node.down?==?null)?{
????????????????break;
????????????}
????????????node?=?node.down;
????????}
????????return?node;
????}

????//插入結(jié)點(diǎn)
????public?void?insert(int?data){
????????Node?preNode=?findNode(data);
????????//如果data相同，直接返回
????????if?(preNode.data?==?data)?{
????????????return;
????????}
????????Node?node=new?Node(data);
????????appendNode(preNode,?node);
????????int?currentLevel=0;
????????//隨機(jī)決定結(jié)點(diǎn)是否“晉升”
????????Random?random?=?new?Random();
????????while?(random.nextDouble()?????????????//如果當(dāng)前層已經(jīng)是最高層，需要增加一層
????????????if?(currentLevel?==?maxLevel)?{
????????????????addLevel();
????????????}
????????????//找到上一層的前置節(jié)點(diǎn)
????????????while?(preNode.up==null)?{
????????????????preNode=preNode.left;
????????????}
????????????preNode=preNode.up;
????????????//把“晉升”的新結(jié)點(diǎn)插入到上一層
????????????Node?upperNode?=?new?Node(data);
????????????appendNode(preNode,?upperNode);
????????????upperNode.down?=?node;
????????????node.up?=?upperNode;
????????????node?=?upperNode;
????????????currentLevel++;
????????}
????}

????//在前置結(jié)點(diǎn)后面添加新結(jié)點(diǎn)
????private?void?appendNode(Node?preNode,?Node?newNode){
????????newNode.left=preNode;
????????newNode.right=preNode.right;
????????preNode.right.left=newNode;
????????preNode.right=newNode;
????}

????//增加一層
????private?void?addLevel(){
????????maxLevel++;
????????Node?p1=new?Node(Integer.MIN_VALUE);
????????Node?p2=new?Node(Integer.MAX_VALUE);
????????p1.right=p2;
????????p2.left=p1;
????????p1.down=head;
????????head.up=p1;
????????p2.down=tail;
????????tail.up=p2;
????????head=p1;
????????tail=p2;
????}

????//刪除結(jié)點(diǎn)
????public?boolean?remove(int?data){
????????Node?removedNode?=?search(data);
????????if(removedNode?==?null){
????????????return?false;
????????}

????????int?currentLevel=0;
????????while?(removedNode?!=?null){
????????????removedNode.right.left?=?removedNode.left;
????????????removedNode.left.right?=?removedNode.right;
????????????//如果不是最底層，且只有無(wú)窮小和無(wú)窮大結(jié)點(diǎn)，刪除該層
????????????if(currentLevel?!=?0?&&?removedNode.left.data?==?Integer.MIN_VALUE?&&?removedNode.right.data?==?Integer.MAX_VALUE){
????????????????removeLevel(removedNode.left);
????????????}else?{
????????????????currentLevel?++;
????????????}
????????????removedNode?=?removedNode.up;
????????}

????????return?true;
????}

????//刪除一層
????private?void?removeLevel(Node?leftNode){
????????Node?rightNode?=?leftNode.right;
????????//如果刪除層是最高層
????????if(leftNode.up?==?null){
????????????leftNode.down.up?=?null;
????????????rightNode.down.up?=?null;
????????}else?{
????????????leftNode.up.down?=?leftNode.down;
????????????leftNode.down.up?=?leftNode.up;
????????????rightNode.up.down?=?rightNode.down;
????????????rightNode.down.up?=?rightNode.up;
????????}
????????maxLevel?--;
????}

????//輸出底層鏈表
????public?void?printList()?{
????????Node?node=head;
????????while?(node.down?!=?null)?{
????????????node?=?node.down;
????????}
????????while?(node.right.data?!=?Integer.MAX_VALUE)?{
????????????System.out.print(node.right.data?+?"?");
????????????node?=?node.right;
????????}
????????System.out.println();
????}

????//鏈表結(jié)點(diǎn)類
????public?class?Node?{
????????public?int?data;
????????//跳表結(jié)點(diǎn)的前后和上下都有指針
????????public?Node?up,?down,?left,?right;

????????public?Node(int?data)?{
????????????this.data?=?data;
????????}
????}

????public?static?void?main(String[]?args)?{
????????SkipList?list=new?SkipList();
????????list.insert(50);
????????list.insert(15);
????????list.insert(13);
????????list.insert(20);
????????list.insert(100);
????????list.insert(75);
????????list.insert(99);
????????list.insert(76);
????????list.insert(83);
????????list.insert(65);
????????list.printList();
????????list.search(50);
????????list.remove(50);
????????list.search(50);
????}
}