Προς το περιεχόμενο

δομη splay tree

Crawl_From_Death

Από τον Crawl_From_Death
στο Προγραμματισμός

Προτεινόμενες αναρτήσεις

Crawl_From_Death Experienced

Crawl_From_Death

Δημοσ.
Δημοσ.

Καλησπερα σας,

 

μηπως υπαρχει καπου ή εχετε πετυχει καπου την δομη που πρεπει να εχει η δεντροποιηση splay tree? θα πρεπει να την χρησιμοποιησω σαν βασικη δομη σε εναν αλγοριθμο digging και δεν μπορω να ξεκινησω καν χωρις να γνωριζω την δομη.

 

Αρχικα θα γινει εισαγωγη δεδομενων σε αυτο το δεντρο.

 

Απανταχου παροντες τζιμανια του προγραμματισμου δωστε τα φωτα σας

 

PS. Δεν μπορω να βγαλω ακρη, δεν ξερω απο που θα ξεκινησω!

V.I.Smirnov Experienced

V.I.Smirnov

Δημοσ.
Δημοσ.

Χμμ... εγώ τα ξέρω (ή μάλλον τα ήξερα...)

Mιαν ευγενική προσφορά από εμένα λοιπόν :

 

V.I.Smirnov

 

>
/*
   *******************************
   *                             *
   *   a trial SplayTree class   *
   *                             *
   *      SplayTree.h file       *
   *                             *
   *******************************
   *       (c) V.I.Smirnov       *
   *******************************



  In construction use an ITEM_NOT_FOUND object to signal that Find failed
 
  ----------------- memmeber functions -----------------

  void insert(x)        :  Insert x
  void remove(x)        :  Remove x
  Comparable find(x)    :  Return item that matches x
  Comparable findMin()  :  Return smallest item
  Comparable findMax()  :  Return largest item
  boolean isEmpty()     :  Return true if empty; else false
  void makeEmpty()      :  Remove all items
  void printTree()      :  Print tree in sorted order
*/


#ifndef SPLAY_TREE_H_
#define SPLAY_TREE_H_

#include <iostream>     // (for NULL definition)



template <class Comparable>
class SplayTree;

template <class Comparable>
class BinaryNode
{
  Comparable  element;
  BinaryNode *left;
  BinaryNode *right;

  BinaryNode() : left(NULL), right(NULL) { }
  BinaryNode(const Comparable & theElement, BinaryNode *lt, BinaryNode *rt)
    : element(theElement), left(lt), right(rt) { }

  friend class SplayTree<Comparable>;
};


template <class Comparable>
class SplayTree
{
public:
  explicit SplayTree(const Comparable & notFound);
  SplayTree(const SplayTree & rhs);
  ~SplayTree();

  const Comparable & findMin();
  const Comparable & findMax();
  const Comparable & find(const Comparable & x);
  bool isEmpty() const;
  void printTree() const;

  void makeEmpty();
  void insert(const Comparable & x);
  void remove(const Comparable & x);

  const SplayTree & operator=(const SplayTree & rhs);

private:
  BinaryNode<Comparable> *root;
  BinaryNode<Comparable> *nullNode;
  const Comparable ITEM_NOT_FOUND;

  const Comparable & elementAt(BinaryNode<Comparable> *t) const;

  void reclaimMemory(BinaryNode<Comparable> * t) const;
  void printTree(BinaryNode<Comparable> *t) const;
  BinaryNode<Comparable> * clone(BinaryNode<Comparable> *t) const;

      // Tree manipulations
  void rotateWithLeftChild(BinaryNode<Comparable> * & k2) const;
  void rotateWithRightChild(BinaryNode<Comparable> * & k1) const;
  void splay(const Comparable & x, BinaryNode<Comparable> * & t) const;
};

#endif



/*
   *******************************
   *                             *
   *   a trial SplayTree class   *
   *                             *
   *     SplayTree.cpp file      *
   *                             *
   *******************************
   *       (c) V.I.Smirnov       *
   *******************************
*/

#include <iostream>
#include "SplayTree.h"


/*
   Construct the tree.
*/
template <class Comparable>
SplayTree<Comparable>::SplayTree(const Comparable & notFound)
: ITEM_NOT_FOUND(notFound)
{
  nullNode = new BinaryNode<Comparable>;
  nullNode->left = nullNode->right = nullNode;
  nullNode->element = notFound;
  root = nullNode;
}



/* 
   Copy constructor.
*/
template <class Comparable>
SplayTree<Comparable>::SplayTree(const SplayTree<Comparable> & rhs)
: ITEM_NOT_FOUND(rhs.ITEM_NOT_FOUND)
{
  nullNode = new BinaryNode<Comparable>;
  nullNode->left = nullNode->right = nullNode;
  nullNode->element = ITEM_NOT_FOUND;
  root = nullNode;
  *this = rhs;
}



/*
   Destructor.
*/
template <class Comparable>
SplayTree<Comparable>::~SplayTree()
{
  makeEmpty();
  delete nullNode;
}



