有序表之跳表

前言

有序表按照设计思想分类的话，AVL树，SB树，红黑树属于上世纪设计思想；跳表属于本世纪设计思想，因为跳表的设计思想比上述实现有序表的结构更先进。

但是跳表的常数项时间有点大。那么跳表还是搜索二叉树吗？用跳表实现有序表去增删改查它的时间复杂度也是LogN吗？

回顾

积压结构

什么是积压结构，我的理解是不用频繁变动和扩容，ArrayList和HashMap都属于积压结构，还有SB树和红黑树，但是AVL树不属于积压结构。比如ArrayList动态数组，是以2^n方式来进行扩容。

所以积压结构适合用在硬盘上，而AVL树适合用在内存里，因为AVL树的平衡性最严苛，变动最频繁；而SB树，红黑树很久都不用调整自己的平衡性，所以在硬盘上的IO时间这个缺点不明显。

但是，如果将来材料科学进步了，导致硬盘上的读写跟内存一样快，那么SB树，红黑树这些属于积压结构的设计都将走向没落。

跳表

package com.harrison.class25;

import java.util.ArrayList;

/**
 * @author Harrison
 * @create 2022-04-05-10:12
 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
 */
public class Code03_SkipListMap {
    // 跳表的结点定义
    public static class SkipListNode<K extends Comparable<K>,V>{
        public K key;
        public V val;
        public ArrayList<SkipListNode<K,V>> nextNodes;

        public SkipListNode(K k,V v){
            key=k;
            val=v;
            nextNodes=new ArrayList<SkipListNode<K,V>>();
        }

        // 遍历的时候，如果是往右遍历到的null(next == null), 遍历结束
        // 头(null), 头节点的null，认为最小
        // node  -> 头，node(null, "")  node.isKeyLess(!null)  true
        // node里面的key是否比otherKey小，true，不是false
        public boolean isKeyLess(K otherKey){
            // otherKey==null -> false
            return otherKey!=null && (key==null || key.compareTo(otherKey)<0);
        }

        public boolean isKeyEqual(K otherKey){
            return (key==null && otherKey==null) ||
                    (key!=null && otherKey!=null && key.compareTo(otherKey)==0);
        }
    }

    public static class SkipListMap<K extends Comparable<K>,V>{
        private static final double PROBABILITY=0.5;// <0.5继续做，>=0.5就停
        private SkipListNode<K,V> head;
        private int size;
        private int maxLevel;

        public SkipListMap(){
            head=new SkipListNode<>(null,null);
            head.nextNodes.add(null);
            size=0;
            maxLevel=0;
        }

        // 从最高层开始，一路找下去，
        // 最终，找到第0层的<key的最右的节点
        private SkipListNode<K,V> mostRightLessNodeInTree(K key){
            if(key==null){
                return null;
            }
            int level=maxLevel;
            SkipListNode<K,V> cur=head;
            // 从上层跳下层
            while(level>=0){
                cur=mostRightLessNodeInLevel(key,cur,level--);
            }
            return cur;
        }

        // 在level层里，如何往右移动
        // 现在来到的节点是cur，来到了cur的level层，在level层上，找到<key最后一个节点并返回
        private SkipListNode<K,V> mostRightLessNodeInLevel(K key,SkipListNode<K,V> cur,int level){
            // 上面层跳过一个，下面层就会跳过一批，优势就体现在这里
            SkipListNode<K,V> next=cur.nextNodes.get(level);
            while (next!=null && next.isKeyLess(key)){
                cur=next;
                next=cur.nextNodes.get(level);
            }
            return cur;
        }

        public boolean containsKey(K key){
            if(key==null){
                return false;
            }
            SkipListNode<K,V> less=mostRightLessNodeInTree(key);
            SkipListNode<K,V> next=less.nextNodes.get(0);
            return next!=null && next.isKeyEqual(key);
        }

