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