Trees

Our trees utilizes a recursive strategy for nearly all their methods. A recursive strategy greatly improves the readability and simplicity of the code, but at the cost of potentially receiving a stack overflow in the case of too many recursions. Due to this, there will be a theoretical limit to how deep our trees can grow (depending on how large your computers stack is). Please note that the insertion/deletion do not utilize a recursive strategy, but the supporting methods like retrieving the height, or printing the tree do use it. The tree is initialized by calling the constructor which will initially give an empty tree. From here, users will be able to insert numbers into the tree through the use of the insert() method. The re-coloring and restructuring will be handled automatically. Other methods that the user will be able to run include insert(), delete_node(), get_num_leaves(), get_height(), print_nodes_in_order(), is_empty(), and print_tree(). A full description of each method and its purpose is shown below:

Red Black Tree

The insert() method will accept a u32 number as an input and then insert the value into the tree. This means that it will first insert the value as if the tree was a binary tree and then perform rotations and recoloring when appropriate. All cases for rotation and recoloring can be found here: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree.

The delete() method will accept a u32 number as an input and then delete the node from the tree. Rotations and recoloring will follow. As mentioned above, all cases for rotation and recoloring can be found here: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

The get_num_leaves() method will return the number of leaf nodes in the tree. A leaf node is defined to be a node that does not have a left nor right child. So a tree with only the root note, will be considered to also have one leaf node.

The get_height() method will return the maximum height of the tree. The max height is defined to be the maximum number of nodes you need to traverse from the root to one of its leaf nodes.

The print_nodes_in_order() method will print out every node’s key in ascending order.

The is_empty() method will return True if the tree does not have a root node and False otherwise.

The print_tree() method will fully print out the tree in the format of <Root/Left/Right Child>, , and . This method will print out null nodes to make it clear where the termination points are.

AVL Tree

The insert() method will accept a number as an input and then insert the value into the tree. This means that it will first insert the value as if the tree was a binary tree and then perform rotations when appropriate. All cases for rotation and recoloring can be found here: https://www.geeksforgeeks.org/avl-tree-set-1-insertion/.

The delete_node() method will accept a number as an input and then delete the node from the tree. Rotations will follow. As mentioned above, all cases for rotation and recoloring can be found here: https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

The get_num_leaves() method will return the number of leaf nodes in the tree. A leaf node is defined to be a node that does not have a left nor right child. So a tree with only the root note, will be considered to also have one leaf node.

The get_height() method will return the maximum height of the tree. The max height is defined to be the maximum number of nodes you need to traverse from the root to one of its leaf nodes.

The print_nodes_in_order() method will print out every node in ascending order.

The is_empty() method will return True if the tree does not have a root node and False otherwise.

The print_tree() method will fully print out the tree in the format of <Root/Left/Right Child>, , and . This method will print out null nodes to make it clear where the termination points are.