当前位置：首页 > news >正文

有序表--跳表

news 来源：原创 2025/8/16 4:04:41

实现一种结构，支持如下操作，要求单次调用的时间复杂度O(log n)
1，增加x，重复加入算多个词频
2，删除x，如果有多个，只删掉一个
3，查询x的排名，x的排名为，比x小的数的个数+1
4，查询数据中排名为x的数
5，查询x的前驱，x的前驱为，小于x的数中最大的数，不存在返回整数最小值
6，查询x的后继，x的后继为，大于x的数中最小的数，不存在返回整数最大值

跳表的节点结构，类似于链表的节点结构，但是可能包含多层指针，一个节点在创建完毕后，它可以拥有多少层指针，类似于扔骰子，[0,1)的随机数，小于0.5就增加一层，大于0.5终止，总层数不超过设置的最大层高。一个节点建立完毕，就能够确定有多少层指针，一旦确定，不会改变。最大层高的设置，是根据插入节点的个数来确定的，例如此时有100万个节点建立跳表，2的20次方是1,048,576，因此此时可以建立20层高的跳表。

插入，假设现在链表的层高是6层，插入节点时，从最高层开始插入，每一层去寻找比插入节点小的最大节点，一层层的往下走，达到应该插入的层数，进行插入。精确查询，从最高层开始，寻找小于查询值尽量大的，未匹配上（完全相等）就向下跳。如果到第一层找不到，说明跳表中没有这个节点。查询小于x尽量大的，通过相同的方法，查到第一层，在第一层中找到小于x尽量大的。时间复杂度为O(logN),第一层N个节点，第二层N/2个...高层的更加少，当从高层节点进行操作时，跨过的低层节点有很多，当走到最后一层的时候，走的大致是跳表的高度，此时设定2^高度=节点个数，因此此时的时间复杂度是O(logN)。

现在要去查询某个节点的排名，如果按照第一层的查询，一定可以查询出，但是时间复杂度达到O(N),而且也没有很好的利用跳表的结构。为了更加高效的查询，在每一层的指针上维护跨过第一层的节点个数，而且也可以更好的寻找排名信息。

静态数组的实现方式：

key[]:某个节点的键值，count[]:同样的键值收集次数，level[]:当前节点一共几层链表，next[][]:每一层链表去往那一个编号的节点，len[][]:当前的链表长度（底层跨过多少个数字）。现在前4号空间被占用，现在插入20，那么要申请第5号空间，在key数组的5号位置填20，在count数组5号位置填1，因为现在20只有一个，节点申请成功，通过随机数得到刚刚插入的节点有几层高，假设是4，那么在level[]的5位置上填4。现在假设20在第四层指向的节点编号是3，数值是30，第三层指向的节点编号是2，数值是25，那么在它的next数组中，5行（新插入节点对应key数组的位置）3列（新插入节点的第3层）填4（指向节点对应key数组位置）。5号节点（第五行）的第4层（第四列）跨过底层6个节点（填6），这个是len[][]。

建立跳表时，1号空间拥有全部的链表层数，填的值是最小值。代码如下：

public static void build() {cnt = 1;key[cnt] = Integer.MIN_VALUE;level[cnt] = MAXL;
}

扔骰子决定节点的层数

public static int random() {int ans = 1;while (Math.random() < 0.5) {ans++;}return Math.min(ans, MAXL);
}

当前在i号节点的h层，需要找的是key为num的节点，空间编号是多少。当不是到的第一层时，根据next数组判断当前位置是否有值(值对应的key中的空间编号，非0代表有值)，以及通过key判断值是否小于num，小于就根据这个位置往下跳。当来到第一层时，现在卡到第一层距离nun最近的位置，再往后判断一个是否是num,如果是，直接返回空间编号，否则就是找不到了。

    public static int find(int i, int h, int num) {while (next[i][h] != 0 && key[next[i][h]] < num) {i = next[i][h];}if (h == 1) {if (next[i][h] != 0 && key[next[i][h]] == num) {return next[i][h];} else {return 0;}}return find(i, h - 1, num);}

