MTH4300 Home
# Videos About Trees, Sets, and Maps

## Summary

## Video 1: Introduction to binary search trees and AVL trees

## Video 2: Sets and Maps in C++

## 1. Problems

**Problem** 1.
The node of the binary tree is defined in the following way
What is the result of the evaluation
\(X_0\)=5 +
**Problem** 2.
What happens when the number \(55\) is inserted in the following AVL tree? What is the resulting tree after all the rotations?

The solution to the problem from the video 2:

#include<iostream> #include<map> class Point2D{ public: long x; long y; int operator<(const Point2D&) const; void operator+=(const Point2D &); void operator-=(const Point2D &); }; int Point2D::operator<(const Point2D& b) const{ if(x<b.x){ return 1; } if(x>b.x){ return 0; } if(y<b.y){ return 1; } return 0; } void Point2D::operator+=(const Point2D& b){ x+=b.x; y+=b.y; } void Point2D::operator-=(const Point2D& b){ x-=b.x; y-=b.y; } class FJInfo{ public: long spLength; Point2D lastJump; FJInfo(); }; FJInfo::FJInfo(){ spLength=0;lastJump.x=0;lastJump.y=0; } FJInfo fewestJumps(std::map<Point2D,FJInfo>& knowledge, Point2D* allowedJumps, long m, Point2D target){ FJInfo wJump; if((target.x==0)&&(target.y==0)){ return wJump; } wJump.spLength=-1; if((target.x<0)||(target.y<0)){ return wJump; } std::map<Point2D,FJInfo>::iterator iSearch; iSearch=knowledge.find(target); if(iSearch!=knowledge.end()){ return iSearch->second; } long i=0; Point2D targetForEmployee; FJInfo wJumpEmployee; while(i<m){ targetForEmployee=target; targetForEmployee-=allowedJumps[i]; if((targetForEmployee.x > -1)&&(targetForEmployee.y > -1)){ iSearch=knowledge.find(targetForEmployee); if(iSearch!=knowledge.end()){ wJumpEmployee=iSearch->second; } else{ wJumpEmployee=fewestJumps(knowledge,allowedJumps,m,targetForEmployee); } if(wJumpEmployee.spLength > -1){ if( (wJump.spLength==-1) || (wJump.spLength > wJumpEmployee.spLength+1) ){ wJump.spLength=wJumpEmployee.spLength+1; wJump.lastJump=allowedJumps[i]; } } } ++i; } knowledge[target]=wJump; return wJump; } void printfewestJumps(std::map<Point2D,FJInfo>& knowledge, Point2D* allowedJumps, long m, Point2D target){ FJInfo winningStep=fewestJumps(knowledge,allowedJumps,m,target); if(winningStep.spLength > -1){ std::cout<<"The length of the shortest path from (0,0) to ("; std::cout<<target.x<<","<<target.y<<") is "<<winningStep.spLength<<".\n"; std::cout<<"The steps are:\n"; Point2D currentStart; currentStart.x=0;currentStart.y=0; while( (target.x > 0) || (target.y > 0) ){ std::cout<<"("<<currentStart.x<<","<<currentStart.y<<") ---> "; currentStart+=winningStep.lastJump; std::cout<<"("<<currentStart.x<<","<<currentStart.y<<") "; std::cout<<"Jump: <"<<winningStep.lastJump.x <<","<< winningStep.lastJump.y<<">\n"; target-=winningStep.lastJump; winningStep=fewestJumps(knowledge,allowedJumps,m,target); } } else{ std::cout<<"Not possible. \n"; } } int main(){ long m; std::cin>>m; if(m>0){ Point2D* allowedJumps = new Point2D[m]; for(long i=0;i < m;++i){ std::cin>>allowedJumps[i].x>>allowedJumps[i].y; } std::map<Point2D,FJInfo> knowledge; Point2D userInput; std::cin>>userInput.x>>userInput.y; while((userInput.x > 0)&&(userInput.y > 0)){ printfewestJumps(knowledge,allowedJumps,m,userInput); std::cin>>userInput.x>>userInput.y; } delete[] allowedJumps; } }

class TN{ public: long content; TN* aLeft; TN* aRight; };The implementation of the function

`f`