/*
  Insert x into the tree.
*/
template <class Comparable>
void SplayTree<Comparable>::insert(const Comparable & x)
{
  static BinaryNode<Comparable> *newNode = NULL;

  if(newNode == NULL)
      newNode = new BinaryNode<Comparable>;
  newNode->element = x;

  if(root == nullNode)
  {
      newNode->left = newNode->right = nullNode;
      root = newNode;
  }
  else
  {
      splay(x, root);
      if(x < root->element)
      {
          newNode->left = root->left;
          newNode->right = root;
          root->left = nullNode;
          root = newNode;
      }
      else
      if(root->element < x)
      {
          newNode->right = root->right;
          newNode->left = root;
          root->right = nullNode;
          root = newNode;
      }
      else
        return;
  }
  newNode = NULL;   // in next insert will call new
}



/*
   Remove x from the tree.
*/
template <class Comparable>
void SplayTree<Comparable>::remove(const Comparable & x)
{
  BinaryNode<Comparable> *newTree;

      // If x is found, it will be at the root
  splay(x, root);
  if(root->element != x)
      return;   // Item not found; do nothing

  if(root->left == nullNode)
      newTree = root->right;
  else
  {
      // Find the maximum in the left subtree
      // Splay it to the root; and then attach right child
      newTree = root->left;
      splay(x, newTree);
      newTree->right = root->right;
  }
  delete root;
  root = newTree;
}



/*
   Find the smallest item in the tree.
   Not the most efficient implementation (uses two passes), but has correct amortized behavior.
   Return the smallest item or ITEM_NOT_FOUND if empty.
*/
template <class Comparable>
const Comparable & SplayTree<Comparable>::findMin()
{
  if(isEmpty())
      return ITEM_NOT_FOUND;

  BinaryNode<Comparable> *ptr = root;

  while(ptr->left != nullNode)
      ptr = ptr->left;

  splay(ptr->element, root);
  return ptr->element;
}



/*
  Find the largest item in the tree.
  Not the most efficient implementation (uses two passes), but has correct amortized behavior.
  Return the largest item or ITEM_NOT_FOUND if empty.
*/
template <class Comparable>
const Comparable & SplayTree<Comparable>::findMax()
{
  if(isEmpty())
      return ITEM_NOT_FOUND;

  BinaryNode<Comparable> *ptr = root;

  while(ptr->right != nullNode)
      ptr = ptr->right;

  splay(ptr->element, root);
  return ptr->element;
}

/*
  Find item x in the tree.
  Return the matching item or ITEM_NOT_FOUND if not found.
*/
template <class Comparable>
const Comparable & SplayTree<Comparable>::find(const Comparable & x)
{
  if(isEmpty())
      return ITEM_NOT_FOUND;
  splay(x, root);
  if(root->element != x)
      return ITEM_NOT_FOUND;

  return root->element;
}

