void Skiplistinsertint searchKey const stdstring newValue a

void Skip_list::insert(int searchKey, const std::string& newValue) {

auto preds = predecessors(searchKey);

  

{//reassign value if node exists and return

auto next = preds[0]->forward[0];

if (next->key == searchKey && next != NIL) {

next->value = newValue;

return;

}

}

  

// create new node

const int newNodeLevel = randomLevel();

auto newNodePtr = makeNode(searchKey, newValue, newNodeLevel);

  

// connect pointers of predecessors and new node to respective successors

for (int i = 0; i < newNodeLevel; ++i) {

newNodePtr->forward[i] = preds[i]->forward[i];

preds[i]->forward[i] = newNodePtr;

  

}

}

void Skip_list::erase(int searchKey) {

auto preds = predecessors(searchKey);

  

//check if the node exists

auto node = preds[0]->forward[0];

if (node->key != searchKey || node == NIL) {

return;

}

  

// update pointers and delete node

for (size_t i = 0; i < nodeLevel(node); ++i) {

preds[i]->forward[i] = node->forward[i];

  

}

delete node;

}

In this code( functions to insert and delete integer in skiplist), please help me how to implement comparisons each time a integer is added and removed into the skiplist and average cost of insert and delete into the code.

Solution

void Skip_list::insert(int searchKey, const std::string& newValue) {

auto preds = predecessors(searchKey)

{

//reassign value if node exists and retur

auto next = preds[0]->forward[0];

if (next->key == searchKey && next != NIL) {

next->value = newValue;

return;

}

}

  

// create new node

const int newNodeLevel = randomLevel();

auto newNodePtr = makeNode(searchKey, newValue, newNodeLevel);

  

// connect pointers of predecessors and new node to respective successors

for (int i = 0; i < newNodeLevel; ++i) {

newNodePtr->forward[i] = preds[i]->forward[i];

preds[i]->forward[i] = newNodePtr;

  

}

}

void Skip_list::erase(int searchKey) {

auto preds = predecessors(searchKey);

//check if the node exists

auto node = preds[0]->forward[0];

if (node->key != searchKey || node == NIL) {

return;

}

  

// update pointers and delete node

for (size_t i = 0; i < nodeLevel(node); ++i) {

preds[i]->forward[i] = node->forward[i];

  

}

delete node;

}