The solution to the problem from the video 2:
#include\(<\)iostream\(>\)
#include\(<\)map\(>\)
class Point2D{
public:
\(\quad\)long x;
\(\quad\)long y;
\(\quad\)int operator\(<\)(const Point2D&) const;
\(\quad\)void operator+=(const Point2D &);
\(\quad\)void operator-=(const Point2D &);
};
int Point2D::operator\(<\)(const Point2D& b) const{
\(\quad\)if(x\(<\)b.x){
\(\quad\quad\)return 1;
\(\quad\)}
\(\quad\)if(x\(>\)b.x){
\(\quad\quad\)return 0;
\(\quad\)}
\(\quad\)if(y\(<\)b.y){
\(\quad\quad\)return 1;
\(\quad\)}
\(\quad\)return 0;
}
void Point2D::operator+=(const Point2D& b){
\(\quad\)x+=b.x;
\(\quad\)y+=b.y;
}
void Point2D::operator-=(const Point2D& b){
\(\quad\)x-=b.x;
\(\quad\)y-=b.y;
}
class FJInfo{
public:
\(\quad\)long spLength;
\(\quad\)Point2D lastJump;
\(\quad\)FJInfo();
};
FJInfo::FJInfo(){
\(\quad\)spLength=0;lastJump.x=0;lastJump.y=0;
}
FJInfo fewestJumps(std::map\(<\)Point2D,FJInfo\(>\)& knowledge, Point2D* allowedJumps, long m, Point2D target){
\(\quad\)FJInfo wJump;
\(\quad\)if((target.x==0)&&(target.y==0)){
\(\quad\quad\)return wJump;
\(\quad\)}
\(\quad\)wJump.spLength=-1;
\(\quad\)if((target.x\(<\)0)||(target.y\(<\)0)){
\(\quad\quad\)return wJump;
\(\quad\)}
\(\quad\)std::map\(<\)Point2D,FJInfo\(>\)::iterator iSearch;
\(\quad\)iSearch=knowledge.find(target);
\(\quad\)if(iSearch!=knowledge.end()){
\(\quad\quad\)return iSearch-\(>\)second;
\(\quad\)}
\(\quad\)long i=0;
\(\quad\)Point2D targetForEmployee;
\(\quad\)FJInfo wJumpEmployee;
\(\quad\)while(i\(<\)m){
\(\quad\quad\quad\)targetForEmployee=target;
\(\quad\quad\quad\)targetForEmployee-=allowedJumps[i];
\(\quad\quad\quad\)if((targetForEmployee.x \(>\) -1)&&(targetForEmployee.y \(>\) -1)){
\(\quad\quad\quad\quad\quad\)iSearch=knowledge.find(targetForEmployee);
\(\quad\quad\quad\quad\quad\)if(iSearch!=knowledge.end()){
\(\quad\quad\quad\quad\quad\quad\quad\)wJumpEmployee=iSearch-\(>\)second;
\(\quad\quad\quad\quad\quad\)}
\(\quad\quad\quad\quad\quad\)else{
\(\quad\quad\quad\quad\quad\quad\quad\)wJumpEmployee=fewestJumps(knowledge,allowedJumps,m,targetForEmployee);
\(\quad\quad\quad\quad\quad\)}
\(\quad\quad\quad\quad\quad\)if(wJumpEmployee.spLength \(>\) -1){
\(\quad\quad\quad\quad\quad\quad\quad\)if( (wJump.spLength==-1) || (wJump.spLength \(>\) wJumpEmployee.spLength+1) ){
\(\quad\quad\quad\quad\quad\quad\quad\quad\quad\)wJump.spLength=wJumpEmployee.spLength+1;
\(\quad\quad\quad\quad\quad\quad\quad\quad\quad\)wJump.lastJump=allowedJumps[i];
\(\quad\quad\quad\quad\quad\quad\quad\)}
\(\quad\quad\quad\quad\quad\)}
\(\quad\quad\quad\)}
\(\quad\quad\quad\)++i;
\(\quad\)}
\(\quad\quad\)knowledge[target]=wJump;
\(\quad\)return wJump;
}
void printfewestJumps(std::map\(<\)Point2D,FJInfo\(>\)& knowledge, Point2D* allowedJumps, long m, Point2D target){
\(\quad\)FJInfo winningStep=fewestJumps(knowledge,allowedJumps,m,target);
\(\quad\)if(winningStep.spLength \(>\) -1){
\(\quad\quad\)std::cout\(<\)\(<\)"The length of the shortest path from (0,0) to (";
\(\quad\quad\)std::cout\(<\)\(<\)target.x\(<\)\(<\)","\(<\)\(<\)target.y\(<\)\(<\)") is "\(<\)\(<\)winningStep.spLength\(<\)\(<\)".\n";
\(\quad\quad\)std::cout\(<\)\(<\)"The steps are:\n";
\(\quad\quad\)Point2D currentStart; currentStart.x=0;currentStart.y=0;
\(\quad\quad\)while( (target.x \(>\) 0) || (target.y \(>\) 0) ){
\(\quad\quad\quad\)std::cout\(<\)\(<\)"("\(<\)\(<\)currentStart.x\(<\)\(<\)","\(<\)\(<\)currentStart.y\(<\)\(<\)") ---\(>\) ";
\(\quad\quad\quad\)currentStart+=winningStep.lastJump;
\(\quad\quad\quad\)std::cout\(<\)\(<\)"("\(<\)\(<\)currentStart.x\(<\)\(<\)","\(<\)\(<\)currentStart.y\(<\)\(<\)")\(\quad\)";
\(\quad\quad\quad\)std::cout\(<\)\(<\)"Jump: \(<\)"\(<\)\(<\)winningStep.lastJump.x \(<\)\(<\)","\(<\)\(<\) winningStep.lastJump.y\(<\)\(<\)"\(>\)\n";
\(\quad\quad\quad\)target-=winningStep.lastJump;
\(\quad\quad\quad\)winningStep=fewestJumps(knowledge,allowedJumps,m,target);
\(\quad\quad\)}
\(\quad\)}
\(\quad\)else{
\(\quad\quad\quad\)std::cout\(<\)\(<\)"Not possible. \n";
\(\quad\)}
}
int main(){
\(\quad\)long m;
\(\quad\)std::cin\(>\)\(>\)m;
\(\quad\)if(m\(>\)0){
\(\quad\quad\)Point2D* allowedJumps = new Point2D[m];
\(\quad\quad\)for(long i=0;i \(<\) m;++i){
\(\quad\quad\quad\)std::cin\(>\)\(>\)allowedJumps[i].x\(>\)\(>\)allowedJumps[i].y;
\(\quad\quad\)}
\(\quad\quad\)std::map\(<\)Point2D,FJInfo\(>\) knowledge;
\(\quad\quad\)Point2D userInput;
\(\quad\quad\)std::cin\(>\)\(>\)userInput.x\(>\)\(>\)userInput.y;
\(\quad\quad\)while((userInput.x \(>\) 0)&&(userInput.y \(>\) 0)){
\(\quad\quad\quad\)printfewestJumps(knowledge,allowedJumps,m,userInput);
\(\quad\quad\quad\)std::cin\(>\)\(>\)userInput.x\(>\)\(>\)userInput.y;
\(\quad\quad\)}
\(\quad\quad\)delete[] allowedJumps;
\(\quad\)}
}
class TN{
public:
\(\quad\quad\)long content;
\(\quad\quad\)TN* aLeft;
\(\quad\quad\)TN* aRight;
};
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);
}
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+\mbox{f(a-\gneq aLeft,4)}+\mbox{f(a-\gneq 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
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}.\]
Since both \(h=5\) and \(c=519\) are odd numbers the value \(X_{LR}\) is calculated as \[X_{LR}=9+\mbox{f(a-\gneq aLeft,6)}+\mbox{f(a-\gneq aRight,6)}.\] Denote the last two quantities by \(X_{LRL}\) and \(X_{LRR}\) respectively.
Since \(c%10=0\), \(h%2=0\), and \(c%2=0\), the value \(X_{LRL}\) is equal to \(0\).
The value \(h=6\) is even, hence \(X_{LRR}=3+X_{LRRR}\), where \(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\).
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.