[数据结构与算法]初识数据结构-跳表

背景

对于有序的数组，查找一个数可以用二分查找，时间复杂度为O(logn)。

而对于一个有序链表，因为相邻元素存储的位置并不相邻，即使元素有序，也不能像数组一样使用二分去查找元素。 只能从头开始遍历，时间复杂度为O(n)。

优化

我们可以为链表建一层索引，这样查找就会更快一些。就像书的目录一样，假如我们要翻开书本的第五章，首先会去目录找到第五章对应的页数，而不是一页一页去找。

同样的，如果我们在链表上面建一层索引，搜索会不会变快呢？

?这样，原本需要7次的查询缩减至了4次，如果再加一层索引，情况会不会更好呢？

?结果是又减少了一次查询。

在这个例子中，由于原始链表的结点数量较少，仅仅需要2层索引。如果链表的结点数量非常多，我们就可以抽出更多的索引层级，每一层索引的结点数量都是低层索引的一半。

跳表

基于上述链表改造的数据结构就叫跳表。它允许快速查询、插入和删除一个有序的数据链表，而且平均查找和插入时间复杂度都是O（logn）。

快速查询是通过维护一个多层次的链表，每一层索引结点数量都是低层的一半。这样可以在最上最稀疏的层次进行搜索，找到查找元素在该层两个相邻元素中间，跳至下一层，直至找到元素为止。

跳表的效率

假设链表长度为n，每两个节点抽取出一个节点建立索引，第一层索引有n/2个节点，第二层（n/2）/2个节点，第三层（（n/2）/2）/2个节点，第m层n/（2^m）个节点。

假设一共有m级索引，第m级索引节点有两个，则n/(2^m) =2，即跳表的高度为log(n)-1，加上原始链表的话，整个跳表的高度就为log(n)。每一层都需要遍历k个结点的话，最终的时间复杂度就为O(k*log(n))。

但事实上，k是一个常数，且等于2。为什么呢？

跳表查找不能像二分查找那样从中间开始，把区间划分为大于和小于查找值的两个区间。 跳表的查找只能从一个方向开始，但是类似的，它也把链表划分成了两个区间。当前节点A，和下一个节点B组成一个区间AB，B节点跟末尾节点C组成第二个区间BC，所以只要确认查找的值在AB区间还是BC区间。因为就两个区间，只要比较A和B的值，确认是否在AB区间即可。

?跳表是一种空间换时间的做法，如果n个节点的链表每两个节点抽取一个建立节点，一级n/2个，二级n/4个。。。最后一级2。等比数列求和，空间复杂度为O(n)。其实可以每3、5个节点抽取一个索引，这样所占的空间也就少了。

跳表的插入和删除

1.插入

假设要插入一个30，首先找到它的前置节点（仅小于待插入节点）。

?插入完成之后需要对索引节点也做调整，因为随着原始链表的新节点越来越多，索引会渐渐变得不够用。我们要让新插入的节点有机会晋升为索引节点，晋升成功的概率是50%（两个节点抽取一个节点当索引节点），也可以是25%（四个节点抽取一个）。可以看出跳表使用的是概率平衡，而不是强平衡。

如果晋升成功，仍然可以继续向上一层索引晋升。如果失败了，插入操作就结束了。

?还有一种特殊情况，节点一直晋升，超过了最高索引范围，这时候，我们需要再增加一层索引。

2.删除

思路跟插入差不多，首先按跳表的方式找到待删除的节点。然后顺藤摸瓜，删除对应的索引。如果某一层只有一个节点，而且该元素需要被删除，那就直接删除了这一层。

如果把刚才例子中的30重新删除，情况是这样的。

Java中跳表的实现

在程序实现中，跳表使用双向链表，不论上下左右节点，都有两个指针指向彼此。每一层的首位有一个无限小的空节点，末尾有一个无限大的空节点，这样做是为了方便代码的实现。

?定义数据结构

public class SkipList {
	
	// 晋升的概率
	private static final double PROMOTE_RATE = 0.5;
	
	private Node head, tail;
	
	// 记录已经有几层索引了
	private int levelCount = 0;
	
	public SkipList() {
		head = new Node(Integer.MIN_VALUE);
		tail = new Node(Integer.MAX_VALUE);
		head.right = tail;
		tail.left = head;
	}
	
	private class Node {
		private int data;
		private Node up, down, left, right;
		
		public Node(int data) {
			this.data = data;
		}
	}

}

插入操作

