一、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）结构简单就是多级单链表文章来源：https://www.toymoban.com/news/detail-438150.html
代码演示：文章来源地址https://www.toymoban.com/news/detail-438150.html
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到了这里，关于【算法&数据结构体系篇class36】有序表 （中篇）SB树、跳表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
