c++如何实现一个跳表(Skip List)_c++平衡树的高效替代方案

// 跳表主类 class SkipList { private: static const int MAX_LEVEL = 16; // 最大层数 SkipListNode* head; // 头节点 int currentLevel; // 当前最大有效层数

// 随机生成节点层数
int randomLevel() {
    int level = 1;
    while (rand() % 2 == 0 && level < MAX_LEVEL) {
        ++level;
    }
    return level;
}

public: SkipList() : currentLevel(1) { head = new SkipListNode(-1, MAX_LEVEL); }

// 查找插入位置，记录每层最后一个小于num的节点
for (int i = currentLevel - 1; i >= 0; --i) {
    while (curr->forward[i] && curr->forward[i]->val < num) {
        curr = curr->forward[i];
    }
    update[i] = curr;
}

int newNodeLevel = randomLevel();
SkipListNode* newNode = new SkipListNode(num, newNodeLevel);

// 更新各层指针
for (int i = 0; i < newNodeLevel; ++i) {
    newNode->forward[i] = update[i]->forward[i];
    update[i]->forward[i] = newNode;
}

// 更新当前最大层数
if (newNodeLevel > currentLevel) {
    currentLevel = newNodeLevel;
}

}

for (int i = currentLevel - 1; i >= 0; --i) {
    while (curr->forward[i] && curr->forward[i]->val < num) {
        curr = curr->forward[i];
    }
    update[i] = curr;
}

curr = curr->forward[0];
if (!curr || curr->val != num) return false;

// 断开各层指针
for (int i = 0; i < currentLevel; ++i) {
    if (update[i]->forward[i] != curr) break;
    update[i]->forward[i] = curr->forward[i];
}

delete curr;

// 降低当前层数（可选优化）
while (currentLevel > 1 && head->forward[currentLevel-1] == nullptr) {
    --currentLevel;
}

return true;

}