skip-list
unknown
c_cpp
2 months ago
3.4 kB
3
Indexable
Never
#include <iostream> #include <vector> #include <ctime> #include <cstdlib> const float P = 0.5; const int MAX_LEVEL = 16; template<typename T> class Node { public: T value; std::vector<Node<T>*> forward; Node(int level, const T &value) : value(value), forward(level, nullptr) {} }; template<typename T> class SkipList { public: SkipList() : level(0), header(new Node<T>(MAX_LEVEL, T())) { std::srand(std::time(nullptr)); } ~SkipList() { Node<T>* curr = header->forward[0]; while (curr != nullptr) { Node<T>* tmp = curr; curr = curr->forward[0]; delete tmp; } delete header; } void insert(const T &value) { Node<T>* curr = header; std::vector<Node<T>*> update(MAX_LEVEL, nullptr); for (int i = level; i >= 0; --i) { while (curr->forward[i] != nullptr && curr->forward[i]->value < value) { curr = curr->forward[i]; } update[i] = curr; } int newLevel = randomLevel(); if (newLevel > level) { for (int i = level + 1; i <= newLevel; ++i) { update[i] = header; } level = newLevel; } Node<T>* newNode = new Node<T>(newLevel + 1, value); for (int i = 0; i <= newLevel; ++i) { newNode->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newNode; } } bool contains(const T &value) { Node<T>* curr = header; for (int i = level; i >= 0; --i) { while (curr->forward[i] != nullptr && curr->forward[i]->value < value) { curr = curr->forward[i]; } } curr = curr->forward[0]; return curr != nullptr && curr->value == value; } void remove(const T &value) { Node<T>* curr = header; std::vector<Node<T>*> update(MAX_LEVEL, nullptr); for (int i = level; i >= 0; --i) { while (curr->forward[i] != nullptr && curr->forward[i]->value < value) { curr = curr->forward[i]; } update[i] = curr; } curr = curr->forward[0]; if (curr != nullptr && curr->value == value) { for (int i = 0; i <= level; ++i) { if (update[i]->forward[i] != curr) { break; } update[i]->forward[i] = curr->forward[i]; } delete curr; while (level > 0 && header->forward[level] == nullptr) { level--; } } } private: int level; Node<T>* header; int randomLevel() { int lvl = 0; while (std::rand() / static_cast<float>(RAND_MAX) < P && lvl < MAX_LEVEL) { lvl++; } return lvl; } }; int main() { SkipList<int> list; list.insert(3); list.insert(6); list.insert(7); list.insert(9); list.insert(12); std::cout << "Contains 3: " << list.contains(3) << std::endl; std::cout << "Contains 4: " << list.contains(4) << std::endl; list.remove(6); std::cout << "Contains 6: " << list.contains(6) << std::endl; return 0; }