is given below
long f(TN* a, long h){ if(a==nullptr){ return 1; } long c=a->content; 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
`f(aRoot,3)`

? Provide a rigorous justification for your answer.
The function \(f\) is a recursion. The initial call to the function is made with arguments `a=aRoot`

and `h=3`

. The value of the pointer `a`

is different from `nullptr`

hence the function does not exit with the return value \(1\). Instead the return value is

`f(a->aLeft,4)`

+ `f(a->aRight,4)`

. Additional two calls are made to the function `f`

. We will denote by \(X_L\) and \(X_R\) the results of these two calls

**Evaluation of \(X_L=\)**`f(aRoot-> aLeft,4)`

In this evaluation the variable

\[X_L=9+X_{LR}.\]`a`

contains the pointer to the tree whose root contains the number \(59\). This time the value \(h\) is 4, which is even and only the evaluation of \(X_{LR}=\)`f(a->aRight,5)`

is relevant for the final result**Evaluation of \(X_{LR}=\)**`f(aRoot->aLeft->aRight,5)`

Since both \(h=5\) and \(c=519\) are odd numbers the value \(X_{LR}\) is calculated as

\(X_{LR}\)=9 + `f(a->aLeft,6)`

+`f(a->aRight,6)`

.Denote the last two quantities by \(X_{LRL}\) and \(X_{LRR}\) respectively.

**Evaluation of \(X_{LRL}=\)**`f(a->aLeft->aRight->aLeft,6)`

Since \(c\%10=0\), \(h\%2=0\), and \(c\%2=0\), the value \(X_{LRL}\) is equal to \(0\).

**Evaluation of \(X_{LRR}=\)**`f(a->aLeft->aRight->aRight,6)`

The value \(h=6\) is even, hence \(X_{LRR}=3+X_{LRRR}\), where

\(X_{LRRR}=\)

`f(a->aLeft->aRight->aRight->aRight,7)`

.**Evaluation of \(X_{LRRR}=\)**`f(a->aLeft->aRight->aRight->aRight,7)`

Since \(c\%2=0\), only the value

`f(a-> aLeft,8)`

is relevant for the result. Since`a-> aLeft`

is`nullptr`

the function returns \(1\) when applied to this argument. Therefore \(X_{LRRR}=4+1=5\).

We now conclude that \(X_{LRR}=3+X_{LRRR}=3+5=8\).

Having calculated \(X_{LRL}=0\) and \(X_{LRR}=8\) we conclude that \(X_{LR}=9+0+8=17\).

Having calculated \(X_{LR}=17\) we conclude that \(X_L=9+17=26\).

**Evaluation of \(X_R=\)**`f(aRoot-> aRight,4)`

Since \(h\) is even, the value \(X_R\) satisfies \(X_R=3+X_{RR}\) where \(X_{RR}=\)

`f(aRoot->aRight->aRight,5)`

. Since`aRoot->aRight->aRight=nullptr`

the value of the function is \(1\), hence \(X_{RR}=1\) and \(X_R=4\).

We obtained that \(X_L=26\) and \(X_R=4\). Therefore \[X_0=5+X_L+X_R=5+26+4=35.\] Thus the function returns \(35\).

The first step in the AVL algorithm is the insertion of the number \(55\) in the binary search tree without re-balancing. The resulting tree is

The next step in the algorithm is identifying the highest node that violates the AVL property. The only such node is the root \(r\) with content \(40\). The height of its left sub-tree is 2 while the height of its right sub-tree is 4. We now denote by \(c\) the right child. The content of the node \(c\) is \(70\).

The right child has the left sub-tree of height 3 and the right sub-tree of height 2. This means that we need double rotation. We denote by \(g\) the node whose content is \(50\). The left sub-tree breaks into the tree \(X_1\) with root 45 and the tree \(X_2\) with root \(60\). The right subtree of \(c\) is denoted by \(Z\) (its root is \(95\)).

We now apply the right rotation to the node \(c\). The node \(g\) updates its pointer to the right child to contain the address of the node \(c\). The left child of \(c\) becomes the node with content \(60\). The root \(r\) of the entire tree updates its right child to point to \(g\). After this right rotation the tree becomes

The next step is the left rotation applied to the root \(r\). Its right child becomes the pointer to the node whose content is \(45\). The node with content \(50\) updates its left child to point to the original root. The node with content \(50\) becomes the new root. The resulting tree is shown in the picture below.