增加num时，分为加节点和加词频，对于加节点来说，首先是要建立好节点，然后进行加入。对于增加词频来说，注意每一层更新指针的长度。

    public static void add(int num) {if (find(1, MAXL, num) != 0) {addCount(1, MAXL, num);} else {key[++cnt] = num;count[cnt] = 1;level[cnt] = random();addNode(1, MAXL, cnt);}}public static void addCount(int i, int h, int num) {while (next[i][h] != 0 && key[next[i][h]] < num) {i = next[i][h];}if (h == 1) {count[next[i][h]]++;} else {addCount(i, h - 1, num);}len[i][h]++;}

当进行增加节点时，比较难以维护的时指针的长度，例如第4层的a节点到f节点指针长度时40（底层跨过了40个节点长度），此时要在第四层a和f之间插入节点g，总的节点数好说，为41长度，但是a到g,g到f不能够直接得出，需要下层节点的返回值，因此在设计增加节点的函数时，需要一个返回值用来表明从i号节点出发，直到把空间编号为j的节点插入，底层总共有多少数字比key[j]小。在往右走的过程中要计数（为了给上层返回），往下走的计数，返回值告诉。当到达最底层，指针前后连好，指针长度设置对。如果没到第一层，调用下层的返回值，如果插入的节点不到h层，直接长度+1，需要插入时，前后指针连接好，对于插入节点右侧的长度等于未插入之前的长度+1-下层返回值-插入的词频，左边是下方返回值+插入的词频。

public static int addNode(int i, int h, int j) {int rightCnt = 0;while (next[i][h] != 0 && key[next[i][h]] < key[j]) {rightCnt += len[i][h];i = next[i][h];}if (h == 1) {next[j][h] = next[i][h];next[i][h] = j;len[j][h] = count[next[j][h]];len[i][h] = count[next[i][h]];return rightCnt;} else {int downCnt = addNode(i, h - 1, j);if (h > level[j]) {len[i][h]++;} else {next[j][h] = next[i][h];next[i][h] = j;len[j][h] = len[i][h] + 1 - downCnt - count[j];len[i][h] = downCnt + count[j];}return rightCnt + downCnt;}}

对于删除来说，分为删除一个词频以及删除一个节点，对于删除词频来说，需要注意删除词频的同时需要删除指针的长度，对于删除节点来说，高度大于需要删除的节点时，直接减少长度，否则就是节点的正确连接以及长度=左+右-1.

    public static void remove(int num) {int j = find(1, MAXL, num);if (j != 0) {if (count[j] > 1) {removeCount(1, MAXL, num);} else {removeNode(1, MAXL, j);}}}public static void removeCount(int i, int h, int num) {while (next[i][h] != 0 && key[next[i][h]] < num) {i = next[i][h];}if (h == 1) {count[next[i][h]]--;} else {removeCount(i, h - 1, num);}len[i][h]--;}public static void removeNode(int i, int h, int j) {if (h < 1) {return;}while (next[i][h] != 0 && key[next[i][h]] < key[j]) {i = next[i][h];}if (h > level[j]) {len[i][h]--;} else {next[i][h] = next[j][h];len[i][h] += len[j][h] - 1;}removeNode(i, h - 1, j);}

对于寻找排名，如果当前节点比它小，一直往右划，以及统计指针的长度，直到找到比他小的最大值，然后往下跳，直到第一层，统计完总的个数

    public static int rank(int num) {return small(1, MAXL, num) + 1;}public static int small(int i, int h, int num) {int rightCnt = 0;while (next[i][h] != 0 && key[next[i][h]] < num) {rightCnt += len[i][h];i = next[i][h];}if (h == 1) {return rightCnt;} else {return rightCnt + small(i, h - 1, num);}}

相关文章：