0

skipListSearch()誰かがandskipListInsert()メソッドを説明してもらえますか? このコードは、Adam Drozdek の著書Data Structures and Algorithms in C++からのものです。このスキップリストでは、挿入にリストの再構築は必要なく、異なるレベルのノードの分散が適切に保たれるようにノードが生成されます。

maxLevel = 4. 15 要素の場合、必要な 1 ポインター ノードの数は 8、2 ポインター ノードは 4、3 ポインター ノードは 2、4 ポインター ノードは 1 です。ノードが挿入されるたびに、1 から 15 までの乱数 r が生成されます。r < 9 の場合、レベル 1 のノードが挿入されます。r < 13 の場合、第 2 レベルのノードが挿入されます。r < 15 の場合、それは第 3 レベルのノードです。r = 15 の場合、レベル 4 のノードが生成され、挿入されます。

#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
  } 
}
4

0 に答える 0