CSE331 Project 3: Red Black Trees Solution

This is not a team project, do not copy someone else’s work.
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 same number of black nodes.
Here is a visualization tool which is very useful for testing insertions and removals. We used this while developing the project.
Information on static methods in python.
Information on python generators and yield statements. (This is more than you need to use for this project.)
Here is some information 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!
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.
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.
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
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
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