        // 新增，修改value
        public void put(K key,V value){
            if(key==null){
                return ;
            }
            // 0层上，最右一个，< key 的Node -> >key
            SkipListNode<K,V> less=mostRightLessNodeInTree(key);
            SkipListNode<K,V> find=less.nextNodes.get(0);
            if(find!=null && find.isKeyEqual(key)){// 直接更新
                find.val=value;
            }else{// find==null
                size++;
                int newNodeLevel=0;
                while(Math.random()<PROBABILITY){
                    newNodeLevel++;
                }
                // newNodeLevel
                while(newNodeLevel>maxLevel){
                    head.nextNodes.add(null);
                    maxLevel++;
                }
                SkipListNode<K,V> newNode=new SkipListNode<>(key,value);
                for(int i=0; i<=newNodeLevel; i++){
                    newNode.nextNodes.add(null);
                }
                int level=maxLevel;
                SkipListNode<K,V> pre=head;
                while(level>=0){
                    // level 层中，找到最右的 < key 的节点
                    pre=mostRightLessNodeInLevel(key,pre,level);
                    if(level<=newNodeLevel){
                        newNode.nextNodes.set(level,pre.nextNodes.get(level));
                        pre.nextNodes.set(level,newNode);
                    }
                    level--;
                }
            }
        }

        public void remove(K key){
            if(containsKey(key)){
                size--;
                int levle=maxLevel;
                SkipListNode<K,V> pre=head;
                while(levle>=0){
                    pre=mostRightLessNodeInLevel(key,pre,levle);
                    SkipListNode<K,V> next=pre.nextNodes.get(levle);
                    // 1）在这一层中，pre下一个就是key
                    // 2）在这一层中，pre的下一个key是>要删除key
                    if(next!=null && next.isKeyEqual(key)){
                        // free delete node memory -> C++
                        // level : pre -> next(key) -> ...
                        // 前一个结点在level层的指针指向要删除的下一个结点
                        pre.nextNodes.set(levle,next.nextNodes.get(levle));
                    }
                    // 在level层只有一个节点了，就是默认节点head
                    if(levle!=0 && pre==head && pre.nextNodes.get(levle)==null){
                        head.nextNodes.remove(levle);
                        maxLevel--;
                    }
                    levle--;
                }
            }
        }

        public V get(K key) {
            if (key == null) {
                return null;
            }
            SkipListNode<K, V> less = mostRightLessNodeInTree(key);
            SkipListNode<K, V> next = less.nextNodes.get(0);
            return next != null && next.isKeyEqual(key) ? next.val : null;
        }

        public K firstKey() {
            return head.nextNodes.get(0) != null ? head.nextNodes.get(0).key : null;
        }

        public K lastKey() {
            int level = maxLevel;
            SkipListNode<K, V> cur = head;
            while (level >= 0) {
                SkipListNode<K, V> next = cur.nextNodes.get(level);
                while (next != null) {
                    cur = next;
                    next = cur.nextNodes.get(level);
                }
                level--;
            }
            return cur.key;
        }

        public K ceilingKey(K key) {
            if (key == null) {
                return null;
            }
            SkipListNode<K, V> less = mostRightLessNodeInTree(key);
            SkipListNode<K, V> next = less.nextNodes.get(0);
            return next != null ? next.key : null;
        }

        public K floorKey(K key) {
            if (key == null) {
                return null;
            }
            SkipListNode<K, V> less = mostRightLessNodeInTree(key);
            SkipListNode<K, V> next = less.nextNodes.get(0);
            return next != null && next.isKeyEqual(key) ? next.key : less.key;
        }

        public int size() {
            return size;
        }
    }

    public static void printAll(SkipListMap<String, String> obj) {
        for (int i = obj.maxLevel; i >= 0; i--) {
            System.out.print("Level " + i + " : ");
            SkipListNode<String, String> cur = obj.head;
            while (cur.nextNodes.get(i) != null) {
                SkipListNode<String, String> next = cur.nextNodes.get(i);
                System.out.print("(" + next.key + " , " + next.val + ") ");
                cur = next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        SkipListMap<String, String> test = new SkipListMap<>();
        printAll(test);
        System.out.println("======================");
        test.put("A", "10");
        printAll(test);
        System.out.println("======================");
        test.remove("A");
        printAll(test);
        System.out.println("======================");
        test.put("E", "E");
        test.put("B", "B");
        test.put("A", "A");
        test.put("F", "F");
        test.put("C", "C");
        test.put("D", "D");
        printAll(test);
        System.out.println("======================");
        System.out.println(test.containsKey("B"));
        System.out.println(test.containsKey("Z"));
        System.out.println(test.firstKey());
        System.out.println(test.lastKey());
        System.out.println(test.floorKey("D"));
        System.out.println(test.ceilingKey("D"));
        System.out.println("======================");
        test.remove("D");
        printAll(test);
        System.out.println("======================");
        System.out.println(test.floorKey("D"));
        System.out.println(test.ceilingKey("D"));


    }
}