Created
April 21, 2014 04:38
-
-
Save ankitdbst/11132391 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| ** Skip Lists data structures. Equivalent to Balanced Binary Trees | |
| ** Insert: O(LogN) | |
| ** Remove: O(LogN) | |
| ** Search: O(LogN) on average (worst case: O(N)) | |
| */ | |
| #include <vector> | |
| #include <ctime> | |
| #include <cstdlib> | |
| using namespace std; | |
| class SkipLists | |
| { | |
| struct node | |
| { | |
| int value; | |
| vector<node*> next; | |
| node(int v, int level) | |
| { | |
| value = v; | |
| next.resize(level); | |
| for (int i = 0; i < level; ++i) | |
| next[i] = NULL; | |
| } | |
| }; | |
| node *_head; | |
| int _level; | |
| public: | |
| /* | |
| ** Random number with 32 bits so 33 levels, every element should be added to 0th level. | |
| */ | |
| SkipLists() | |
| { | |
| srand(time(NULL)); | |
| _head = new node(0, 33); | |
| _level = 33; | |
| } | |
| /* | |
| ** Insert element to all levels <= levels | |
| */ | |
| void insert(int v) | |
| { | |
| int random = rand(); | |
| int level = 0; | |
| for (int r = random; r & 1 == 1; r >>= 1) | |
| level++; | |
| node *n = new node(v, level+1); | |
| node *curr = _head; | |
| for (int i = _level-1; i >= 0; --i) | |
| { | |
| while (curr->next[i] != NULL) | |
| { | |
| if (curr->next[i]->value > v) | |
| break; | |
| curr = curr->next[i]; | |
| } | |
| if (i <= level) | |
| { | |
| n->next[i] = curr->next[i]; | |
| curr->next[i] = n; | |
| } | |
| } | |
| } | |
| /* | |
| ** Search is similar to Binary search, we move down once the next element is larger than search value | |
| */ | |
| bool search(int v) | |
| { | |
| node *curr = _head; | |
| for (int i = _level-1; i >= 0; --i) | |
| { | |
| while (curr->next[i] != NULL) | |
| { | |
| if (curr->next[i]->value == v) | |
| return true; | |
| if (curr->next[i]->value > v) | |
| break; | |
| curr = curr->next[i]; | |
| } | |
| } | |
| return false; | |
| } | |
| /* | |
| ** Remove removes the element from all the levels | |
| ** Calls delete in the end to remove the node completely (from the bottom level also) | |
| */ | |
| bool remove(int v) | |
| { | |
| node *curr = _head; | |
| bool found = false; | |
| node *temp; | |
| for (int i = _level-1; i >= 0; --i) | |
| { | |
| while (curr->next[i] != NULL) | |
| { | |
| if (curr->next[i]->value == v) | |
| { | |
| found = true; | |
| temp = curr->next[i]; | |
| curr->next[i] = curr->next[i]->next[i]; | |
| break; | |
| } | |
| if (curr->next[i]->value > v) | |
| break; | |
| curr = curr->next[i]; | |
| } | |
| } | |
| if (found) delete temp; | |
| return found; | |
| } | |
| }; | |
| /* | |
| ** Usage: | |
| ** | |
| ** SkipLists s; | |
| ** | |
| ** s.insert(2); | |
| ** s.search(2); | |
| ** s.remove(2); | |
| ** | |
| */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment