Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jun 26th, 2012  |  syntax: C++  |  size: 3.19 KB  |  hits: 15  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #ifndef PERSISTENTBSTREE_H
  2. #define PERSISTENTBSTREE_H
  3. #include <vector>
  4.  
  5. #define ptr std::shared_ptr<Node>
  6. #define newptr std::make_shared<Node>()
  7.  
  8. struct Node {
  9.         ptr left;
  10.         ptr right;
  11.         int value;
  12.  
  13.         Node() {
  14.                 left = NULL;
  15.                 right = NULL;
  16.         }
  17. };
  18.  
  19. struct BSTree {
  20.         ptr root;
  21.  
  22.         BSTree() {
  23.                 root = NULL;
  24.         }
  25.  
  26.         BSTree(ptr newroot) {
  27.                 root = newroot;
  28.         }
  29.  
  30.         bool find(int x) {
  31.                 ptr t = root;
  32.                 while (t != NULL) {
  33.                         if (t->value == x) {
  34.                                 return true;
  35.                         }
  36.                         if (t->value < x) {
  37.                                 t = t->right;
  38.                         }
  39.                         else if (t->value > x) {
  40.                                 t = t->left;
  41.                         }
  42.                 }
  43.                 return false;
  44.         }
  45.  
  46.         BSTree copy(BSTree bst) {
  47.                 ptr t = bst.root;
  48.                 return BSTree(t);
  49.         }
  50.  
  51.         BSTree insert(int x) {
  52.                 if (find(x)) {
  53.                         return BSTree(root);
  54.                 }
  55.                 ptr t = root;
  56.                 ptr newt = newptr;
  57.                 ptr newroot = newt;
  58.                 while (t != NULL) {
  59.                         if (t->value < x) {
  60.                                 newt->value = t->value;
  61.                                 newt->left = t->left;
  62.                                 newt->right = newptr;
  63.                                 newt = newt->right;
  64.                                 t = t->right;
  65.                         }
  66.                         else if (t->value > x) {
  67.                                 newt->value = t->value;
  68.                                 newt->right = t->right;
  69.                                 newt->left = newptr;
  70.                                 newt = newt->left;
  71.                                 t = t->left;
  72.                         }
  73.                 }
  74.                 newt->value = x;
  75.                 BSTree bst(newroot);
  76.                 return bst;
  77.         }
  78.  
  79.         BSTree remove(int x) {
  80.                 if (!find(x)) {
  81.                         return BSTree(root);
  82.                 }
  83.                 ptr t = root;
  84.                 ptr newt = newptr;
  85.                 ptr prevt;
  86.                 ptr newroot = newt;
  87.                 //finding t, where t->value = x;
  88.                 while (t->value != x) {
  89.                         if (t->value < x) {
  90.                                 newt->value = t->value;
  91.                                 newt->left = t->left;
  92.                                 newt->right = newptr;
  93.                                 prevt = newt;
  94.                                 newt = newt->right;
  95.                                 t = t->right;
  96.                         }
  97.                         else if (t->value > x) {
  98.                                 newt->value = t->value;
  99.                                 newt->right = t->right;
  100.                                 newt->left = newptr;
  101.                                 prevt = newt;
  102.                                 newt = newt->left;
  103.                                 t = t->left;
  104.                         }
  105.                 }
  106.                 //if t have no children
  107.                 if (t->left == NULL && t->right == NULL) {
  108.                         if (prevt->right == newt) {
  109.                                 prevt->right = NULL;
  110.                         }
  111.                         else if (prevt->left == newt) {
  112.                                 prevt->left = NULL;
  113.                         }
  114.                         return BSTree(newroot);
  115.                 }
  116.                 //if t have one children
  117.                 if (t->left != NULL && t->right == NULL) {
  118.                         if (prevt->right == newt) {
  119.                                 prevt->right = t->left;
  120.                         }
  121.                         else if (prevt->left == newt) {
  122.                                 prevt->left = t->left;
  123.                         }
  124.                         return BSTree(newroot);
  125.                 }
  126.                 if (t->right != NULL && t->left == NULL) {
  127.                         if (prevt->right == newt) {
  128.                                 prevt->right = t->right;
  129.                         }
  130.                         else if (prevt->left == newt) {
  131.                                 prevt->left = t->right;
  132.                         }
  133.                         return BSTree(newroot);
  134.                 }
  135.                 //if t have two children
  136.                 ptr mint = newptr;
  137.                 newt->right = mint;
  138.                 newt->left = t->left;
  139.                 t = t->right;
  140.                 while (t->left != NULL) {
  141.                         mint->value = t->value;
  142.                         mint->right = t->right;
  143.                         mint->left = newptr;
  144.                         prevt = mint;
  145.                         mint = mint->left;
  146.                         t = t->left;
  147.                 }
  148.                 newt->value = t->value;
  149.                 prevt->left = NULL;
  150.                 return BSTree(newroot);
  151.         }
  152. };
  153.  
  154. struct PersistentBSTree {
  155.         std::vector<BSTree> trees;
  156.  
  157.         PersistentBSTree() {
  158.                 BSTree t;
  159.                 trees.push_back(t);
  160.         }
  161.  
  162.         bool find(int x, int version) {
  163.                 return trees[version].find(x);
  164.         }
  165.  
  166.         void insert(int x, int version) {
  167.                 trees.push_back(trees[version].insert(x));
  168.         }
  169.  
  170.         void remove(int x, int version) {
  171.                 trees.push_back(trees[version].remove(x));
  172.         }
  173. };
  174. #endif
create a new version of this paste RAW Paste Data