 ## Data Structures and Algorithms in C++

Mentioned 1

Strengthen your understanding of data structures and their algorithms for the foundation you need to successfully design, implement and maintain virtually any software system. Theoretical, yet practical, DATA STRUCUTRES AND ALGORITHMS IN C++, 4E by experienced author Adam Drosdek highlights the fundamental connection between data structures and their algorithms, giving equal weight to the practical implementation of data structures and the theoretical analysis of algorithms and their efficiency. This edition provides critical new coverage of treaps, k-d trees and k-d B-trees, generational garbage collection, and other advanced topics such as sorting methods and a new hashing technique. Abundant C++ code examples and a variety of case studies provide valuable insights into data structures implementation. DATA STRUCTURES AND ALGORITHMS IN C++ provides the balance of theory and practice to prepare readers for a variety of applications in a modern, object-oriented paradigm. Important Notice: Media content referenced within the product description or the product text may not be available in the ebook version.

Mentioned in questions and answers.

Can someone please explain the `skipListSearch()` and `skipListInsert()` method? The code is from Adam Drozdek's book Data Structures and Algorithms in C++. In this skiplist, inserting does not require list restructuring and nodes are generated so that the distribution of the nodes on different levels is kept adequate.

`maxLevel = 4`. For 15 elements, the required number of one-pointer nodes is eight, two-pointer nodes is four, three-pointer nodes is two, and four-pointer nodes is one. Each time a node is inserted, a random number r between 1 and 15 is generated. If r < 9, then a node of level one is inserted. If r < 13, a second-level node is inserted. If r < 15, it is a third-level node. If r = 15, the node of level four is generated and inserted.

``````#include <iostream>
#include <cstdlib>
using namespace std;
const int maxLevel = 4;

template<class T>
class SkipListNode{

public:
SkipListNode(){}
T key;
SkipListNode **next;

};

template<class T>
class SkipList{

public:
SkipList();
bool isEmpty() const;
void choosePowers();
int chooseLevel();
T* skipListSearch(const T&);
void skipListInsert(const T&);

private:
typedef SkipListNode<T> *nodePtr;
nodePtr root[maxLevel];
int powers[maxLevel];
};

template<class T>
SkipList<T>::SkipList(){
for (int i = 0 ; i < maxLevel ; i++){
root[i] = 0;
}
}

template<class T>
bool SkipList<T>::isEmpty() const{
return root == 0;
}

template<class T>
void SkipList<T>::choosePowers(){
powers[maxLevel - 1] = (2 << (maxLevel - 1)) - 1;         // 2^maxLevel - 1
for (int i = maxLevel - 2, j = 0 ; i >= 0 ; i--, j++){
powers[i] = powers[i + 1] - (2 << j);                   // 2^(j + 1)
}
}

template<class T>
int SkipList<T>::chooseLevel(){
int i , r = rand() % powers[maxLevel - 1] + 1;
for ( i = 1 ; i < maxLevel ; i++)
if (r < powers[i])
return i - 1;
return i - 1;
}

template<class T>
T* SkipList<T>::skipListSearch(const T& key){
if (isEmpty()) return 0;
nodePtr prev , curr;
int lvl;
for (lvl = maxLevel - 1 ; lvl >= 0 && !root[lvl]; lvl--);            // level
prev = curr = root[lvl];
while(true){
if (key == curr->key)
return &curr->key;
else if (key < curr->key){
if (lvl == 0)
return 0;
else if (curr == root[lvl])
curr = root[--lvl];
else curr = *(prev->next + --lvl);
}
else{
prev = curr;
if (*(curr->next + lvl) != 0)
curr = *(curr->next + lvl);
else{
for (lvl--; lvl >= 0 && *(curr->next + lvl) == 0; lvl--);
if (lvl >= 0)
curr = *(curr->next + lvl);
else return 0;
}
}
}
}

template<class  T>
void    SkipList<T>::skipListInsert(const   T&  key){
nodePtr curr[maxLevel] , prev[maxLevel] , newNode;
int lvl , i;
curr[maxLevel - 1] = root[maxLevel - 1];
prev[maxLevel - 1] = 0;
for (lvl = maxLevel - 1; lvl >= 0 ; lvl--){
while (curr[lvl] && curr[lvl]->key < key){         // go to next
prev[lvl] = curr[lvl];                          // if smaller
curr[lvl] = *(curr[lvl]->next + lvl);
}

if (curr[lvl] && curr[lvl]->key == key)          // dont include
return;                                      // duplicates
if (lvl > 0)                                 // go one level down
if (prev[lvl] == 0){                     // if not the lowest
curr[lvl - 1] = root[lvl - 1];         // level , using a link
prev[lvl - 1] = 0;                  // either from the root
}
else{                                         // or from the predecessor
curr[lvl - 1] = *(prev[lvl]->next + lvl -1);
prev[lvl - 1] = prev[lvl];
}
}

lvl = chooseLevel();                          // generate randomly level for newNode
newNode = new SkipListNode<T>;
newNode->next = new nodePtr[sizeof(nodePtr) * (lvl -1)];
newNode->key = key;
for (i = 0 ; i <= lvl; i++){                    // initialize next fields of
*(newNode->next + i) = curr[i];                 // newNode and reset to newNode
if (prev[i] == 0)                                // either fields of the root
root[i] = newNode;                         // or next fields of newNode's
else *(prev[i]->next + i) = newNode;           // predecessors
}
}
``````
Realated tags