Videos About Trees, Sets, and Maps

Summary

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;
  }
}

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

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

A binary search tree with 8 nodes. The root is 75, with left child 59 and right child 193. Node 59 has left child 201 (a leaf) and right child 519. Node 519 has left child 510 (a leaf) and right child 323. Node 323 has no left child and right child 24 (a leaf). Node 193 has left child 727 and no right child. Node 727 has no left child and right child 28 (a leaf).

What is the result of the evaluation 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

\(X_0\)=5 + 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 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
\[X_L=9+X_{LR}.\]
- 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\).

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