$***$ No STLs are allowed $***$ answer in c$++$ also use the provided material

Implement the splay$()$ operation as discussed in class. Some incomplete codes are given the attachment as hints. Two testing examples are given below.

Example $1$:

Original tree:

After Slay$($T$)$:

$***$ No STLs are allowed $***$

Example $2$:

After Slay$($R$)$:

class BSTree$\{$

public:

Node $*$root;

BSTree$($Node $*$r$)\{$

root $=$ r;

$\}$

void print$()\{$

root$->$print$(0)$;

cout endl;

$\}$

void rotateRight$($Node $*$Gr$,$ Node $*$Par$,$ Node $*$Ch$)\{$

if $($Gr $!=$ NULL$)\{$

$//$ grandparent Gr of child Ch becomes Chs parent Par

Par$->$left $=$ Ch$->$right;

if $($Ch$->$right $!=$ NULL$)\{$

Ch$->$right$->$parent $=$ Par;

$\}$

$//$ node Ch acquires Par as its right child

Ch$->$right $=$ Par;

Par$->$parent $=$ Ch;

Gr$->$right $=$ Ch; $//$ What if Par was the left child of Gr $?$

Ch$->$parent $=$ Gr;

$\}$

$//$ What if Gr $==$ NULL $?$

$\}$

void rotateLeft$($Node $*$Gr$,$ Node $*$Par$,$ Node $*$Ch$)\{$

if $($Gr $!=$ NULL$)\{$

$//$ grandparent Gr of child Ch becomes Chs parent Par

Par$->$right $=$ Ch$->$left;

if $($Ch$->$left $!=$ NULL$)\{$

Ch$->$left$->$parent $=$ Par;

$\}$

$//$ node Ch acquires Par as its left child

Ch$->$left $=$ Par;

Par$->$parent $=$ Ch;

Gr$->$left $=$ Ch; $//$ What if Par was the right child of Gr $?$

Ch$->$parent $=$ Gr;

$\}$

$//$ What if Gr $==$ NULL $?$

$\}$

Node$*$ search$($string data$)\{$

$//$ works for the toy example, needs to be replaced by binary search

return root$->$right$->$left$->$left;

$\}$

void splay$($string data$)\{$

Node$*$ Ch $=$ search$($data$)$;

Node$*$ Par $=$ Ch$->$parent;

Node$*$ Gr $=$ Par$->$parent;

if $($Gr $==$ NULL$)$

rotateRight$($Gr$,$ Par, Ch$)$; $//$ or rotateLeft

else $\{$

$//$ Zig Zig

if $($Gr$->$left $==$ Par && Par$->$left $==$ Ch$)\{$

rotateRight$($Gr$->$parent, Gr$,$ Par$)$;

print$()$;

$//$Ch was pushed up$,$ hence having new Par and Gr

Par $=$ Ch$->$parent;

Gr $=$ Par$->$parent;

rotateRight$($Gr$,$ Par, Ch$)$;

print$()$;

$\}$

$//$ Zig Zag

else if $($Gr$->$left $==$ Par && Par$->$right $==$ Ch$)\{$

rotateLeft$($Gr$,$Par,Ch$)$;

print$()$;

$//$Ch was pushed up$,$ hence having new Par and Gr

Par $=$ Ch$->$parent;

Gr $=$ Par$->$parent;

rotateRight$($Gr$,$Par,Ch$)$;

$\}$

$//$ Zag Zig

$//$ Zag Zag

$\}$

$\}$