左神算法笔记——跳表

2020-04-13  本文已影响0人  yaco

我们知道二叉搜索算法能够高效的查询数据,但是需要一块连续的内存,而且增删改效率很低。
跳表,是基于链表实现的一种类似“二分”的算法。它可以快速的实现增,删,改,查操作。
我们先来看一下单向链表如何实现查找

image.png

当我们要在该单链表中查找某个数据的时候需要的时间复杂度为O(n).
怎么提高查询效率呢?如果我们给该单链表加一级索引,将会改善查询效率。


image.png

如图所示,当我们每隔一个节点就提取出来一个元素到上一层,把这一层称作索引,其中的down指针指向原始链表。
当我们查找元素16的时候,单链表需要比较10次,而加过索引的两级链表只需要比较7次。当数据量增大到一定程度的时候,效率将会有显著的提升。
如果我们再加多几级索引的话,效率将会进一步提升。这种链表加多级索引的结构,就叫做跳表。


image.png
跳表的查询时间复杂度可以达到O(logn)

代码设计

    // 跳表的节点类
    public static class SkipListNode {
        public Integer value;                            // 属性一:该节点代表的值
        public ArrayList<SkipListNode> nextNodes;        // 属性二:该节点所的node列表

        public SkipListNode(Integer value) {             // 构造器
            this.value = value;
            nextNodes = new ArrayList<SkipListNode>();
        }
    }

    public static class SkipListIterator implements Iterator<Integer> {
        SkipList list;
        SkipListNode current;

        public SkipListIterator(SkipList list) {
            this.list = list;
            this.current = list.getHead();
        }

        public boolean hasNext() {
            return current.nextNodes.get(0) != null;
        }

        public Integer next() {
            current = current.nextNodes.get(0);
            return current.value;
        }
    }

    // 跳表类
    public static class SkipList {
        private SkipListNode head;         // 填表的头节点
        private int maxLevel;              // 调表的最大高度
        private int size;                  // 当前容量
        private static final double PROBABILITY = 0.5;

        // 构造器
        public SkipList() {
            size = 0;
            maxLevel = 0;
            head = new SkipListNode(null);
            head.nextNodes.add(null);
        }

        // 获取头节点
        public SkipListNode getHead() {
            return head;
        }

        // 向跳表中添加元素
        public void add(Integer newValue) {
            // 如果当前跳表里面不包含这个newValue
            if (!contains(newValue)) {
                size++;   //向跳表里面添加节点,size增长
                int level = 0;   // 随机出层数
                while (Math.random() < PROBABILITY) {
                    level++;
                }
                // 如果随机出来的level层数大于最大层数maxLevel,则maxLevel增加
                while (level > maxLevel) {
                    head.nextNodes.add(null);
                    maxLevel++;
                }
                // 创建该newValue对应的跳表
                SkipListNode newNode = new SkipListNode(newValue);
                SkipListNode current = head;
                do {
                    current = findNext(newValue, current, level); // 针对每一层,找到第一个比newValue小的地方
                    newNode.nextNodes.add(0, current.nextNodes.get(level));  // 将当前跳表接单的第一个加上current的下一个节点,以这种方式将跳表全部连接起来
                    current.nextNodes.set(level, newNode);   // 将current的当前层节点放上newValue的节点
                } while (level-- > 0);
            }
            // 如果跳表中存在此value,不进行任何操作
        }

        public void delete(Integer deleteValue) {
            if (contains(deleteValue)) {
                SkipListNode deleteNode = find(deleteValue);
                size--;
                int level = maxLevel;
                SkipListNode current = head;
                do {
                    current = findNext(deleteNode.value, current, level);
                    if (deleteNode.nextNodes.size() > level) {
                        // 删除操作直接取消连接就可以了
                        current.nextNodes.set(level, deleteNode.nextNodes.get(level));
                    }
                } while (level-- > 0);
            }
        }

        // Returns the skiplist node with greatest value <= e
        private SkipListNode find(Integer e) {
            // 给定元素e,查询其所在的跳表节点
            return find(e, head, maxLevel);
        }

        // Returns the skiplist node with greatest value <= e
        // Starts at node start and level
        private SkipListNode find(Integer e, SkipListNode current, int level) {
            do {
                current = findNext(e, current, level);
            } while (level-- > 0);
            return current;  // 一直查到最下面一层
        }

        // Returns the node at a given level with highest value less than e
        private SkipListNode findNext(Integer e, SkipListNode current, int level) {
            // 首先获取当前层的下一个节点
            SkipListNode next = current.nextNodes.get(level);
            while (next != null) {
                Integer value = next.value;
                if (lessThan(e, value)) { // e < value  如果当前e小于下一层的节点值,则直接break,进入下一层
                    break;
                }
                current = next;
                next = current.nextNodes.get(level);
            }
            // 如果下一层为null,直接返回给父函数find(),进入下一层
            return current;
        }

        public int size() {
            return size;
        }

        // 检查跳表中是否存在此value
        public boolean contains(Integer value) {
            // 首先根据指定的值查询value在跳表种存在的节点
            SkipListNode node = find(value);
            // 查到的节点值和当前的值一样,则表示已经查到了


            return node != null && node.value != null && equalTo(node.value, value);
        }

        public Iterator<Integer> iterator() {
            return new SkipListIterator(this);
        }

        /******************************************************************************
         * Utility Functions *
         ******************************************************************************/

        private boolean lessThan(Integer a, Integer b) {
            return a.compareTo(b) < 0;
        }

        private boolean equalTo(Integer a, Integer b) {
            return a.compareTo(b) == 0;
        }
    }
上一篇下一篇

猜你喜欢

热点阅读