CSCI311-Project 2 AVL-tree Solved

Part 1. i.e. implement an AVL-tree (balanced BST tree, name it BST  and implement insert member function that inserts a new item in the tree and balances the tree.

Part 2 .i.e. add member function remove that removes a node from the tree.

Part 3   

1  . Add an integer size as a data member to Tnode class; the non-default constructor of the class will initialize size to 1. This data member, size, will be stored and maintained at each node. The meaning of size at any node i is the total number of nodes in the subtree rooted at i. When the constructor is called a new node is created in the tree, and this new node is the only node in the subtree rooted at this node, so the constructor initializes size at this node to 1.

You need to update your code for insert and remove to update size on each node on the path from the root to the new node (or to the removed node); this could be something similar to how you updated height – update function must run in constant time (this is not a recursive function, it should take just a few basic operations).

Write the following member functions to maintain and test size:

int getSize(Tnode* cur) that returns size (think what should be size of a subtree rooted at node that is NULL, i.e. if the parameter cur is NULL.

Every test t01-t08 checks printSize.

int getSize(Tnode* cur)
returns size of the subtree rooted at the parameter cur (think what should be size of a subtree rooted at node that is NULL, i.e. if the parameter cur is NULL)
void updateSize(Tnode *cur)
Updates the size of the subtree rooted at cur, use the size of left and right children
void printSize() 

void printSize(Tnode *cur) 
Traverses the tree using in-order traversal and prints size at each node (same format as printing height)

 
 

2  . Implement the following member functions for AVL tree.

(1)  Please watch the videos below (one is enough to implement this problem: the first a bit more complicated than the second approach). Both approaches are very useful for solving problems on a programming exam.

YouTube video Find LCA using collecting paths by Elena (15 min)

YouTube video Find LCA using find approach by Elena (5 min)

Definition: Given two keys, akey1 and akey2, of the two nodes in AVL tree, the lowest common ancestor is the node in AVL tree that occurs on the path from the root to each node and whose depth is the greatest (the depth of a node is the number of edges from the root to that node).

Given two keys as parameters, akey1 and akey2, of the two nodes in AVL tree, write a member function findLCA for AVL class that finds and returns the lowest ancestor of the two nodes given by akey1 and akey2. Your function must be recursive and run in O(logn)-time. This function returns a key, i.e. string type object. If your function reaches NULL, return an empty string.

Tests to test this function: t09.

 

(2)  Please watch the video below.

YouTube video how to find the k-th smallest key in an AVL tree by Elena (16 min).

Write a recursive member function findKthSmallest for AVL tree that finds and returns the k-th smallest key in AVL tree, where k is given as a parameter to this function. Your function must run in O(logn) worst-case time. Use the fact that each node stores size, the total number of nodes in the subtree rooted at this node. If your function reaches NULL, return an empty string. The count of keys in increasing order starts with 1 (i.e. the smallest key is 1-st).

Test t10 checks this function.

(3)  Please watch the video below.

YouTube video how to print the longest path in an AVL-tree by Elena (3 min).

Write a recursive member function printLongestPath for AVL tree that prints the longest path from the root to a deepest leaf in the tree (if there is a tie between some leaves, your function must choose the path to the leftmost, or the smallest-key, leaf). The order of printing is from the root to a leaf. You need to print only keys of the nodes. 

Tests t11, t12, and t13 check this function.

(4)

Write a recursive member function(s) collectSubtree that takes an empty vector as a parameter, and at the end of this function, the vector will have all the nodes (keys) in the subtree rooted at the node whose key is akey in increasing order. You may write a few functions to handle this task. If akey is not in the tree, then the vector will be empty at the end of execution.

Test t14 checks this function.

( 5) Update your main.cpp file from Assignment 8 to be able to test your new member functions:

Command
Description of what to do for this command
printSize
If command equals to "printSize", then call member function printSize() Print out endl after calling this function.
findLCA
Using cin, read in two strings akey1 and akey2, and use them as parameters to call member function findLCA().

Use cout to print out the result returned, and then print out endl.
findKthSmallest
Using cin, read in an integer k. Call findKthSmallest using k as a parameter to find and return the k-th smallest key in the tree. 

Use cout to print out the result returned, and then print out endl.
printLongestPath
Call printLongestPath(), and print out endl after calling this function.
collectSubtree
Using cin, read in a string akey. Use this as a parameter to call the member function collectSubtree. Another parameter to this function is an empty vector of strings. After this function has been executed, the vector will have keys of the nodes in the subtree rooted at the node whose key is akey. Write a for loop that will print out the keys (strings) from the vector (if the vector is not empty) in format

<key<space

At the end, print out endl.
Test t15 checks all the functions after a node has been removed from the tree