【算法&数据结构体系篇class36】有序表（中篇）SB树、跳表

梦里梦外; 2024-03-22 14:08 94阅读 0赞

### 一、SB树（size-balance-tree） ###

> 1）让每一个叔叔节点为头的数，节点个数都不少于其任何一个侄子节点
> 
> 2）也是从底层被影响节点开始向上做路径每个节点检查
> 
> 3）与AVL树非常像，也是四种违规类型：LL、RR、LR、RL
> 
> 4）与AVL树非常像，核心点是：
> 
> LL（做一次右旋）、RR（做一次左旋）
> 
> LR和RL（利用旋转让底层那个上到顶部）
> 
> 5）与AVL树不同的是，每轮经过调整后，谁的孩子发生变化了，谁就再查

### 二、SB树在使用时候的改进 ###

> 1）删除时候可以不用检查
> 
> 2）就把平衡性的调整放在插入的时候
> 
> 3）因为这种只要变就递归的特性，别的树没有
> 
> 4）可以在节点上封装别的数据项，来增加功能

代码演示：

package class36;
    
    
    
    /**
     * SB树（size-balance-tree）
     * 1）让每一个叔叔节点为头的数，节点个数都不少于其任何一个侄子节点   （叔叔节点就是  cur的父节点的兄弟节点  就是cur的叔叔节点 而且cur就是其侄子节点）
     * 2）也是从底层被影响节点开始向上做路径每个节点检查
     * 3）与AVL树非常像，也是四种违规类型：LL、RR、LR、RL
     * 4）与AVL树非常像，核心点是：
     * LL（做一次右旋）、RR（做一次左旋）
     * LR和RL（利用旋转让底层那个上到顶部）
     * 5）与AVL树不同的是，每轮经过调整后，谁的孩子发生变化了，谁就再查
     *    LL 调整后   cur.r  cur两个节点的孩子节点发生变化 所以就对两个节点递归进行再次调整
     *    LR    cur.l cur.r cur 三个节点
     *    RR    cur.l cur 两个节点
     *    RL    cur.l cur.r cur 三个节点
     *
     * SB树在使用时候的改进
     * 1）删除时候可以不用检查
     *
     * 2）就把平衡性的调整放在插入的时候
     *
     * 3）因为这种只要变就递归的特性，别的树没有
     *
     * 4）可以在节点上封装别的数据项，来增加功能
     */
    public class SizeBalancedTreeMap1 {
        //定义SB树节点类， K类型表示树的 key 支持比较 继承比较类 用于后续的大小比较找对应的节点位置
        public static class SBTNode<K extends Comparable<K>, V> {
            public K k;           //SB树节点的 key值
            public V v;           //SB树节点的 value值
            public SBTNode<K, V> l; //当前节点的左子节点
            public SBTNode<K, V> r; //当前节点的右子节点
            public int size;         //sb树该节点作为根节点的子树的节点个数  作为后续平衡性调整的关键因子
    
            public SBTNode(K key, V value) {    //构造器 初始化节点属性 键值
                k = key;
                v = value;
                size = 1;               //节点个数为当前节点本身 1
            }
        }
    
        //定义SB树类  实现有序表的类结构  注意Key值支持比较大小
        public static class SizeBalancedTreeMap<K extends Comparable<K>, V>{
            private SBTNode<K,V> root;            //定义SB树的根节点
    
            //右旋操作 将cur右旋到 其右子节点  而其左子节点会上移到cur位置
            //注意返回值 是因为要刷新当前节点树的新的头节点 给其他的方法调用返回 刷新
            private SBTNode<K,V> rightRotate(SBTNode<K,V> cur){
                SBTNode<K,V> left = cur.l;         //取出当前节点的左子节点
                cur.l = left.r;                    //left节点的右子树 赋值给 cur节点的左子树
                left.r = cur;                      //left上移 然后将右子树指向 cur节点
                left.size = cur.size;              //先调整 left树的节点个数 就换成cur树的个数
                cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;  //再调整cur 的个数 因为cur的位置子节点可能调整了所以等Left调整好再改
                return left; //返回新的头节点
            }
    
            //左旋操作 将cur左旋到 其左子节点  而其右子节点会上移到cur位置
            private SBTNode<K,V> leftRotate(SBTNode<K,V> cur){
                SBTNode<K,V> right = cur.r;         //取出当前节点的右子节点
                cur.r = right.l;                    //right节点的左子树 赋值给 cur节点的右子树
                right.l = cur;                      //right上移 然后将左子树指向 cur节点
                right.size = cur.size;              //先调整 right树的节点个数 就换成cur树的个数
                cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;  //再调整cur 的个数 因为cur的位置子节点可能调整了所以等right调整好再改
                return right; //返回新的头节点
            }
    
            //SBT树，调整平衡方法 返回调整后的新头节点
            // 注意这里的平衡 是根据 叔叔节点数 大于 全部每个侄子节点数  否则就是不平衡要调整
            //与AVL树相同分四种情况 LL LR RR RL
            //每一种对应的调整平衡旋转都一样  右旋  ； 对子节点左旋再对当前节点右旋 ； 左旋；  对子节点右旋再对当前节点左旋
            //不一样的地方在于 SBT树还需要再判断那些节点的孩子节点变化了 对这些节点 要递归继续调整平衡，因为可能会调整了树位置后 又多出了一些不平衡的情况
            //   LL 调整后   cur.r  cur两个节点的孩子节点发生变化 所以就对两个节点递归进行再次调整
            //   LR    cur.l cur.r cur 三个节点
            //   RR    cur.l cur 两个节点
            //   RL    cur.l cur.r cur 三个节点
            private SBTNode<K,V> maintain(SBTNode<K,V> cur){
                if(cur == null) return null;                 //cur空树  直接返回null
    
                //根据平衡特性 叔叔节点与侄子节点的比较  分别取出 cur.l cur.l.l cur.l.r ; cur.r cur.r.l cur.r.r 六个节点进行比较
                //也就是cur的左右子树 以及孙子树
                int leftSize = cur.l != null ? cur.l.size : 0;
                int leftLeftSize = cur.l != null && cur.l.l !=null ? cur.l.l.size : 0;
                int leftRightSize = cur.l != null && cur.l.r != null ? cur.l.r.size : 0;
                int rightSize = cur.r != null ? cur.r.size : 0;
                int rightLeftSize = cur.r != null && cur.r.l != null ? cur.r.l.size :0;
                int rightRightSize = cur.r != null && cur.r.r != null ? cur.r.r.size : 0;
    
                if(leftLeftSize > rightSize ){    //1.左左侄子树 大于 右叔叔树 LL型
                    cur = rightRotate(cur);      //当前节点右旋
                    cur.r = maintain(cur.r);     //当前节点的右子节点 其孩子节点变化 需要递归调用再调整看看是否不平衡了
                    cur = maintain(cur);         //等右子节点调整好 再调整cur节点 因为其孩子节点肯定也是变化了
                }
                else if(leftRightSize > rightSize){    //2. 左右侄子树 大于 右叔叔树 LR型
                    cur.l = leftRotate(cur.l);      //当前节点的左子节点 左旋
                    cur = rightRotate(cur);         //当前节点 右旋 把孙子节点提上来
                    cur.l = maintain(cur.l);     //当前节点的左子节点 其孩子节点变化 需要递归调用再调整看看是否不平衡了
                    cur.r = maintain(cur.r);     //当前节点的右子节点 其孩子节点变化 需要递归调用再调整看看是否不平衡了
                    cur = maintain(cur);         //等左右子节点调整好 再调整cur节点 因为其孩子节点肯定也是变化了
                }
                else if(rightRightSize > leftSize ){    //3.右右侄子树 大于 左叔叔树 RR型
                    cur = leftRotate(cur);      //当前节点左旋
                    cur.l = maintain(cur.l);     //当前节点的左子节点 其孩子节点变化 需要递归调用再调整看看是否不平衡了
                    cur = maintain(cur);         //等左子节点调整好 再调整cur节点 因为其孩子节点肯定也是变化了
                }
                else if(rightLeftSize > leftSize){    //4. 右左侄子树 大于 左叔叔树 RL型
                    cur.r = rightRotate(cur.r);      //当前节点的右子节点 右旋
                    cur = leftRotate(cur);         //当前节点 左旋 把孙子节点提上来
                    cur.l = maintain(cur.l);     //当前节点的左子节点 其孩子节点变化 需要递归调用再调整看看是否不平衡了
                    cur.r = maintain(cur.r);     //当前节点的右子节点 其孩子节点变化 需要递归调用再调整看看是否不平衡了
                    cur = maintain(cur);         //等左右子节点调整好 再调整cur节点 因为其孩子节点肯定也是变化了
                }
                return cur;    //最后要返回刷新的当前新头节点
            }
    
            //如果插入key  那么就要找要插入的位置 如果SBT树存在 key值的节点 那么就直接返回这个节点 后续就直接修改v值
            //如果不存在 那么就根据搜索顺序 往左右下移 直到空 返回的就是key的父节点
            private SBTNode<K,V> findLastIndex(K key){
                //定义两个辅助变量指向root 进行遍历
                SBTNode<K,V> pre = root;
                SBTNode<K,V> cur = root;
                //开始遍历cur 节点 ，
                while(cur != null){
                    //让pre指向cur
                    pre = cur;
                    //如果key值等于当前cur的key 那么就是找到最后经过的节点 不用再继续下去了  直接退出
                    if(key.compareTo(cur.k) == 0){
                        break;
                    } else if(key.compareTo(cur.k) < 0){
                        //如果key是比当前cur小的 那么就去cur的左子树找，因为左子树值小 区间就在左子树
                        cur = cur.l;
                    }else{
                        //如果key比当前cur大，那么就需要继续到cur的右子树找，找到最靠近key的节点
                        cur =cur.r;
                    }
                }
                return pre;  //最后返回辅助变量指向的就是最终的结果
            }
    
            //获取大于等于指定的key的最靠近的节点 比如key=8  SBT树节点有1,3,6,7,13,10 那么就返回10 最接近8 且大于等于8  如果存在8 就返回8
            private SBTNode<K,V> findLastNoSmallIndex(K key){
                SBTNode<K,V> ans = null;
                SBTNode<K,V> cur = root;
                while(cur != null){
                    if(key.compareTo(cur.k) == 0){
                        //key 等于当前cur的key  ans指向当前节点cur 退出
                        ans = cur;
                        break;
                    }else if(key.compareTo(cur.k) < 0){
                        //如果key 小于cur的key 说明cur是在目标范围内的，ans赋值当前节点 接着下层到做子树看看有没有更小更接近key的节点
                        ans = cur;
                        cur = cur.l;
                    }else{
                        //如果key大于cur 说明cur 不在范围内，需要往右子树 扩大到 大于等于key值
                        cur = cur.r;
                    }
                }
                return ans;  //最后返回ans 节点
            }
    
            //获取小于等于指定的key的最靠近的节点 比如key=8  SBT树节点有1,3,6,7,13,10 那么就返回7 最接近8 且小于等于8  如果存在8 就返回8
            private SBTNode<K,V> findLastNoBigIndex(K key){
                SBTNode<K,V> ans = null;
                SBTNode<K,V> cur = root;
                while(cur != null){
                    if(key.compareTo(cur.k) == 0){
                        ans = cur;
                        break;
                    } else if(key.compareTo(cur.k) > 0){  //key 大于 cur.k 说明是在范围内 赋值ans 并且接着往右子树扩大看有没有更接近的节点
                        ans = cur;
                        cur = cur.r;
                    } else{
                        cur = cur.l;
                    }
                }
                return ans;
            }
    
            //添加一个K,V值，传入的root节点从整个SBT树的根节点开始往下遍历
            //因为添加的过程可能会需要调整平衡性，并且会不断往最低个下层 找到位置添加 然后再返回新调整好的节点返回上层 就需要递归
            //为了方便 我们递归函数给一个 返回当前节点的返回值
            private SBTNode<K,V> add(SBTNode<K,V> cur, K key, V value){
                if(cur == null){
                    //如果是一个空的树，那么添加的节点 就直接返回一个新节点就可以了
                    return new SBTNode<>(key,value);
                } else{
                    //添加元素 个数要加
                    cur.size++;
                    //如果非空，那么就判断大小 如果key 比cur的大 那么就需要cur.r 去递归右子树 否则就是递归左子树 并且要返回接收刷新节点左右子树
                    //这里没有等于的情况，因为会在 调用添加节点的 put方法去提前做相等的判断
                    if(key.compareTo(cur.k) > 0){
                        cur.r = add(cur.r,key,value);
                    }else{
                        cur.l = add(cur.l,key,value);
                    }
    
                    //然后再调整cur的平衡性
                    return maintain(cur);
                }
            }
    
            //在cur头节点的SBT树上，删掉key的对应节点 ， 返回树的新头节点，因为可能会涉及平衡调整 ，头节点需要返回
            private SBTNode<K,V> delete(SBTNode<K,V> cur, K key){
                cur.size--;   //节点个数上来先减
                if(key.compareTo(cur.k) > 0){
                    //key 大于 cur 那么就递归 cur右子树 并且返回新的右子树头节点
                    cur.r = delete(cur.r, key);
                } else if(key.compareTo(cur.k) < 0){
                    //key 小于 cur 递归cur左子树
                    cur.l = delete(cur.l, key);
                } else{ //相等值，那么就表示要删的节点找到了
                    if(cur.l == null && cur.r == null){
                        cur = null;    //如果没有左右子节点 直接删除 cur赋值空
                    } else if(cur.l != null && cur.r == null){  //左非空 右空 直接将左子节点上移
                        cur = cur.l;
                    } else if(cur.r != null && cur.l == null){  //右非空 左空 右子节点上移
                        cur = cur.r;
                    } else {
                        //左右子节点非空，那么删除cur节点 就需要找后继节点 替换cur 也就是cur的右子树的最左子节点，这个节点就是接着比cur大的最接近的下个节点
                        //思路就是 先在cur.r子树中 找到最左子节点  然后把该节点  提出到cur节点
                        //而最左子节点 也可能有右子树 那么就把这个右子树挂到 最左子节点的父节点的左子树上即可
                        SBTNode<K,V> pre = null;              //pre赋值变量 用来获取cur的右子树的最左子节点的父节点
                        SBTNode<K,V> next = cur.r;            //当前节点的右子树
                        next.size--;                          //由于 右子树最左子节点要提到cur位置 所以每个上层节点的大小要依次-1 这里先进行-1操作
                        while(next.l != null){
                            pre = next;    //把next赋值给pre 到最后跳出时 next来到最左子节点 而pre就是其父节点
                            next = next.l; //下沉到cur右子树的最左节点 直到为空停 next就是最左子节点
                            next.size--;   //每个下节点的大小都需要-1 因为最底部的左子节点将被提取
                        }
    
                        if(pre != null){  //跳出循环 如果说最左节点的存在父节点
                            pre.l = next.r;   //此时next最左子节点提上去后  其右子树 就指向父节点的左子树位置  也就是顶替上去之前的最左子节点
                            next.r = cur.r;   //并且将最左子节点的右指向 指到当前节点的右指向 进行替换cur位置
                        }
                        //如果说pre为空 说明cur.r 右子树 只有一个节点。 该节点就充当最左子节点 上移到cur 那么其右子树自然是指向null 就不用进行指向cur.r
                        next.l = cur.l;      //最后这里 再将cur的左子树 指向 next最左子节点的左子树 替换cur
                        next.size = next.l.size + (next.r == null ? 0 : next.r.size) + 1;  //刷新next节点的个数
                        cur = next;                     //最后cur节点再指向新的节点  完成cur的替换并且删除了cur
                    }
                }
                return cur;    //最后返回cur新的头节点 这里就不需要再调用平衡调整方法 SBT的特别之处就在于此 会在add的时候快速调整整个树的平衡 效率一样都是高效的 logN 因为最多就是一个高度的往上调整
            }
    
    
            //在cur头节点的SBT树上，查询 key为 kth的所在节点   假设kth = 3，表示要当前树上第3小的节点
            private SBTNode<K,V> getIndex(SBTNode<K,V> cur, int kth){
                //注意要判断cur.l是否为空 避免空指针异常
                if(kth == (cur.l != null ? cur.l.size : 0) + 1){
                    //1.假设当前头节点cur，左树上2个节点，就中了第一个if， 3 = 2+1 左树上2个节点，右数上又都是比cur大的节点，所以cur正好是第3个。于是直接返回。
                    return cur;
                } else if(kth <= (cur.l != null ? cur.l.size : 0)){
                    //2.假设当前头节点cur，左树上5个节点，就中了第2个if，3 < 5,左树上5个节点，一定包含第3小的节点，所以在左树上找第3小的节点。
                    return getIndex(cur.l,kth);
                } else {
                    //3.假设当前头节点cur，左树上1个节点。就中了第3个if，左树上1个节点，头节点1个节点，这一共才凑够前两小，那么第3小的节点呢？一定是右树上第1小的节点。 所有就传参要减去左数个数 再减当前节点1
                    return getIndex(cur.r, kth - (cur.l != null ? cur.l.size : 0) - 1);
                }
            }
    
            //外部接口： 获取整个树的节点个数
            public int size(){
                return root == null ? 0 : root.size;
            }
    
            //外部接口： 判断key值是否包含在SBT树中
            public boolean containsKey(K key){
                if(key == null){
                    //如果key是空值 就手动抛个异常返回
                    throw new RuntimeException("invalid parameter.");
                }
                //调用方法查询key对应的节点位置 如果key存在 那么node就是对应的key节点 返回true 否则返回false
                SBTNode<K,V> node = findLastIndex(key);
                return node != null && key.compareTo(node.k) == 0 ;
            }
    
            //外部接口： 新增k,v节点 put   如果存在同个key 就将value刷新即可
            public void put(K key, V value){
                if(key == null){  //空的key  直接抛出异常
                    throw new RuntimeException("invalid parameter.");
                }
                SBTNode<K,V> node = findLastIndex(key); //获取key对应的在树中的节点
                if(node != null && key.compareTo(node.k) == 0){
                    node.v = value;    //如果存在key对应的节点 ，就刷新节点的value值
                }else{
                    root = add(root,key,value);   //如果不存在 那么就在整个树 添加新节点 并且返回新的头节点 赋值给root
                }
            }
    
            //外部接口： 移除key节点 如果存在key节点的话
            public void remove(K key){
                if(key == null) return;
                if(containsKey(key)){  //如果存在该节点  则调用删除方法进行删除节点 然后root接收新的头节点
                    root = delete(root,key);
                }
            }
    
            //外部接口： 获取树对应的索引的节点的key  索引是从0开始的 注意 所以key=0 表示要取树中第一个节点 第一小的节点 也就是树的最左子节点
            public K getIndexKey(int index){
                if(index < 0 || index >= size()){
                    throw new RuntimeException("invalid parameter.");
                }
                return getIndex(root,index + 1).k;  //index索引范围合理 就调用方法返回节点的k值 注意index要+1 因为该方法是 从1开始的 最小
            }
    
            //外部接口： 获取索引对应节点的value
            public V getIndexValue(int index){
                if(index < 0 || index >= size()){
                    throw new RuntimeException("invalid parameter.");
                }
                return getIndex(root,index+1).v;    //调用方法返回节点的v值 index索引要+1
            }
    
            //外部接口： 获取key 节点对应的value
            public V get(K key){
                if(key == null){
                    throw new RuntimeException("invalid parameter.");
                }
                SBTNode<K,V> node = findLastIndex(key);  //获取key 对应节点
                if(node !=null && key.compareTo(node.k) == 0){
                    return node.v;   //如果对应节点找到 与key值相等 就返回该节点的value
                } else{
                    return null;      //如果没有找到 返回null
                }
            }
    
            //外部接口： 获取树中的第1个Key  SBT树中的最左子节点 就是第一个节点
            public K firstKey(){
                if(root == null) return null;    //空树 返回null
                SBTNode<K,V> node = root;        //节点赋值root
                while (node.l != null){          //往左节点遍历直到空 node就会来到最左子节点
                    node = node.l;
                }
                return node.k;                   //返回其节点的key
            }
    
            //外部接口： 获取树中的最后1个Key  SBT树中的最右子节点
            public K lastKey(){
                if(root == null) return null;    //空树 返回null
                SBTNode<K,V> node = root;        //节点赋值root
                while (node.r != null){          //往右节点遍历直到空 node就会来到最右子节点
                    node = node.r;
                }
                return node.k;                   //返回其节点的key
            }
    
            //外部接口： 获取树中 小于等于key的节点 最大的节点 也就是就接近key的节点
            public K floorKey(K key){
                if(key == null){
                    throw new RuntimeException("invalid parameter.");
                }
                //调用小于等于方法 返回节点 非空则为小于等于key的最大的那个节点 返回其key
                SBTNode<K,V> node = findLastNoBigIndex(key);
                return node != null ? node.k : null;
            }
    
            //外部接口： 获取树中 大于等于key的节点 最小的节点 也就是就接近key的节点
            public K ceilingKey(K key){
                if(key == null){
                    throw new RuntimeException("invalid parameter.");
                }
                //调用大于等于方法 返回节点 非空则为大于等于key的最小的那个节点 返回其key
                SBTNode<K,V> node = findLastNoSmallIndex(key);
                return node != null ? node.k : null;
            }
        }
    
        // for test
        public static void printAll(SBTNode<String, Integer> head) {
            System.out.println("Binary Tree:");
            printInOrder(head, 0, "H", 17);
            System.out.println();
        }
    
        // for test
        public static void printInOrder(SBTNode<String, Integer> head, int height, String to, int len) {
            if (head == null) {
                return;
            }
            printInOrder(head.r, height + 1, "v", len);
            String val = to + "(" + head.k + "," + head.v + ")" + to;
            int lenM = val.length();
            int lenL = (len - lenM) / 2;
            int lenR = len - lenM - lenL;
            val = getSpace(lenL) + val + getSpace(lenR);
            System.out.println(getSpace(height * len) + val);
            printInOrder(head.l, height + 1, "^", len);
        }
    
        // for test
        public static String getSpace(int num) {
            String space = " ";
            StringBuffer buf = new StringBuffer("");
            for (int i = 0; i < num; i++) {
                buf.append(space);
            }
            return buf.toString();
        }
    
        public static void main(String[] args) {
            SizeBalancedTreeMap<String, Integer> sbt = new SizeBalancedTreeMap<String, Integer>();
            sbt.put("d", 4);
            sbt.put("c", 3);
            sbt.put("a", 1);
            sbt.put("b", 2);
            // sbt.put("e", 5);
            sbt.put("g", 7);
            sbt.put("f", 6);
            sbt.put("h", 8);
            sbt.put("i", 9);
            sbt.put("a", 111);
            System.out.println(sbt.get("a"));
            sbt.put("a", 1);
            System.out.println(sbt.get("a"));
            for (int i = 0; i < sbt.size(); i++) {
                System.out.println(sbt.getIndexKey(i) + " , " + sbt.getIndexValue(i));
            }
            printAll(sbt.root);
            System.out.println(sbt.firstKey());
            System.out.println(sbt.lastKey());
            System.out.println(sbt.floorKey("g"));
            System.out.println(sbt.ceilingKey("g"));
            System.out.println(sbt.floorKey("e"));
            System.out.println(sbt.ceilingKey("e"));
            System.out.println(sbt.floorKey(""));
            System.out.println(sbt.ceilingKey(""));
            System.out.println(sbt.floorKey("j"));
            System.out.println(sbt.ceilingKey("j"));
            sbt.remove("d");
            printAll(sbt.root);
            sbt.remove("f");
            printAll(sbt.root);
    
        }
    }

