Search, Delete & Ordered Traversal

Insert already does the hard part, walking down through the levels to find a position. Search and delete reuse that exact same traversal.

Search

bool search(float key) {
    SkipNode* current = head;

    for (int level = currentLevel - 1; level >= 0; level--) {
        while (current->forward[level] != nullptr && current->forward[level]->key > key) {
            current = current->forward[level];
        }
    }

    current = current->forward[0]; // level 0 always lands exactly on the target, if it exists
    return current != nullptr && current->key == key;
}

This is the same "drop down a level each time the next hop would overshoot" walk from the last lesson, just without recording an update array, search doesn't need to modify anything, so there's nothing to remember on the way down.

Delete

void erase(float key) {
    std::vector<SkipNode*> update(MAX_LEVEL, head);
    SkipNode* current = head;

    for (int level = currentLevel - 1; level >= 0; level--) {
        while (current->forward[level] != nullptr && current->forward[level]->key > key) {
            current = current->forward[level];
        }
        update[level] = current;
    }

    SkipNode* target = update[0]->forward[0];
    if (target != nullptr && target->key == key) {
        for (int level = 0; level < currentLevel; level++) {
            if (update[level]->forward[level] != target) break; // target doesn't exist at this level
            update[level]->forward[level] = target->forward[level];
        }
        delete target;
    }
}

erase is insert's mirror image: find the update array the same way, but instead of splicing a new node in, unlink target from every level it actually participates in, then delete it. The break matters, once a level is reached where target isn't the next node (because target wasn't promoted that high), no higher level needs touching either.

Ordered traversal: reading the leaderboard back out

std::vector<int> leaderboard() {
    std::vector<int> order;
    SkipNode* current = head->forward[0];

    while (current != nullptr) {
        order.push_back(current->horseId);
        current = current->forward[0];
    }

    return order;
}

This is the payoff for keeping level 0 a complete, ordered linked list at all times, walking it front to back visits every horse in current rank order, 1st place first, with no sorting step required. The upper levels exist purely to make getting to a position fast, level 0 is what makes reading the whole order back out trivial.