1 Overview
In this project, you will develop code for a binary search tree variant called a Sequoia. Specifically,you will need to implement member functions for two classes, Sequoia and SequoiaNode. Just likea BST, Sequoia is the main class and represents the tree as a whole, while SequoiaNode representsa single node in the tree.A header file and a driver have been provided. You are allowed to add member functions tothe classes defined in the header; however, you are not allowed to change the data members ofthe Sequoia or SequoiaNode classes or modify the driver file. The driver file implements severalvalidation functions for the Sequoia; these functions must be defined in the header, and you arenot allowed to modify them
2 Sequoia trees
Just like their real world counterparts, Sequoias are very tall trees. Specifically, every node in aSequoia must be atallnode, where atallnode satisfies one of the following
Sequoias are also BSTs, and every node must simultaneously satisfy the BST property:
To maintain the tallness of the Sequoia, each node stores a height in addition to its value parent,left and right children. The Sequoia itself stores a root pointer and size.
3 Sequoia insertion
Inserting a node in a Sequoia tree starts by inserting the node in the same way you would inserta node into a BST. Similar to an AVL tree, we then need to adjust the other nodes in the treeafterwards to maintain their tallness property. Unlike an AVL tree, though, a Sequoia is quiteunbalanced in an effort to increase its height.
To fix the Sequoia nodes’ tallness, iterate up the tree, starting at the parent of the newly insertednode. At each node, recalculate the height by examining the height of the left and right children.(I recommend writing an updateHeight() function for this purpose, though this function is notrequired.) Then, check whether the height of the left and right trees satisfy the tallness property.If so, continue on to the parent of this node. Otherwise, there are two cases
Case 1 :the left subtree height is greater than or equal to the right subtree height, but less than double
Case 2 :the right subtree height is greater than the left but not double
In case 1, we simply rotate the right child of this node to the left, and we resolve case 2 byrotating the left child of this node to the right. In both cases, we will need to update the heightof the rotated child; however, both this node and the rotated child will be tall afterwards, and wecan continue moving up the tree. These rotations are performed exactly like the rotations for AVLtrees.Once we have iterated all the way to the root node, we need to check the tree to see whether theroot node was rotated, and if so, update its root. The easiest way to do this is to include a loop in theSequoia::insertfunction that updates the root to be its parent if its parent is not null.
4 Sequoia insertion example
Suppose that we are inserting the value 1 into the Sequoia below. Note that each node is labelledas value:height, and every node in the tree is tall.We start by adding the 1 as a left child of 2. This node has height 1
We then start adjusting the tree, beginning with node 2. The height of node 2 is still 2; however,the node is no longer tall, as the height of its left and right subtrees are both 1 (16≤2(1)). Thisqualifies as case 1 of the insertion procedure above since the left tree height is greater than or equalto the right height and but less than double the right height, so we fix it by rotating the right child(3) to the left and updating the height of node 3:
Afterwards, we see that both 2 and 3 are tall, so we continue on to node 4. Node 4 still hasheight 5; however, it is also no longer tall, as the height of its left subtree is 3 and the height of itsright subtree is 4 (36≥2(4) and 46≥2(3)). This qualifies as case 2 of the insertion procedure above(since 4>3 and 4<2(3)), so we fix it by rotating the left child (3) to the right and updating theheight of 3:
At this point, we have reached the root of the tree, so we can stop: every node satisfies the BSTproperty, has the correct height, and is tall. Afterwards, we need to update the root of the Sequoiafrom 4 to 3
5 Sequoia deletion
Deleting a node from a Sequoia is very similar to insertion; however, the tallness property will berestored after at most 1 rotation. To start, delete the given node from the Sequoia in the samemanner as a BST. Then, begin iterating up the tree, starting from the parent of the deleted node
At each node, update the height based on its children, then check whether the node is tall bycomparing the left and right subtree heights. If the tree is tall, continue to the parent of this node,but otherwise we have the same two cases as insertion:
Case 1: the left subtree height is greater than or equal to the right subtree height, but less than double
Case 2: the right subtree height is greater than the left but not double
The cases are resolved in the same way as insertion: in case 1, we simply rotate the right childof this node to the left, and in case 2, we rotate the left child to the right. In both cases, we willneed to update the height of the rotated child; however, this rotation will guarantee that all nodesin the tree are now tall. As with insertion, we need to update the root in case it was rotated.
6 Sequoia deletion example
We start by deleting the 9, so 8 has no children. Then, we start moving up the tree at node 8.The height of 8 is now 1, and node 8 is tall because its left and right subtrees both have height 0(0≥2(0)). The height of 6 is now 2, and it’s also still tall: its left subtree height is 0 and the rightsubtree is 1, and 1≥2(0). Continuing to 5, the height of 5 is now 3. Its left subtree height is 1and its right subtree height is 2, and 2≥2(1), so node 5 is tall and we continue to 3. The heightof 3 is now 4, but it is no longer tall, as its left subtree has a height of 2 and its right subtree aheight of 3 (36≥2(2) and 26≥2(3)). According to case 2, we should rotate the 1 node to the rightand update its height:
Every node now satisfies the BST property, has the correct height, and is tall. Lastly, we wouldupdate the root of this tree to 1. Note that the height of this tree has not changed, so if this treewere a subtree of a larger Sequoia, all of the other nodes would still be tall and have the correct height.
7 Driver file
You have been provided with a simple driver file that reads in values to insert and delete frominput.txtand performs these operations on an empty Sequoia tree. The driver writes two trees tooutput.txt, one per line: the first is printed after all insertions and the second after all deletionsare done.Theinput.txtfile will have 2 lines. The first line has all of the integers to be inserted into theSequoia tree, separated by spaces, and the second line has all of the integers to be removed fromthe tree, separated by spaces. All of the values on the second line will also appear on the first line.All insertions and deletions are performed in the order that the values are entered on each line.Moreover, the driver checks that every node in the tree has the correct height and is tall after everyinsertion and deletion and will print an error message and stop if some node is incorrect.
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
Get Free Quote!
403 Experts Online