111
    1
    a , 1
    b , 2
    c , 3
    d , 4
    f , 6
    g , 7
    h , 8
    i , 9
    Binary Tree:
                                           v(i,9)v     
                          v(h,8)v     
                                           ^(g,7)^     
         H(f,6)H     
                                           v(d,4)v     
                          ^(c,3)^     
                                                            v(b,2)v     
                                           ^(a,1)^     
    
    a
    i
    g
    g
    d
    f
    null
    a
    i
    null
    Binary Tree:
                                           v(i,9)v     
                          v(h,8)v     
                                           ^(g,7)^     
         H(f,6)H     
                          ^(c,3)^     
                                                            v(b,2)v     
                                           ^(a,1)^     
    
    Binary Tree:
                                           v(i,9)v     
                          v(h,8)v     
         H(g,7)H     
                          ^(c,3)^     
                                                            v(b,2)v     
                                           ^(a,1)^     
    
    
    Process finished with exit code 0

### 三、跳表（skiplist） ###

> 1）结构上根本和搜索二叉树无关
> 
> 2）利用随机概率分布来使得高层索引可以无视数据规律，做到整体性能优良
> 
> 3）思想是所有有序表中最先进的
> 
> 4）结构简单就是多级单链表

代码演示：

package class36;
    
    import java.util.ArrayList;
    import java.util.Currency;
    
    /**
     * 跳表（skiplist）
     * 1）结构上根本和搜索二叉树无关
     *
     * 2）利用随机概率分布来使得高层索引可以无视数据规律，做到整体性能优良
     *
     * 3）思想是所有有序表中最先进的
     *
     * 4）结构简单就是多级单链表
     */
    public class SkipListMap1 {
        //跳表的节点定义
        public static class SkipListNode<K extends Comparable<K>, V>{
            //节点的键值   以及一个下个指向的链表集合
            public K k;
            public V v;
            public ArrayList<SkipListNode<K,V>> nextNodes;
    
            public SkipListNode(K key, V value){
                k = key;
                v = value;
                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非空 k 空 返回true  表示空值是最小的
                //两者非空 那么k 小于 otherkey就返回true
                return otherKey != null && (k == null || k.compareTo(otherKey) < 0);
            }
    
            //判断key值 是否与当前的节点的k值相等   都为空 则判断相等
            public boolean isKeyEqual(K key){
                return (k == null && key == null) || (k != null && key != null && k.compareTo(key) == 0);
            }
        }
    
        //定义跳表类 实现有序表
        public static class SkipListMap<K extends Comparable<K>, V>{
            private SkipListNode<K,V> head;        //定义跳表的头节点 第一个节点
            private final double P = 0.5;   //p概率 用于后续进行随机概率判断节点的层级  <0.5就增加层级 否则就不做
            private int size;               //跳表的节点个数
            private int maxLevel;           //跳表的最高层级 第一层是 0， 第二层1 ...
    
            public SkipListMap(){           //构造器初始化
                head = new SkipListNode<>(null,null);
                head.nextNodes.add(null);   //注意这里头节点的 下层指向集合 可以初始化时添加一个 null
                size = 0;
                maxLevel = 0;
            }
    
            // 在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);     //获取当前节点cur 在level层上的  指向节点
                while (next != null && next.isKeyLess(key)){           //遍历next下个节点 非空并且其k值小于目标节点key 就继续往下个节点走
                    cur = next;
                    next = cur.nextNodes.get(level);
                }
                return cur;          //最后跳出循环 cur就是小于key 最右的一个节点
            }
    
            // 从最高层开始，一路找下去，
            // 最终，找到第0层的<key的最右的节点
            private SkipListNode<K,V> mostRightLessNodeInTree(K key){
                if(key == null) return null;    //如果查询的key是 null 那么就直接返回null
                int level = maxLevel;           //获取当前跳表的层级高度
                SkipListNode<K,V> node = head;  //获取当前跳表的头节点 用来遍历
    
                while(level >= 0){              //从最高层级开始往下层走到底0层位置
                    node = mostRightLessNodeInLevel(key,node,level--);    //调用方法 当前头节点开始 最高层级 往下指向下一个层级的对应节点返回 层级-- 一直迭代
                }
                return node;    //最后跳出循环 就在0层了 node就是 <key的最右节点
            }
    
            //外部接口：判断 跳表中是否存在key值的节点
            public boolean containsKey(K key){
                if(key == null) return false;
                SkipListNode<K,V> node = mostRightLessNodeInTree(key);    //找到小于key 最右的节点
                SkipListNode<K,V> cur = node.nextNodes.get(0);            //最右节点的下个节点 get(0) 如果值为key 非空 那么就表示存在
                return cur != null && cur.isKeyEqual(key);      //非空 且 值相等 cur 就是其节点 返回true
            }
    
            //外部接口： 新增节点到跳表上 如果该key存在 那就进行进行 不存在就进行插入
            public void put(K key, V value){
                if(key == null) return;
    
                //调用方法 找到整个树上 <key 离key最近的节点
                SkipListNode<K,V> pre = mostRightLessNodeInTree(key);
                //获取下个指向集合在第一个 就是来到了key位置
                SkipListNode<K,V> node = pre.nextNodes.get(0);
                if(node != null && node.isKeyEqual(key)){
                    //如果找到的节点非空 并且k值等于key 那么说明树中存在key值节点 就进行修改value
                    node.v = value;
                } else{
                    //如果不存在 那么就新增节点  树的个数加1
                    size++;
                    //然后用随机概率判断 节点所占有的层级高度
                    int newNodeLevel = 0;
                    while (Math.random() < P){
                        //如果概率小于P 那么就进行层级增加
                        newNodeLevel++;
                    }
                    //然后需要判断 如果新节点高度 比当前跳表最大高度还大 那就需要先把最大高度追加到相等 并且把下个指向集合追加null节点
                    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); //首先对节点的下指向做初始化 高度多少 指向就有多少个
                    }
    
                    //接着就开始进行从最高层遍历到0层
                    int level = maxLevel;
                    SkipListNode<K,V> cur = head;  //cur指向头节点
                    while (level >= 0){
                        //从最高层开始往下遍历 找到当前层级对应 <key 最右的节点
                        cur = mostRightLessNodeInLevel(key,cur,level);
    
                        //注意当最高层级遍历 是来到了要插入节点的层级时，才表示节点需要依次对每一层进行插入
                        //比如最高高度一开始8， 节点随机高度后时10 那么maxlevel就会先升到同等高度 10
                        //此时情况 就是每一层都是有节点值 就会进判断做插入
                        //比如maxLevel=8  newNodeLevel=4 说明新节点层级只会出现在 4 3 2 1 0 层
                        //所以就只会当maxLevel 减到 4的时候 后面的层级才会进判断 对每一层做节点插入
                        if(level <= newNodeLevel){
                            //先将新节点的下个指向  设置为 前一个节点cur的下个指向 都是在level层级的指向  因为节点就是插入 cur --> next 这个中间
                            newNode.nextNodes.set(level,cur.nextNodes.get(level));
                            //再将前一个节点cur 下个指向节点 设置为新节点  就完成了当前level层级 节点的插入
                            cur.nextNodes.set(level,newNode);
                        }
                        level--;   //然后层级--来到下个层级 直到0层
                    }
                }
            }
    
            //外部接口： 获取跳表上的key对应的值
            public V get(K key){
                if(key == null) return null;
                //找到跳表树中 <key 最右的节点pre
                SkipListNode<K,V> pre = mostRightLessNodeInTree(key);
                //pre 的下个指向集合的第一个元素 Node   就是key的位置
                SkipListNode<K,V> node = pre.nextNodes.get(0);
                //如果节点非空 且节点k值等于Key值 说明存在这个key对应节点 返回其v值 否则就是null
                return node != null && node.isKeyEqual(key) ? node.v : null;
    
            }
    
            //外部接口： 删除跳表上的key对应的节点
            public void remove(K key){
                //如果包含key值的节点  再进行删除动作
                if(containsKey(key)){
                    size--;             //跳表节点数-1
                    int level = maxLevel;    //跳表最高层级高度  用来从高往底层依次删除key对应的节点
                    SkipListNode<K,V> pre = head;        //头节点
                    while(level >= 0 ){
                        pre = mostRightLessNodeInLevel(key,pre,level);     //获取当前pre节点 所在level层级 <key的最右节点
                        SkipListNode<K,V> node = pre.nextNodes.get(level);     //获取pre下个指向节点 node就是key位置
                        if(node != null && node.isKeyEqual(key)){          //如果节点非空 且key值相等 说明这个节点就是key对应节点
                            pre.nextNodes.set(level,node.nextNodes.get(level));    //将pre前一个节点指向 跳过node 来到node的下个节点
                        }
                        //这里还需要注意 如果删除后 当前层 节点都空了 只剩下一个head 节点 也就是pre是head节点 那这一层就要删除 并且层级要-1
                        if(level != 0 && pre == head && pre.nextNodes.get(level) == null){
                            head.nextNodes.remove(level);
                            maxLevel--;    //最高层级-1
                        }
                        level--;    //当前层处理完之后要-1
                    }
                }
            }
    
            //外部接口： 获取跳表的第一个key值  也就是第0层 head头节点的下个节点
            public K firstKey(){
                return head.nextNodes.get(0) != null ? head.nextNodes.get(0).k : null;
            }
    
            //外部接口： 获取跳表的最后一个key值 依次从高层的指向节点跳转到最后一个节点 这样的方式 时间复杂度才能O(logN)
            public K lastKey(){
                int level = maxLevel;          //跳表最高层级高度
                SkipListNode<K,V> cur = head; //头节点开始去找下个指向节点
                while (level >= 0){
                    SkipListNode<K,V> next = cur.nextNodes.get(level);  //节点在level层级的下个指向
                    while (next != null){                           //next非空 就继续往右指向
                        cur = next;
                        next = cur.nextNodes.get(level);
                    }
                    level--;     //层级-- 只要最后第0层
                }
                return cur.k;    //最后返回cur节点 就是最后节点
            }
    
            //外部接口： 获取 大于等于key 最小的节点
            public K ceilingKey(K key){
                if(key == null) return null;
                SkipListNode<K,V> pre = mostRightLessNodeInTree(key);   //获取<key 最右节点
                SkipListNode<K,V> node = pre.nextNodes.get(0);          //获取下个指向 因为当前来到的是最后第0层 所以就是0索引 node就是key位置
                return node != null ? node.k : null;                    //node就是大于等于key的第一个位置 非空 就直接返回即可 如果是空 那么就表示不存在 返回null
            }
    
            //外部接口： 获取 小于等于key 最大的节点
            public K floorKey(K key){
                if(key == null) return null;
                SkipListNode<K,V> pre = mostRightLessNodeInTree(key);   //获取<key 最右节点
                SkipListNode<K,V> node = pre.nextNodes.get(0);          //获取下个指向 因为当前来到的是最后第0层 所以就是0索引 node就是key位置
                return node != null && node.isKeyEqual(key)? node.k : pre.k;                    //如果node K值相等 那么最右节点就是node 否则就是pre
            }
    
            //外部接口： 获取跳表的节点个数
            public int size(){
                return size;
            }
    
            // for test
            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.k + " , " + next.v + ") ");
                        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"));
    
    
            }
    
    
    
        }
    
    
    }

Level 0 : 
    ======================
    Level 0 : (A , 10) 
    ======================
    Level 0 : 
    ======================
    Level 2 : (C , C) 
    Level 1 : (A , A) (C , C) (D , D) 
    Level 0 : (A , A) (B , B) (C , C) (D , D) (E , E) (F , F) 
    ======================
    true
    false
    C
    F
    D
    D
    ======================
    Level 2 : (C , C) 
    Level 1 : (A , A) (C , C) 
    Level 0 : (A , A) (B , B) (C , C) (E , E) (F , F) 
    ======================
    C
    E
    
    Process finished with exit code 0