hashtree.h

hashtree算发

#include<iostream.h>

struct Content {
/********************************************************
*** input your content in each node of hash tree here ***
********************************************************/
  int a;
};

class HashTree;  // forward declaration

// Node of a hash tree
class TreeNode {
public:
  TreeNode(bool l, int d, int n);
  ~TreeNode();
  bool isLeaf() const { return (index!=NULL); }
  int hashFunc(int i);
  TreeNode* transver(const IntList& i);
  void insert(const IntList& ss);
  void split();
  void resize(int newsize);
  void remove(const IntList& ss, int& no_ss);
  void show() const;
  void convert2array(IntList*& ia, int& idx_ss) const;
  void setCon(const IntList& ss, const Content& es);

  IntList** index; // Array of indexs (leaf node)
  TreeNode** child;   // Array of pointers to children (internal node)
  Content* con;       // contents of the node
  int len;            // No of leaf node
  int depth;          // Depth of current node
  int brFactor;       // Branching factor
};

// A hash tree
class HashTree {
public:
  HashTree(int n, int d);
  ~HashTree();
  void insert(const IntList& ss);
  void remove(const IntList& ss);
  void show() const { root->show(); }
  bool exist(const IntList& il) const;
  void convert2array(IntList*& ia, int& idx_ss) const;
  void locktree();
  void setCon(const IntList& ss, const Content& es);
  Content findStat(const IntList& ss) const;
  
  int get_dim() const { return dim; }
  int get_no_ss() const { return no_ss; }

private:
  int brFactor;    // Branching factor
  int dim;         // Dimension of indexs
  int no_ss;       // No of nodes stored
  
  TreeNode* root;  // Root of hash tree
};