/**
	 *  找到前置节点
	 * @param data
	 * @return
	 */
	private Node findPreNode(int data) {
		Node node = head;
		while(true) {
			// 不要超过边界
			// 当前节点的右节点大于data 那么当前节点就是前置节点
			while(node.right.data != Integer.MAX_VALUE && node.right.data <= data) {
				node = node.right;
			}
			if (node.down == null) {
				break;
			}
			node = node.down;
		}
		return node;
	}
	
	/**
	 *  追加节点
	 * @param preNode
	 * @param newNode
	 */
	private void appendNode(Node preNode, Node newNode) {
		newNode.left = preNode;
		newNode.right = preNode.right;
		
		preNode.right.left = newNode;
		preNode.right = newNode;
	}
	
	/**
	 *  增加一层
	 */
	private void addLevel() {
		this.levelCount++;
		
		Node p1 = new Node(Integer.MIN_VALUE);
		Node p2 = new Node(Integer.MAX_VALUE);
		
		p1.right = p2;
		p2.left = p1;
		
		p1.down = head;
		p2.down = tail;
		
		head.up = p1;
		tail.up = p2;
		
		head = p1;
		tail = p2;
	}
	
	/**
	 *  插入节点
	 * @param data
	 */
	public void insert(int data) {
		Node preNode = findPreNode(data);
		
		Node newNode = new Node(data);
		appendNode(preNode, newNode);
		
		// 晋升代码
		int currentLevel = 0;
		Random random = new Random();
		boolean isAddLevel = false;
		
		while(random.nextDouble() < this.PROMOTE_RATE) {
			// 限制只能新增一层
			if (isAddLevel) {
				break;
			}
			// 当前层已经是最高层，新增一层
			if (currentLevel == this.levelCount) {
				addLevel();
				isAddLevel = true;
			}
			// 针对新增一层的情况 
			// preNode已经没有上层节点了  需要移动到该层的头节点
			while(preNode.up == null) {
				preNode = preNode.left;
			}
			preNode = preNode.up;
			// 把晋升的节点插入到上一层
			Node upperNode = new Node(data);
			appendNode(preNode, upperNode);
			upperNode.down = newNode;
			newNode.up = upperNode;
			currentLevel++;
		}
	}

查找操作

public Node search(int data) {
		Node p = findPreNode(data);
		if (p.data == data) {
			System.out.println("找到了： " + data);
			return p;
		}
		System.out.println("没有找到： " + data);
		return null;
	}

删除操作

/**
	 *  删除节点
	 * @param data
	 * @return
	 */
    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;
            //如果不是最底层，且只有无穷小和无穷大结点，删除该层
            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;
    }

    /**
     *  删除一层
     * @param leftNode
     */
    private void removeLevel(Node leftNode){
        head = head.down;
        tail = tail.down;
        head.up = null;
        tail.up = null;
        this.levelCount--;
    }

完整代码

public class SkipList {
	
	// 晋升的概率
	private static final double PROMOTE_RATE = 0.5;
	
	private Node head, tail;
	
	// 记录已经有几层索引了
	private int levelCount = 0;
	
	public SkipList() {
		head = new Node(Integer.MIN_VALUE);
		tail = new Node(Integer.MAX_VALUE);
		head.right = tail;
		tail.left = head;
	}
	
	/**
	 *  找到前置节点
	 * @param data
	 * @return
	 */
	private Node findPreNode(int data) {
		Node node = head;
		while(true) {
			// 不要超过边界
			// 当前节点的右节点大于data 那么当前节点就是前置节点
			while(node.right.data != Integer.MAX_VALUE && node.right.data <= data) {
				node = node.right;
			}
			if (node.down == null) {
				break;
			}
			node = node.down;
		}
		return node;
	}
	
	/**
	 *  追加节点
	 * @param preNode
	 * @param newNode
	 */
	private void appendNode(Node preNode, Node newNode) {
		newNode.left = preNode;
		newNode.right = preNode.right;
		
		preNode.right.left = newNode;
		preNode.right = newNode;
	}
	
	/**
	 *  增加一层
	 */
	private void addLevel() {
		this.levelCount++;
		
		Node p1 = new Node(Integer.MIN_VALUE);
		Node p2 = new Node(Integer.MAX_VALUE);
		
		p1.right = p2;
		p2.left = p1;
		
		p1.down = head;
		p2.down = tail;
		
		head.up = p1;
		tail.up = p2;
		
		head = p1;
		tail = p2;
	}
	
	/**
	 *  插入节点
	 * @param data
	 */
	public void insert(int data) {
		Node preNode = findPreNode(data);
		
		Node newNode = new Node(data);
		appendNode(preNode, newNode);
		
		// 晋升代码
		int currentLevel = 0;
		Random random = new Random();
		boolean isAddLevel = false;
		
		while(random.nextDouble() < this.PROMOTE_RATE) {
			// 限制只能新增一层
			if (isAddLevel) {
				break;
			}
			// 当前层已经是最高层，新增一层
			if (currentLevel == this.levelCount) {
				addLevel();
				isAddLevel = true;
			}
			// 针对新增一层的情况 
			// preNode已经没有上层节点了  需要移动到该层的头节点
			while(preNode.up == null) {
				preNode = preNode.left;
			}
			preNode = preNode.up;
			// 把晋升的节点插入到上一层
			Node upperNode = new Node(data);
			appendNode(preNode, upperNode);
			upperNode.down = newNode;
			newNode.up = upperNode;
			currentLevel++;
		}
	}
	
	public Node search(int data) {
		Node p = findPreNode(data);
		if (p.data == data) {
			System.out.println("找到了： " + data);
			return p;
		}
		System.out.println("没有找到： " + data);
		return null;
	}
	
	/**
	 *  删除节点
	 * @param data
	 * @return
	 */
    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;
            //如果不是最底层，且只有无穷小和无穷大结点，删除该层
            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;
    }

    /**
     *  删除一层
     * @param leftNode
     */
    private void removeLevel(Node leftNode){
        head = head.down;
        tail = tail.down;
        head.up = null;
        tail.up = null;
        this.levelCount--;
    }

	private class Node {
		private int data;
		private Node up, down, left, right;
		
		public Node(int data) {
			this.data = data;
		}
	}
	
	//输出底层链表
    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();
    }

    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);
    }

}