Project 3: Red Black Trees Solution

  Assignment Overview

 # Red/Black Tree


A Red Black Tree is a type of self-balancing binary search tree (BST). A BST is a binary tree with the property that given a node contained therein, its left and right children store values less and greater than it respectively. This allows for, on average, logarithmic time complexity of searches. BSTs can, as has been discussed in class, become unbalanced when subject to certain sequences of insertions or removals. A self balancing BST seeks to remedy this issue by ensuring that given a node, its left and right branches are of relatively equal size. A Red Black tree ensures this balance by assigning a color (red or black) to each node and applying rules to the ways in which these colors are distributed. These rules are as follows:

1.  Each node must be either Red or Black.
2.  The root of the tree must always be Black.
3.  A Red node must always have a Black parent node, and a Black child node (as shown above, null nodes are assumed to be Black).
4.  Every path from the root of the tree to a null pointer must pass through the <span style="text-decoration: underline;">same number</span> of black nodes.

The method by which these rules maintain balance is best discussed in further depth than feasible in a project description, and can be readily found online. A few links, though, may be helpful.

[Here is a visualization tool](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html) which is very useful for testing insertions and removals. We used this while developing the project.

[Information on static methods in python.](https://pythonbasics.org/static-method/)

[Information on python generators and yield statements.](https://realpython.com/introduction-to-python-generators/#building-generators-with-generator-expressions) (This is more than you need to use for this project.)

[Here is some information](https://www.geeksforgeeks.org/red-black-tree-vs-avl-tree/) on the differences between Red Black trees and AVL trees, which this project was based on in previous semesters.

  Assignment Notes

IMPORTANT: Don't create new objects without good reason. Never in the course of this project should one create a new tree, and new nodes should only be created within   insert().   Doing so in other situations is very likey to violate complexity requirements, and never necessary.

    Remember to write docstrings. Project 1 provides examples of how they should be written. Docstrings should include a description of the function they pertain to, its parameters, and its return type.
    An   RBtree   is strictly typed, and will not contain mismatched types. However, the structure should be type agnostic and able to contain any standard type.
    Several of the method implemented are   static methods   - the reason for this is that while they are members of the   RBtree   class, they act only on the   RBnode   class, and are not called on an   RBtree  . I.e. rather than calling on `self` (an   RBtree   instance) with `self.get_uncle(node)`, one would call the function `RBtree.get_uncle(node)`.
    The methods below are given in a suggested logical order of implementation.
      IT IS HIGHLY RECOMMENDED YOU REFER TO THE SECTIONS OF ZYBOOKS RELEVANT TO THE PROJECT BEFORE AND DURING IMPLEMENTATION!  
      remove()   and   prepare_removal()   are large functions. Consider ways in which one may divide it into multiple functions (hint: look at zybooks).
    As the above note should indicate, feel free to implement helper functions as necessary- as long as they obey time and space complexity requirements.
    For traversals, use of recursion is highly recommended.
    This project will   not have an application problem   due to the complexity and difficulty of implemeting Red Black trees. With that said, <span style="text-decoration: underline;">_make sure you start this project early._</span>
      Types:  
          T  : Generic Type
          RBnode  : Described below

  Assignment Specifications

 # class RBnode: 

This class describes the nodes contained in an   RBtree  .

  _DO NOT MODIFY this class_  

      Attributes  
          value  : Value contained in a node. Is also used as a key insertion, removal, and other pertinent operations.
          is_red:   Boolean identifier for node color (if it is not red, it is black)
          parent:   Parent of the node
          left:   Left child of the node
          right:   Right child of the node

      __init__  (self, value, is_red=True, parent=None, left=None, right=None)  

          val  :   T   
          is_red  :   bool  
          parent  :   RBnode  
          left  :   RBnode  
          right  :   RBnode  
        Instantiates an   RBnode  , assigning its member variables.
        return:   None  
        _Time Complexity: O(1)_
      __eq__  (self, other)
          other  :   RBnode  
        Assesses equality of data contained in a node, checking both   value   and   is_red  
        return:   bool  
        _Time Complexity: O(1)_
      __str__  (self)
        Representation of   val   and   is_red   as a string
        return:   str  
        _Time Complexity: O(1)_
      __repr__  (self)
        Representation as a string utilizing   __str__  
        return:   str  
        _Time Complexity: O(1)_
      subtree_size  (self)
        Size of a subtree rooted at _self_
        return:   int  
        _Time Complexity: O(n)_
      subtree_size  (self)
        Height of a subtree rooted at _self_
        return:   int  
        _Time Complexity: O(n)_
      subtree_red_black_property  (self)
        Determines whether the subtree rooted at _self_ adheres to Red Black properties
        return:   bool  
        _Time Complexity: O(n)_

 # class RBtree: 

  _DO NOT MODIFY the following attributes/functions_  

      Attributes  
          root  : root of an   RBtree  , of type   RBnode  
          size  : number of nodes contained in the tree
      __init__  (self, root=None)
          root  :   RBnode  
        Instantiates an   RBtree  , creating a deepcopy of the subtree rooted at a provided node. This provided node defaults to   None  .
        Size is assigned based on the described subtree.
        _Time Complexity: O(n) -_ where _n _is the size of the rooted subtree provided
      __eq__  (self, other)
          other  :   RBtree  
        Determines equality between   RBtree   instances.
        return:   bool  
        _Time Complexity: O(min(N, M)) --> M is size of other  _
      __str__  (self)
        Represents the   RBtree   as a string, for use in debugging
        return:   str  
        _Time Complexity: O(N)_

      __repr__  (self)
        Represents the list as a string utilizing   __str__  
        return:   str  
        _Time Complexity: O(N)_

  _IMPLEMENT the following functions_  

      set_child  (parent, child, is_left)   --> static method  
          parent  :   RBnode  
          child  :   RBnode  
          is_left  :   bool  
        Sets the childparameter of _parent _to _child_. Which child is determined by the identifier _is_left. _The parent parameter of the new child node should be updated as required.
        return:   None  
        _Time Complexity: O(1), Space Complexity: O(1)_
      replace_child  (parent, current_child, new_child)   --> static method  
          parent  :   RBnode  
          current_child  :   RBnode  
          new_child  :   RBnode  
        Replaces   parent  's child   current_child   with   new_child  .
        return:   None  
        _Time Complexity: O(1), Space Complexity: O(1)_
      get_sibling  (node)   --> static method  

          node  :   RBnode  
        Given a node, returns the other child of that node's parent, or   None   should no parent exist.
        _Time Complexity: O(1), Space Complexity: O(1)_
      get_uncle  (node)   --> static method  
          node  :   RBnode  
        Given a node, returns the sibling of that node's parent, or   None   should no such node exist.
        _Time Complexity: O(1), Space Complexity: O(1)_
      get_grandparent  (node)   --> static method  
          node  :   RBnode  
        Given a node, returns the parent of that node's parent, or   None   should no such node exist.
        _Time Complexity: O(1), Space Complexity: O(1)_
      left_rotate  (self, node)
          node  :   RBnode  
        Performs a left tree rotation on the subtree rooted at _node_.
        return:   None  
        _Time Complexity: O(1), Space Complexity: O(1)_
      right_rotate  (self, node)
          node  :   RBnode  
        Performs a right tree rotation on the subtree rooted at _node._
        return:   None  
        _Time Complexity: O(1), Space Complexity: O(1)_
      insertion_repair  (self, node)
          node  :   RBnode  
        This method is not tested explicitly, but should be called after insertion on the node which was inserted, and should rebalance the tree by ensuring adherance to Red/Black properties.
        It is highly recommended you utilize recursion.
        return:   None  
        _Time Complexity: O(log(n)), Space Complexity: O(1)_
      prepare_removal  (self, node)
          node  :   RBnode  
        This method is not tested explicitly, but should be called prior to removal, on a node that is to be removed. It should ensure balance is maintained after the removal.
        return:   None  
        _Time Complexity: O(log(n)), Space Complexity: O(1)_
      insert  (self, node, val)
          node: RBnode  
          val: Type T  
        Inserts an   RBnode   object to the subtree rooted at _node_ with value _val_.
        Should a node with value _val_ already exist in the tree, do nothing.
        It is _highly recommended _you implement this function recursively. To do so non-recursively will be significantly harder, and we won't assist you in doing so in the helproom or on piazza.
        return:   None  
        _Time Complexity: O(log(n)), Space Complexity: O(1)_
      search  (self, node, val)
          node: RBnode  
          val: Type T  
        Searches the subtree rooted at _node_ for a node containing value _val. _If such a node exists, return that node- otherwise return the node which would be parent to a node with value _val_ should such a node be inserted.
        This is probably best to implement recursively, but not required.
        _Time Complexity: O(log(n)), Space Complexity: O(1)_
      min  (self, node)
          node: RBnode  
        Returns the minimum value stored in the subtree rooted at _node_. (  None   if the subtree is empty).
        _Time Complexity: O(log(n)), Space Complexity: O(1)_
      max  (self, node)
          node: RBnode  
        Returns the maximum value stored in a subtree rooted at _node_. (  None   if the subtree is empty).
        _Time Complexity: O(log(n)), Space Complexity: O(1)_
      inorder  (self, node)
          node: RBnode  
        Returns a _generator_ object describing an inorder traversal of the subtree rooted at _node._
        Points will be deducted if the return of this function is not a generator object (hint:   yield   and   yield     from  )
        _Time Complexity: O(n), Space Complexity: O(n)_
      preorder  (self, node)
          node: RBnode  
        Returns a _generator_ object describing a preorder traversal of the subtree rooted at _node._
        Points will be deducted if the return of this function is not a generator object (hint:   yield   and   yield     from  )
        _Time Complexity: O(n), Space Complexity: O(n)_
      postorder  (self, node)
          node: RBnode  
        Returns a _generator _object describing a postorder traversal of the subtree rooted at _node._
        Points will be deducted if the return of this function is not a generator object (hint:   yield   and   yield     from  )
        _TIme Complexity: O(n), Space Complexity: O(n)_
      bfs  (self, node)
          node: RBnode  
        Returns a _generator _object describing a breadth first traversal of the subtree rooted at _node_.
        Hint: the _queue _class has been imported already, feel free to use it.
        Points will be deducted if the return of this function is not a generator object (hint:   yield   and   yield     from  )
        _Time Complexity: O(n), Space Complexity: O(n)_
      remove  (self, node, val)
          node: RBnode  
          val: Type T  
        Removes node with value _val _from the subtree rooted at _node_. If no such node exists, do nothing.
        If the node to be removed is an internal node with two children, swap its value with that of the maximum of its left subtree, then remove the node its value was swapped to.
        Using   search()   might be a good idea.
        This function is complicated and hard, don't be afraid to ask for help. We strongly recommend referring to zybooks.
        Note this function uses inorder traversals for testing, so your tests will not pass if the in order traversal function is not completed.
        return:   None  
        _Time Complexity: O(log(n)), Space Complexity: O(1)_

  Submission

  Deliverables

Be sure to upload the following deliverables in a .zip folder to Mimir by 8:00p Eastern Time on Thursday, 10/22/20.

    Project3.zip
        |— Project3/
            |— README.md       (for project feedback)
            |— __init__.py     (for proper Mimir testcase loading)
            |— RBtree.py       (contains your solution source code)        |— RBnode.py       (supports RBtree.py)

  Grading

    Tests (70)
        Tests: __/70
    Manual (30)  

        Time Complexity: __/14
            set_child, replace_child, get_sibling, get_uncle, get_grandparent, min, max, search (0.5 each)
            inorder, preorder, postorder, bfs, left_rotate, right_rotate (1 each)
            insert, remove (2 each)
        Space Complexity: __/14
            set_child, replace_child, get_sibling, get_uncle, get_grandparent, min, max, search (0.5 each)
            inorder, preorder, postorder, bfs, left_rotate, right_rotate (1 each)
            insert, remove (2 each)
        README.md is _completely_ filled out with (1) Name, (2) Feedback, (3) Time to Completion and (4) Citations: __/2

Project designed by Andrew Haas and Ian Barber