2016 August 20

跳表

跳表是一种随机化数据结构，其功能和性能可媲美平衡树，但实现却要简单很多，在redis和LevelDB中有大量使用。下面以跳表实现集合为例进行说明，要求如下：

结构定义

跳表是在链表的基础上每个节点增加了多级指针形成的，先定义节点：

typedef struct Node {
    int key;
    int height;
    struct Node *next[0];
}Node;

这里用到了变长数组，它需要C99标准的支持。有了节点定义后可定义跳表：

typedef struct SkipList {
    int size;
    int height;
    Node *head;
}SkipList;

创建跳表

一般来讲，应根据数据量大小定义合理的跳表最大层数，以节省空间，并且不影响性能。创建跳表要做的主要工作就是初始化满层的表头。

Node* CreateNode(int key, int height) {
    int i;
    Node *p = malloc(sizeof(Node) + sizeof(Node*) * (1 + height));
    p->key = key;
    p->height= height;
    for (i = 0; i <= height; i++)
        p->next[i] = NULL;
    return p;
}
SkipList* CreateList(void) {
    srand(time(NULL)); /* prepare for rand() */
    SkipList *sl = malloc(sizeof(SkipList));
    sl->size = sl->height = 0;
    sl->head = CreateNode(INT_MIN, MAX_HEIGHT);
    return sl;
}

插入元素

跳表的插入与链表类似，区别在于节点是有高度的，为了近可能得达到平衡，理想的高度随机性应满足几何分布，可用类似投硬币的方法来模拟，这也是跳表随机化的关键。

int PickHeight(void) {
    int h = 0;
    while (rand() & 1)
        h += 1;
    return h <= MAX_HEIGHT ? h : MAX_HEIGHT;
}

在确定待插入元素的高度后，接下来便要找插入位置，由于插入时可能会影响到前面节点的next指针，可在找插入位置时顺带把需要变更的节点记录下来。

Node* Insert(SkipList *sl, int key) {
    Node *stack[MAX_HEIGHT+1], *p = sl->head;
    int i, j, h = sl->height, idx = 0;
    
    while (h >= 0) {
        if (NULL == p->next[h] || p->next[h]->key > key) {
            stack[idx++] = p;
            h -= 1;
        } else if (p->next[h]->key < key) {
            p = p->next[h];
        } else { /* already exist */
            return p->next[h];
        }
    }

    h = PickHeight();
    p = CreateNode(key, h);
    for (i = 0, j = idx - 1; i <= h && j >= 0; i++, j--) {
        p->next[i] = stack[j]->next[i];
        stack[j]->next[i] = p;
    }
    while (sl->height < h) {
        sl->height += 1;
        sl->head->next[sl->height] = p;
    }
    sl->size += 1;
    return p;
}

删除元素

删除与插入类似，在找待删除元素过程中记录下可能需要变更next指针的节点，区别在于：插入时可能会多记高层节点，因插入节点的高度不够而导致无需修改；而删除只记next指针指向待删除节点的节点，所有这些节点的next指针都必须修改。

int Delete(SkipList *sl, int key) {
    Node *stack[MAX_HEIGHT+1], *p = sl->head;
    int i, j, idx = 0, h = sl->height;

    while (h >= 0) {
        if (NULL == p->next[h] || p->next[h]->key > key) {
            h -= 1;
        } else if (p->next[h]->key < key) {
            p = p->next[h];
        } else {
            stack[idx++] = p;
            h -= 1;
        }
    }

    if (0 == idx) return 0;  /* not exist */
    p = p->next[0]; /* now p is the node to be deleted */
    for (i = 0, j = idx - 1; j >= 0; i++, j--) {
        stack[j]->next[i] = p->next[i];
        if (INT_MIN == stack[j]->key && NULL == p->next[i]) /* no elements in this level */
            sl->height -= 1;
    }
    free(p);
    sl->size -= 1;
    return 1;
}

查找元素

查找比插入和删除容易多了，从表头顶开始，优先往右、不行就往下走。

Node* Find(SkipList *sl, int key) {
    int h = sl->height;
    Node *p = sl->head;
    while (h >= 0) {
        if (p->next[h] && p->next[h]->key <= key)
            p = p->next[h];
        else h -= 1;
    }
    return p->key == key ? p : NULL;
}

跳表大小

int GetListSize(const SkipList *sl) {
    return sl->size;
}

释放跳表

void FreeList(SkipList *sl) {
    Node *p = sl->head, *q;
    while (p) {
        q = p;
        p = p->next[0];
        free(q);
    }
    free(sl);
}
Table of Contents