Data Structures and Algorithms in C++

Adam Drozdek

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.

More on Amazon.com

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] == 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
  } 
}