daily pastebin goal
72%
SHARE
TWEET

Untitled

a guest Jan 12th, 2018 55 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top