daily pastebin goal
12%
SHARE
TWEET

Untitled

a guest Jan 12th, 2018 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // All of the methods you will need to implement (5 of them) will have the comment
  2.  
  3. // IMPLEMENT ME
  4.  
  5. // above them. Note that one of the methods to be filled in is inside the class
  6. // definition. This is because you cannot return an inner class outside the scope of the
  7. // defining class. Since findNode returns a Node (an inner class), its definition has to be
  8. // inside the definition scope of the RedBlackTree class itself, so the Node class is in scope
  9. // as well.
  10.  
  11.  
  12. #ifndef RBTREE_CS197
  13. #define RBTREE_CS197
  14.  
  15. #include <cassert>
  16. #include <functional>
  17. #include <utility>
  18. #include <iostream>
  19.  
  20. using namespace std;
  21.  
  22. // Two types are templated here!
  23. // K = key type
  24. // V = value type
  25. template<typename K, typename V, typename Compare = less<K> >
  26. class RedBlackTree {
  27.  public:
  28.  // This is defining an enumeration type.
  29.  // Enumerations are categorical variables, meaning
  30.  // a variable of the enumeration type (in this case 'Color')
  31.  // Can only receive the values 'BLACK' and 'RED'
  32.  typedef enum Color { BLACK, RED };
  33.  
  34.  private:
  35.  class Node {
  36.  public:
  37.    Node() {
  38.      parent = left = right = NULL;
  39.      color = RED;
  40.    }
  41.    Node(K key, V value) {
  42.      parent = left = right = NULL;
  43.      color = RED;
  44.      this->key = key;
  45.      this->value = value;
  46.    }
  47.    ~Node() {}
  48.  
  49.    string getColor() {
  50.     if(color == BLACK) return "BLACK";
  51.     else if(color==RED)return "RED";
  52.     else return "I don't know man";
  53. }
  54.  
  55.    Node *parent;
  56.    Node *left;
  57.    Node *right;
  58.    K key;
  59.    V value;
  60.    Color color;
  61.  };
  62.  
  63.  Node *root;
  64.  Node *sentinel; // This is used as a "null" pointer. It should never be directly used except
  65.                  // to indicate a boundary. However its color is black.
  66.  
  67.  // These are internal methods that are used to maintain
  68.  // the correctness of the tree, and for convenience
  69.  void rotateLeft(Node *x);
  70.  void rotateRight(Node *x);
  71.  void insertFixup(Node *z);
  72.  void deleteFixup(Node *x);
  73.  
  74.  Node *subTreeMinimum(Node *n) {
  75.    Node *current;
  76.    current = n;
  77.    while (current->left != sentinel) {
  78.      current = current->left;
  79.    }
  80.    return current;
  81.  }
  82.  
  83.  Node *subTreeMaximum(Node *n) {
  84.    Node *current;
  85.    current = n;
  86.    while (current->right != sentinel) {
  87.      current = current->right;
  88.    }
  89.    return current;
  90.  }
  91.  
  92.  // IMPLEMENT ME
  93.  Node *findNode(K key, Node *currentPosition) {
  94.  
  95.      if(key == currentPosition->key)
  96.          return currentPosition;
  97.      else if(key < currentPosition->key)
  98.      {  //I was stuck on an error here for a long long time until I put the brackets in and fixed the error.
  99.          if(currentPosition->left != sentinel)
  100.             return findNode(key, currentPosition->left);
  101.      }
  102.          else if(key > currentPosition ->key)
  103.          {
  104.            if(currentPosition->right != sentinel)
  105.             return findNode(key, currentPosition->right);
  106.          }
  107.          return NULL;
  108.  }
  109.  
  110.  public:
  111.  // Constructor and Destructor
  112.  RedBlackTree();
  113.  ~RedBlackTree();
  114.  
  115.  // methods -- Again, don't return a Node, the return type, if there is one,
  116.  // is of type T. See comments near methods for description
  117.  void insert(K key, V value);
  118.  void remove(K key);
  119.  pair<K,V> *get(K key);
  120.  pair<K,V> *minimum();
  121.  pair<K,V> *maximum();
  122.  pair<K,V> *successor(K key);
  123.  pair<K,V> *predecessor(K key);
  124.  
  125.  
  126. };
  127.  
  128. // Constructor definition - the tree should start off empty, meaning that not
  129. // even a root exists, yet this is still a valid state of the tree.
  130. template <typename K, typename V, typename Compare >
  131. RedBlackTree<K,V,Compare>::RedBlackTree() {
  132.   sentinel = new Node();
  133.   sentinel->color = BLACK;
  134.   // This is so we never hit a null.
  135.   // The color checks will terminate our loops.
  136.   sentinel->left = sentinel;
  137.   sentinel->right = sentinel;
  138.   sentinel->parent = sentinel;
  139.   root = sentinel;
  140. }
  141.  
  142. // Deconstructor for the tree. Don't call delete on the key or value data since you
  143. // don't know what it is. However, any remaining nodes in the tree need to be deallocated
  144. // to avoid memory leaks.
  145. template<typename K, typename V, typename Compare >
  146. RedBlackTree<K,V,Compare>::~RedBlackTree() {
  147.   delete sentinel;
  148. }
  149.  
  150.  
  151. // Inserts a new node into the tree.
  152. template<typename K, typename V, typename Compare >
  153. void RedBlackTree<K,V,Compare>::insert(K key, V value) {
  154.   Node *z = new Node(key, value);
  155.   Node *y = sentinel;
  156.   Node *x = root;
  157.   while (x != sentinel) {
  158.     y = x;
  159.     if (Compare()(z->key, x->key)) {
  160.       x = x->left;
  161.     } else {
  162.       x = x->right;
  163.     }
  164.   }
  165.   z->parent = y;
  166.   if (y == sentinel) {
  167.     root = z;
  168.   } else {
  169.     if (Compare()(z->key, y->key)) {
  170.       y->left = z;
  171.     } else {
  172.       y->right = z;
  173.     }
  174.   }
  175.   z->left = sentinel;
  176.   z->right = sentinel;
  177.   z->color = RED;
  178.   insertFixup(z);
  179. }
  180.  
  181. // Removes a node from the tree, if it (the node) exists.
  182. template<typename K, typename V, typename Compare >
  183. void RedBlackTree<K,V,Compare>::remove(K key) {
  184.     /*
  185.      //Tracer code for tree
  186. cout<<"||"<<root->left->key<<"("<<root->left->getColor()<<")("<<root->left->parent->key<<")<-";
  187.      cout<<"Root:"<<root->key<<"("<<root->getColor()<<"("<<root->parent->key<<")";
  188.  
  189.        cout<<"->"<<root->right->key<<"("<<root->right->getColor()<<")("<<root->right->parent->key<<")";
  190.        cout<<"->"<<root->right->right->key<<"("<<root->right->right->getColor()<<")("<<root->right->right->parent->key<<")||"<<endl;
  191. */
  192.   Node *x, *y;
  193.   Node *z = findNode(key, root);
  194.  
  195.   if (z == sentinel) return;
  196.  
  197.   // Harder from here...
  198.   if (z->left == sentinel || z->right == sentinel) {
  199.     y = z;
  200.   } else {
  201.     pair<K,V> *result = successor(z->key);
  202.     y = findNode(result->first, root);
  203.     delete result; // Cleaning up
  204.   }
  205.  
  206.   if (y->left != sentinel) {
  207.     x = y->left;
  208.   } else {
  209.     x = y->right;
  210.   }
  211.  
  212.   x->parent = y->parent;
  213.  
  214.   if (y->parent == sentinel) {
  215.     root = x;
  216.   } else {
  217.     if (y == y->parent->left) {
  218.       y->parent->left = x;
  219.     } else {
  220.       y->parent->right = x;
  221.     }
  222.   }
  223.  
  224.   if (y != z) {
  225.     z->key = y->key;
  226.     z->value = y->value;
  227.   }
  228.  
  229.   if (y->color == BLACK) {
  230.     deleteFixup(x);
  231.   }
  232.  
  233. }
  234.  
  235. // Returns the key/value pair of the provided key if it exists.
  236. // Otherwise returns null.
  237. template<typename K, typename V, typename Compare >
  238. pair<K,V> *RedBlackTree<K,V,Compare>::get(K key) {
  239.   Node *found = findNode(key, root);
  240.   if (found == sentinel) return NULL;
  241.   else return new pair<K,V>(found->key, found->value);
  242. }
  243.  
  244. // Returns the smallest item in the tree, or NULL if the tree is empty.
  245. template<typename K, typename V, typename Compare >
  246. pair<K,V> *RedBlackTree<K,V,Compare>::minimum() {
  247.   if (root == sentinel) {
  248.     return NULL;
  249.   } else {
  250.     Node *min = subTreeMinimum(root);
  251.     return new pair<K,V>(min->key, min->value);
  252.   }
  253. }
  254.  
  255. // Returns the largest item in the tree, or NULL if the tree is empty.
  256. template<typename K, typename V, typename Compare >
  257. pair<K,V> *RedBlackTree<K,V,Compare>::maximum() {
  258.   if (root == sentinel) {
  259.     return NULL;
  260.   } else {
  261.     Node *max = subTreeMaximum(root);
  262.     return new pair<K,V>(max->key, max->value);
  263.   }
  264. }
  265.  
  266. template<typename K, typename V, typename Compare >
  267. void RedBlackTree<K,V,Compare>::insertFixup(Node *z) {
  268.   Node *y;
  269.  
  270.   while (z->parent->color == RED) {
  271.     if (z->parent == z->parent->parent->left) {
  272.       y = z->parent->parent->right;
  273.       if (y->color == RED) {
  274.     z->parent->color = BLACK;
  275.     y->color = BLACK;
  276.     z->parent->parent->color = RED;
  277.     z = z->parent->parent;
  278.       } else {
  279.     if (z == z->parent->right) {
  280.       z = z->parent;
  281.       rotateLeft(z);
  282.     }
  283.         //
  284.     z->parent->color = BLACK;
  285.     z->parent->parent->color = RED;
  286.     rotateRight(z->parent->parent);
  287.       }
  288.     } else  {
  289.       y = z->parent->parent->left;
  290.       if (y->color == RED) {
  291.     z->parent->color = BLACK;
  292.     y->color = BLACK;
  293.     z->parent->parent->color = RED;
  294.     z = z->parent->parent;
  295.       } else {
  296.     if (z == z->parent->left) {
  297.       z = z->parent;
  298.       rotateRight(z);
  299.     }
  300.     z->parent->color = BLACK;
  301.     z->parent->parent->color = RED;
  302.     rotateLeft(z->parent->parent);
  303.       }
  304.     }
  305.   }
  306.   root->color = BLACK;
  307.  
  308.  
  309.  
  310. }
  311.  
  312. template<typename K, typename V, typename Compare >
  313. void RedBlackTree<K,V,Compare>::deleteFixup(Node *x) {
  314.   Node *w;
  315.  
  316.   while (x != root && x->color == BLACK) {
  317.     if (x = x->parent->left) {
  318.       w = x->parent->right;
  319.       if (w->color == RED) {
  320.     w->color = BLACK;
  321.     x->parent->color = RED;
  322.     rotateLeft(x->parent);
  323.     w = x->parent->right;
  324.       }
  325.      
  326.       if (w->left->color == BLACK && w->right->color == BLACK) {
  327.     w->color = RED;
  328.     x = x->parent;
  329.       } else {
  330.     if (w->right->color == BLACK) {
  331.       w->color = RED;
  332.       rotateRight(w);
  333.       w = x->parent->right;
  334.     }
  335.     w->color = x->parent->color;
  336.     x->parent->color = BLACK;
  337.     w->right->color = BLACK;
  338.     rotateLeft(x->parent);
  339.     x = root;
  340.       }
  341.     } else {
  342.       w = x->parent->left;
  343.       if (w->color == RED) {
  344.     w->color = BLACK;
  345.     x->parent->color = RED;
  346.     rotateRight(x->parent);
  347.     w = x->parent->left;
  348.       }
  349.      
  350.       if (w->right->color == BLACK && w->left->color == BLACK) {
  351.     w->color = RED;
  352.     x = x->parent;
  353.       } else {
  354.     if (w->left->color == BLACK) {
  355.       w->color = RED;
  356.       rotateLeft(w);
  357.       w = x->parent->left;
  358.     }
  359.     w->color = x->parent->color;
  360.     x->parent->color = BLACK;
  361.     w->left->color = BLACK;
  362.     rotateRight(x->parent);
  363.     x = root;
  364.       }
  365.     }
  366.   }
  367.   x->color = BLACK;
  368.  
  369. }
  370.  
  371. // IMPLEMENT ME
  372. template<typename K, typename V, typename Compare >
  373. pair<K,V> *RedBlackTree<K,V,Compare>::successor(K key) {
  374.     Node *x = findNode(key, this->root);
  375.  
  376.     K k;
  377.   if(x == NULL)return NULL;
  378.  
  379.     x = this->root;
  380.      pair<K,V> *p = new pair<K,V>(x->key, x->value);
  381.  
  382.     while(x != sentinel)
  383.     {
  384.         if(Compare()(key, x->key))
  385.         {
  386.             if(Compare() (key, x->key) && ((x->key < p->first && p->first > key)|| (p->first <= key)))
  387.                 p = new pair<K,V>(x->key, x->value);
  388.             x = x->left;
  389.         }
  390.         else
  391.         {
  392.             x = x->right;
  393.         }
  394.     }
  395.  
  396.      if(p->first > key) return p;
  397.      else return new pair<K,V>;
  398. }
  399.  
  400. // IMPLEMENT ME
  401. template<typename K, typename V, typename Compare >
  402. pair<K,V> *RedBlackTree<K,V,Compare>::predecessor(K key) {
  403.   return NULL;
  404. }
  405.  
  406. // IMPLEMENT ME
  407. template<typename K, typename V, typename Compare >
  408. void RedBlackTree<K,V,Compare>::rotateLeft(Node *x) {
  409.    // cout<<"ROTATELEFT:"<<x->key<<endl;
  410.  
  411.           Node *me;
  412.           Node *z;
  413.        if (x->right == 0) return;
  414.        
  415.        me          = x; // me = x
  416.        z           = me->right; //z = y
  417.        z->parent = x->parent;
  418.        me->right = z->left;
  419.        me->parent = z;
  420.        z->left   = me;    
  421.        
  422.       // cout<<"z->parent("<<z->parent->key<<")";
  423.         if(z->parent == sentinel) root = z;
  424.         else x = z;
  425. }
  426.  
  427.  
  428. // IMPLEMENT ME
  429. template<typename K, typename V, typename Compare >
  430. void RedBlackTree<K,V,Compare>::rotateRight(Node *x) {
  431.   //  cout<<"ROTATERIGHT"<<endl;
  432.           Node *me;
  433.           Node *z;
  434.     if (x->left == 0) return;
  435.  
  436.        me          = x; // me = x
  437.        z           = me->left; //z = y
  438.        z->parent = x->parent;
  439.        me->left = z->right;
  440.        me->parent = z;
  441.        z->right   = me;
  442.  
  443.       // cout<<"z->parent("<<z->parent->key<<")";
  444.         if(z->parent == sentinel) root = z;
  445.         else x = z;
  446. }
  447.  
  448. #endif
RAW Paste Data
Top