#include "bstSequence.h$"$

using namespace std;

void fix$\_$size$($Node $*$T$)$

$\{$

T$->$size $=1$;

if $($T$->$left$)$ T$->$size $+=$ T$->$left$->$size;

if $($T$->$right$)$ T$->$size $+=$ T$->$right$->$size;

$\}$

$/*$

$//$ insert key k into tree T$,$ returning a pointer to the resulting tree

Node $*$insert$($Node $*$T$,$ int k$)$

$\{$

if $($T $==$ nullptr$)$ return new Node$($k$)$;

if $($k $<$ T$->$key$)$ T$->$left $=$ insert$($T$->$left, k$)$;

else T$->$right $=$ insert$($T$->$right, k$)$;

fix$\_$size$($T$)$;

return T;

$\}$

$*/$

$//$ insert value v at rank r

Node $*$insert$($Node $*$T$,$ int v$,$ int r$)$

$\{$ if $($T $==$ nullptr$)$ return new Node$($v$)$; $//$ If the tree is empty, create a new node with the value v and return it

int rank$\_$of$\_$root $=$ T$->$left $?$ T$->$left$->$size : $0$; $//$ Calculate the rank of the root node

if $($r $<=$ rank$\_$of$\_$root$)//$ If the rank is less than or equal to the rank of the root, insert the value in the left subtree

T$->$left $=$ insert$($T$->$left, v$,$ r$)$;

else $//$ If the rank is greater than the rank of the root, insert the value in the right subtree

T$->$right $=$ insert$($T$->$right, v$,$ r $-$ rank$\_$of$\_$root $-1)$;

fix$\_$size$($T$)$; $//$ Update the size of the tree

return T; $//$ Return the modified tree

$\}$

$//$ returns a vector of key values corresponding to the inorder traversal of T $($i$.$e$.,$ the contents of T in sorted order$)$

vector inorder$\_$traversal$($Node $*$T$)$

$\{$

vector inorder;

vector rhs;

if $($T $==$ nullptr$)$ return inorder;

inorder$=$inorder$\_$traversal$($T$->$left$)$;

inorder.push$\_$back$($T$->$key$)$;

rhs$=$inorder$\_$traversal$($T$->$right$)$;

inorder.insert$($inorder$.$end$(),$ rhs$.$begin$(),$ rhs$.$end$())$;

return inorder;

$\}$

$//$ return pointer to node of rank r $($with r$\text{'}$th largest key; e$.$g$.$ r$=0$ is the minimum$)$

Node $*$select$($Node $*$T$,$ int r$)$

$\{$

assert$($T$!=$nullptr && r$>=0$ && rsize$)$;

int rank$\_$of$\_$root $=$ T$->$left $?$ T$->$left$->$size : $0$;

if $($r $==$ rank$\_$of$\_$root$)$ return T;

if $($r $<$ rank$\_$of$\_$root$)$ return select$($T$->$left, r$)$;

else return select$($T$->$right, r $-$ rank$\_$of$\_$root $-1)$;

$\}$

$//$ Split tree T on rank r into tree L $($containing ranks $<$ r$)$ and

$//$ a tree R $($containing ranks $>=$ r$)$

void split$($Node $*$T$,$ int r$,$ Node $**$L$,$ Node $**$R$)$

$\{$

$//$Implement void split$($Node $*$T$,$ int r$,$ Node $**$L$,$ Node $**$R$)$

$\}$

$//$ insert value v at rank r

Node $*$insert$\_$random$($Node $*$T$,$ int v$,$ int r$)$

$\{$

$//$ If $($v$,$r$)$ is the Nth node inserted into T$,$ then:

$//$ with probability $1/$N$,$ insert $($v$,$r$)$ at the root of T

$//$ otherwise, insert$\_$random $($v$,$r$)$ recursively left or right of the root of T

$//$Implement Node $*$insert$\_$random$($Node $*$T$,$ int v$,$ int r$)$

$\}$

$//$ Returns true if team x defeated team y

$//$ Leave this function unmodified

bool did$\_$x$\_$beat$\_$y$($int x$,$ int y$)$

$\{$

assert $($x $!=$ y$)$;

if $($x $>$ y$)$ return $!$did$\_$x$\_$beat$\_$y$($y$,$x$)$;

unsigned long long lx $=$ x;

unsigned long long ly $=$ y;

return $((17+8321813*$ lx $+1861*$ ly$)\%1299827)\%2==0$;

$\}$

$//$ Return a BST containing a valid ordering of n teams

Node $*$order$\_$n$\_$teams$($int n$)$

$\{$

Node $*$T $=$ nullptr;

$//$ start by inserting the first team

T $=$ insert$\_$random$($T$,0,0)$;

$//$ now insert the other teams...

for $($int i$=1$; ikey$))//$ can we insert at beginning?

T $=$ insert$\_$random$($T$,$ i$,0)$;

else if $($did$\_$x$\_$beat$\_$y$($select$($T$,$T$->$size$-1)->$key, i$))//$ can we insert at end?

T $=$ insert$\_$random$($T$,$ i$,$ T$->$size$)$;

else $\{$

$//75420316($when inserting team i$=8)$

$//$ W W W L L L W L

$\}$

$\}$

return T;

$\}$

void printVector$($vector v$)$

$\{$

for $($int i$=0$; i inorder;

Node $*$T $=$ nullptr;

$//$ test insert at beginning

for $($int i$=0$; i$<5$; i$++)$

T $=$ insert$($T$,$ i$+1,0)$;

cout $<<$ "Tree should contain $54321$:

$"$;

inorder$=$inorder$\_$traversal$($T$)$;

printVector$($inorder$)$;

$//$ test insert at end

for $($int i$=5$; i$<10$; i$++)$

T $=$ insert$($T$,$ i$+1,$ T$->$size$)$;

cout $<<$ "Tree should contain $54321678910$:

$"$;

inorder$=$inorder$\_$traversal$($T$)$;

printVector$($inorder$)$;

$//$ test insert at middle

for $($int i$=10$; i$<15$; i$++)$

T $=$ insert$($T$,$ i$+1,$ T$->$size$/2)$;

cout $<<$ "Tree should contain $543211214151311678910$:

$"$;

inorder$=$inorder$\_$traversal$($T$)$;

printVector$($inorder$)$;

$//$ once insert is working, the next step is to build the

$//$ insert$\_$random function $--$ to test this, just change

$//$ calls to insert above to insert$\_$random.

int N $=100000$; $//$ this should run quickly even for very large N$!$

Node $*$S $=$ order$\_$n$\_$teams$($N$)$;

if $($S $==$ nullptr $||$ S$->$size $!=$ N$)$

cout $<<$ "Size of tree returned by order$\_$n$\_$teams is wrong

$"$;

else $\{$

cout $<<$ "Team ordering:

$"$;

$//$ inorder$=$inorder$\_$traversal$($S$)$;

$//$ printVector$($i