/*
   Make the tree logically empty.
*/
template <class Comparable>
void SplayTree<Comparable>::makeEmpty()
{
/* 
-----------------------------------
Comment this out, because it is prone to excessive 
recursion on degenerate trees. 
Use alternate algorithm.

  reclaimMemory(root);
  root = nullNode;
-----------------------------------
*/
  findMax();        // Splay max item to root
  while(!isEmpty())
      remove(root->element);
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
template <class Comparable>
bool SplayTree<Comparable>::isEmpty() const
{
  return root == nullNode;
}



/*
  Print the tree contents in sorted order.
*/
template <class Comparable>
void SplayTree<Comparable>::printTree() const
{
  if(isEmpty())
      cout << "Empty tree" << endl;
  else
      printTree(root);
}



/*
  Deep copy.
*/
template <class Comparable>
const SplayTree<Comparable> &
SplayTree<Comparable>::operator=(const SplayTree<Comparable> & rhs)
{
  if(this != &rhs)
  {
      makeEmpty();
      root = clone(rhs.root);
  }

  return *this;
}

/*
  Internal method to perform a top-down splay.
  The last accessed node becomes the new root.
  This method may be overridden to use a different splaying algorithm, 
  however, the splay tree code depends on the accessed item going to the root.
    x is the target item to splay around.
    t is the root of the subtree to splay.
*/
template <class Comparable>
void SplayTree<Comparable>::splay(const Comparable & x,
                                 BinaryNode<Comparable> * & t) const
{
  BinaryNode<Comparable> *leftTreeMax, *rightTreeMin;
  static BinaryNode<Comparable> header;

  header.left = header.right = nullNode;
  leftTreeMax = rightTreeMin = &header;

  nullNode->element = x;   // Guarantee a match

  for(; 
      if(x < t->element)
      {
          if(x < t->left->element)
              rotateWithLeftChild(t);
          if(t->left == nullNode)
              break;
          // Link Right
          rightTreeMin->left = t;
          rightTreeMin = t;
          t = t->left;
      }
      else if(t->element < x)
      {
          if(t->right->element < x)
              rotateWithRightChild(t);
          if(t->right == nullNode)
              break;
          // Link Left
          leftTreeMax->right = t;
          leftTreeMax = t;
          t = t->right;
      }
      else
          break;

  leftTreeMax->right = t->left;
  rightTreeMin->left = t->right;
  t->left = header.right;
  t->right = header.left;
}



/*
  Rotate binary tree node with left child.
*/
template <class Comparable>
void SplayTree<Comparable>::rotateWithLeftChild(BinaryNode<Comparable> * & k2) const
{
  BinaryNode<Comparable> *k1 = k2->left;
  k2->left = k1->right;
  k1->right = k2;
  k2 = k1;
}



/*
  Rotate binary tree node with right child.
*/
template <class Comparable>
void SplayTree<Comparable>::rotateWithRightChild(BinaryNode<Comparable> * & k1) const
{
  BinaryNode<Comparable> *k2 = k1->right;
  k1->right = k2->left;
  k2->left = k1;
  k1 = k2;
}



/*
  Internal method to print a subtree t in sorted order.
  WARNING: this is prone to running out of stack space.
*/
template <class Comparable>
void SplayTree<Comparable>::printTree(BinaryNode<Comparable> *t) const
{
  if(t != t->left)
  {
      printTree(t->left);
      cout << t->element << endl;
      printTree(t->right);
  }
}



/*
  Internal method to reclaim internal nodes in subtree t.
  WARNING: this is prone to running out of stack space.
*/
template <class Comparable>
void SplayTree<Comparable>::reclaimMemory(BinaryNode<Comparable> * t) const
{
  if(t != t->left)
  {
      reclaimMemory(t->left);
      reclaimMemory(t->right);
      delete t;
  }
}

/*
  Internal method to clone subtree.
  WARNING: this is prone to running out of stack space.
*/
template <class Comparable>
BinaryNode<Comparable> *
SplayTree<Comparable>::clone(BinaryNode<Comparable> * t) const
{
  if(t == t->left)  // Cannot test against nullNode !
     return nullNode;
  else
     return new BinaryNode<Comparable>(t->element, clone(t->left), clone(t->right));
}



/*
   *******************************
   *                             *
   *   a trial SplayTree class   *
   *                             *
   *       test.cpp file         *
   *                             *
   *******************************
   *       (c) V.I.Smirnov       *
   *******************************
*/


#include <iostream>
#include "SplayTree.h"
#include "SplayTree.cpp"

using namespace std;


// Test program
int main()
{
  const int ITEM_NOT_FOUND = -9999;
  SplayTree<int> t(ITEM_NOT_FOUND);

  int i, NUMS = 6000,
         GAP  = 37;

  cout << "Checking... (no more output means success)" << endl;

  for(i = GAP; i != 0; i = (i + GAP) % NUMS)
      t.insert(i);

  for(i = 1; i < NUMS; i+= 2)
      t.remove(i);

  if(NUMS < 40)
      t.printTree();
  if(t.findMin() != 2 || t.findMax() != NUMS - 2)
      cout << "FindMin or FindMax error !" << endl;

  for(i = 2; i < NUMS; i+=2)
      if(t.find(i) != i)
          cout << "Εrror 1 in Find !" << endl;

  for(i = 1; i < NUMS; i+=2)
  {
      if(t.find(i) != ITEM_NOT_FOUND)
          cout << "Error 2 in Find !" << endl;
  }

  SplayTree<int> t2(ITEM_NOT_FOUND);
  t2 = t;

  for(i = 2; i < NUMS; i+=2)
      if(t2.find(i) != i)
          cout << "Error 1 in Find !" << endl;

  for(i = 1; i < NUMS; i+=2)
  {
      if(t2.find(i) != ITEM_NOT_FOUND)
          cout << "Error 2 in Find !" << endl;
  }

  return 0;
}

 

 

Έχω μελετήσει τα AVL και τα Splay trees πριν πολύ καιρό.

Eπίσης είχα διαβάσει και τα B και Red-Black (αλλά δίχως να γράψω κώδικα).

Τα παραπάνω είναι από δοκιμές μου σε μια υλοποίηση splay tree.

Το δοκιμαστικό πρόγραμμα γεμίζει ένα splay tree και ψάχνει κάποια στοιχεία σε αυτό.

 

Το χαρακτηριστικό των splay trees είναι ο amortized time που έχουν και η θεωρία τους αφορά κυρίως αυτό.

Ωστόσο, αν δεν σε περιορίζει κάτι, καλύτερα να χρησιμοποιήσεις την δομή map της STL που ενδογενώς

υλοποιείται με Red-Black trees τα οποία είναι τα καλύτερα όλων και έχει έτοιμες πολλές ευκολίες.

 

Καλή συνέχεια.

 

-

Crawl_From_Death Experienced

Crawl_From_Death

Δημοσ.
  • Μέλος
Δημοσ.

Το ελαχιστο που μπορω να σου πω ειναι ενα μεγαλο ευχαριστω. θα μελετησω πολυ τον κωδικα για να καταλαβω την λογικη του, μελετωντας παραλληλα και σε θεωρητικο περιβαλλον την ολη δομη.

 

Και παλι σε ευχαριστω παρα πολυ.

Αρχειοθετημένο

Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.

Προς την λίστα θεμάτων
  • Δημιουργία νέου...