数据结构学习:跳表

一、如何理解跳表

在这里插入图片描述

  • 跳表是由链表组成的,如上图,为一个单链表,每个节点存储本身和指向下一节点的指针
  • 即使单链表是有序的,在其中随机查找某个值的时候,还是需要遍历链表,时间复杂度为O(n)
  • 链表追加或给定节点插入或删除的时间复杂度为O(1),但如果在其中插入或删除某个节点,时间复杂度还是O(n)

在这里插入图片描述

如上图所示,这是一张跳表结构

  • 跳表是一张有序链表
  • 查找的时候,比如查找8,可以先找2-10,然后6-10,就可以不用遍历链表,层数设置的好的情况下,可以达到O(logn)的复杂度,类似于二分查找
  • 插入和删除也是,插入和删除的时候也可以通过类似于二分查找找到待插入的前置节点,时间复杂度也是O(logn)

二、跳表的动态更新

  • 假如跳表在增加的过程中,出现某两个层数中出现节点特别多的情况,这就会导致跳表退化为单链表,性能也会下降
  • 红黑树等平衡二叉查找树会利用左旋、右旋的方式来保持平衡;跳表也可以采用随机函数的方式生成层数,具体可看代码实现

三、代码实现

(一)、Java

package LinkedList;

/*
    跳表
    1)存储的是正整数,并且是不重复的
 */

public class SkipList {
    private final static float SKIPLIST_P = 0.5f;
    private final static int MAX_LEVEL = 16; //最大层数

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

    static class Node{
        private int data = -1;
        private Node[] next = new Node[MAX_LEVEL];
        private int level = 0;

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

    public Node find(int value){
        /*
        find方法,从最高层往下一步一步搜索
         */
        Node p = head;
        for (int i = level_count - 1; i >= 0; i++){
            while(p.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
        }

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

    // 理论来讲,一级索引中元素个数应该占原始数据的 50%,二级索引中元素个数占 25%,三级索引12.5% ,一直到最顶层。
    // 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点,都需要调用 randomLevel 生成一个合理的层数。
    // 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数,且 :
    //        50%的概率返回 1
    //        25%的概率返回 2
    //      12.5%的概率返回 3 ...
    private int randomLevel(){
        int level = 1;

        while (Math.random() < SKIPLIST_P && level < MAX_LEVEL){
            level += 1;
        }
        return level;
    }

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

    public void insert(int value){
        /*
        由于是有序链表,每一层都要找到前置节点然后插入
         */
        int level = randomLevel();
        Node newNode = new Node();
        newNode.data = value;
        newNode.level = level;

        Node[] prev = new Node[level]; //前置节点
        for (int i = 0; i < level;i++){
            prev[i] = head;
        }

        Node p = head;
        for (int i = level - 1;i >= 0;i--){
            while (p.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
            prev[i] = p;
        }

        //prev[i]为每层待插入的前置节点,p为最底层待插入的前置节点
        for (int i = 0; i < level;i++){
            newNode.next[i] = prev[i].next[i];
            prev[i].next[i] = newNode;
        }

        if (level_count < level){
            level_count = level;
        }
    }

    public void delete(int value){
        /*
        删除操作同样需要找到每层的前置节点
         */
        Node p = head;
        Node[] prev = new Node[level_count];

        for (int i = level_count - 1; i >= 0; i--){
            while (p.next[i] != null && p.next[i].data < value){
                p = p.next[i];
            }
            prev[i] = p;
        }

        if (p.next[0] != null && p.next[0].data == value){
            for (int i = level_count - 1; i >= 0;i--){
                if (p.next[i] != null && p.next[i].data == value){
                    prev[i].next[i] = prev[i].next[i].next[i];
                }
            }
        }


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

(二)、Scala

package SingelyList

/*
  scala实现:
  MAX_LEVEL:跳表所能达到的最大高度
  skipListLevel:跳表当前的最大高度
  maxlevel:跳表每个节点的高度
 */
import scala.util.Random

class Node(var data:Int,var next:Array[Node],var maxLevel:Int)
class Skip_List(var head:Node,var skipListLevel:Int) {
  def this() = this(new Node(-1,new Array[Node](16),0),1)
  val MAX_LEVEL = 16
  val random = new Random()

  def find(value:Int):Option[Node] = {
    var p = head
    for (i <- skipListLevel - 1 to 0 by -1){
      while (p.next(i) != null && p.next(i).data < value) {
        p = p.next(i)
      }
    }

    if (p.next(0) != null && p.next(0).data == value)
      Some(p.next(0))
    else
      None
  }

  def insert(value:Int):Unit = {
    val level = randomLevel()
    val newnode = new Node(value,new Array[Node](level),level)
    val prev:Array[Node] = new Array[Node](level)
    var p = head
    for (i <- level - 1 to 0 by -1){
      while(p.next(i) != null && p.next(i).data < value){
        p = p.next(i)
      }
      prev(i) = p
    }

    for (i <- 0 to level - 1){
      newnode.next(i) = prev(i).next(i)
      prev(i).next(i) = newnode
    }

    if (level > skipListLevel) {
      skipListLevel = level
    }
  }

  def delete(value:Int):Unit = {
      var p = head
      val prev = new Array[Node](skipListLevel)
      for (i <- skipListLevel - 1 to 0 by -1){
        while (p.next(i) != null && p.next(i).data < value){
          p = p.next(i)
        }
        prev(i) = p
      }

    if (p.next(0) != null && p.next(0).data == value) {
      for (i <- skipListLevel - 1 to 0 by -1){
        if (p.next(i) != null && p.next(i).data == value){
          prev(i).next(i) = prev(i).next(i).next(i)
        }
      }
    }

    while (skipListLevel > 1 && head.next(skipListLevel) == null) {
      skipListLevel -= 1
    }

  }


  def randomLevel():Int = {
    var level = 1
    while (Math.random() < 0.5f && level < MAX_LEVEL){
      level += 1
    }
    level
  }

  def mkString():String = {
    val builder = new StringBuilder
    var p = head
    while (p.next(0)!= null){
      p = p.next(0)
      builder.append(p.data)
    }
    builder.mkString
  }
}

四、跳表的优势

  1. 支持快速的插入、删除、查找操作,性能不逊色于红黑树
  2. 通过改变索引策略,有效平衡执行效率和内存消耗
  3. 更容易代码实现,相比红黑树,跳表还是更容易理解和实现的

版权声明:本文为nzbing原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。