MTH4300 Home

Video about Sets and Maps

Summary

The solution to the problem from the video 2:

Video 1: Introduction to binary search trees and AVL trees

Video 2: Sets and Maps in C++

Problems

Problem 1. The node of the binary tree is defined in the following way


class TN{
public:
\(\quad\quad\)long content;
\(\quad\quad\)TN* aLeft;
\(\quad\quad\)TN* aRight;
};

The implementation of the function f is given below


long f(TN* a, long h){
\(\quad\quad\)if(a==nullptr){
\(\quad\quad\quad\quad\)return 1;
\(\quad\quad\)}
\(\quad\quad\)long c=a-\(>\)content;
\(\quad\quad\)return (c%10)+(h%2)*f(a-\(>\)aLeft,h+1)+(c%2)*f(a-\(>\)aRight,h+1);
}

Assume that aRoot is the pointer to the root of the tree

What is the result of the evaluation f(aRoot,3)? Provide a rigorous justification for your answer.

Problem 2. What happens when the number \(55\) is inserted in the following AVL tree? What is the resulting tree after all the rotations?

What is the result of the evaluation f(aRoot,3)? Provide a rigorous justification for your answer.