## Description

## 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 like

a BST, Sequoia is the main class and represents the tree as a whole, while SequoiaNode represents

a single node in the tree.

A header file and a driver have been provided. You are allowed to add member functions to

the classes defined in the header; however, you are not allowed to change the data members of

the Sequoia or SequoiaNode classes or modify the driver file. The driver file implements several

validation functions for the Sequoia; these functions must be defined in the header, and you are

not allowed to modify them.

## 2 Sequoia trees

Just like their real world counterparts, Sequoias are very tall trees. Specifically, every node in a

Sequoia must be a tall node, where a tall node satisfies one of the following:

the left subtree has at least double the height of the right subtree, or

the right subtree has at least double the height of the left subtree

Sequoias are also BSTs, and every node must simultaneously satisfy the BST property:

every value in the left subtree is less than or equal to the value of this node, and

every value in the right subtree is greater than or equal to the value of this node

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 insert

a node into a BST. Similar to an AVL tree, we then need to adjust the other nodes in the tree

afterwards to maintain their tallness property. Unlike an AVL tree, though, a Sequoia is quite

unbalanced in an effort to increase its height.

1

To fix the Sequoia nodes’ tallness, iterate up the tree, starting at the parent of the newly inserted

node. 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 not

required.) 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 by

rotating the left child of this node to the right. In both cases, we will need to update the height

of the rotated child; however, both this node and the rotated child will be tall afterwards, and we

can continue moving up the tree. These rotations are performed exactly like the rotations for AVL

trees.

Once we have iterated all the way to the root node, we need to check the tree to see whether the

root node was rotated, and if so, update its root. The easiest way to do this is to include a loop in

the Sequoia::insert function 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 labelled

as 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 (1 6≤ 2(1)). This

qualifies as case 1 of the insertion procedure above since the left tree height is greater than or equal

to 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:

2

Afterwards, we see that both 2 and 3 are tall, so we continue on to node 4. Node 4 still has

height 5; however, it is also no longer tall, as the height of its left subtree is 3 and the height of its

right subtree is 4 (3 6≥ 2(4) and 4 6≥ 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 the

height of 3:

At this point, we have reached the root of the tree, so we can stop: every node satisfies the BST

property, has the correct height, and is tall. Afterwards, we need to update the root of the Sequoia

from 4 to 3.

## 5 Sequoia deletion

Deleting a node from a Sequoia is very similar to insertion; however, the tallness property will be

restored after at most 1 rotation. To start, delete the given node from the Sequoia in the same

manner 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 by

comparing 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

3

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 child

of this node to the left, and in case 2, we rotate the left child to the right. In both cases, we will

need to update the height of the rotated child; however, this rotation will guarantee that all nodes

in the tree are now tall. As with insertion, we need to update the root in case it was rotated.

## 6 Sequoia deletion example

Suppose that we are deleting 9 from the Sequoia below:

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 right

subtree is 1, and 1 ≥ 2(0). Continuing to 5, the height of 5 is now 3.

Its left subtree height is 1

and its right subtree height is 2, and 2 ≥ 2(1), so node 5 is tall and we continue to 3. The height

of 3 is now 4, but it is no longer tall, as its left subtree has a height of 2 and its right subtree a

height of 3 (3 6≥ 2(2) and 2 6≥ 2(3)).

According to case 2, we should rotate the 1 node to the right

and update its height:

4

Every node now satisfies the BST property, has the correct height, and is tall. Lastly, we would

update the root of this tree to 1. Note that the height of this tree has not changed, so if this tree

were 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 from

input.txt and performs these operations on an empty Sequoia tree. The driver writes two trees to

output.txt, one per line: the first is printed after all insertions and the second after all deletions

are done.

The input.txt file will have 2 lines. The first line has all of the integers to be inserted into the

Sequoia tree, separated by spaces, and the second line has all of the integers to be removed from

the 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 every

insertion and deletion and will print an error message and stop if some node is incorrect.

### 8 Submission and grading

You should your source code and header, sequoia.cpp and sequoia.h, as a zip archive. Your code

will be evaluated based on whether it produces the correct output for some number of test cases.

You may use any development environment that you like when developing the code; however, it

will be compiled and run using g++ in a Linux environment. Code that does not compile will not

receive substantial credit, so be sure that your code can be compiled using g++.

The development environment used in class is VS Code (https://code.visualstudio.com/

download). This IDE includes useful features like syntax highlighting and an integrated terminal

window that you can use to invoke a compiler.

Windows users can download MinGW (https://sourceforge.net/projects/mingw-w64) to

use g++, though you will need to add the MinGW bin directory to the Windows path in order for

the terminal to recognize the command g++ (or gdb or any of the other tools provided by MinGW).

#### 9 Important note

You are allowed to use any code posted for this course on Canvas, and you are allowed to discuss

this project with the course TAs or professor. However, you are not allowed to use code from the

internet or your peers. Your code will be run through plagiarism-detection software, and violators

will be dealt with accordingly.

5