Download the zip file $\backslash (\backslash$underset$\{\backslash$sim$\}\{\backslash$downarrow$\}\backslash )$ containing the source code for the Red Black tree. Use this script $\backslash (\backslash$downarrow $\backslash )$ to test your work.

Complete the implementation of rbtree.h by replacing TODOs with code. Do NOT modify the other files.

Submit rbtree.h only.

Tips:

$-$ height$()$ should be $-1$ for an empty tree.

$-$ The parent of root$\_$ is a typical nullptr $($not an actual node$).$

$-$ Check out node.h for all the fields and methods you can use to complete your implementation.

Note: your code MUST throw an exception when trying to insert a duplicate value. We will read and check your code for this and you will lose points if your code does anything other than throwing an exception in such case.

Provided Code:

void insert$($const K &key, const V &value$)\{$

Node $*$x $=$ root$\_,*$y $=$ nullptr;

$//$ TODO

$\}$

void delete$\_$tree$($Node $*$n$)\{$

$//$ TODO

$\}$

void insert$\_$fixup$($Node $*$z$)\{$

$//$ TODO

$//$ Last line below

root$\_->$color $=$ BLACK;

$\}$

void left$\_$rotate$($Node $*$x$)\{$

$//$ TODO

$\}$

void right$\_$rotate$($Node $*$x$)\{$

$//$ TODO

$\}$

$/**$

$*$ Returns the height of the red$-$black tree starting at node.

$*$ A null node starts at height $-1.$

$*/$

int height$($Node $*$node$)$ const $\{$

$//$ TODO

$\}$

$/**$

$*$ Returns the count of leaves in the red$-$black tree starting at node.

$*$ For this method, a leaf is a non$-$null node that has no children.

$*/$

size$\_$t leaf$\_$count$($Node $*$node$)$ const $\{$

$//$ TODO

$\}$

$/**$

$*$ Returns the count of internal nodes in the red$-$black tree starting at

$*$ node.

$*$ An internal node has at least one child.

$*/$

size$\_$t internal$\_$node$\_$count$($Node $*$node$)$ const $\{$

$//$ TODO

$\}$

$/**$

$*$ Helper method to assist in the computation of tree diameter.

$*/$

size$\_$t diameter$($Node $*$node$)$ const $\{$

$//$ TODO

$\}$

$/**$

$*$ Returns the width of the red$-$black tree at the designated level.

$*$ Width is defined as the number of nodes residing at a level.

$*/$

size$\_$t width$($Node $*$node$,$ size$\_$t level$)$ const $\{$

$//$ TODO

$\}$

size$\_$t null$\_$count$()$ const $\{$

return null$\_$count$($root$\_)$;

$\}$

$/**$

$*$ Returns the count of null pointers in the red$-$black tree starting at

$*$ node.

$*/$

size$\_$t null$\_$count$($Node $*$node$)$ const $\{$

$//$ TODO

$\}$

size$\_$t sum$\_$levels$()$ const $\{$

return sum$\_$levels$($root$\_,0)$;

$\}$

$/**$

$*$ Returns the sum of the levels of each non$-$null node in the red$-$black

$*$ tree starting at node.

$*$ For example, the tree

level $0$

$*/\backslash$

level $1$

$*\backslash$

level $2$

$*$ has sum $1*0+2*1+1*2=4.$

$*/$

size$\_$t sum$\_$levels$($Node $*$node$,$ size$\_$t level$)$ const $\{$

$//$ TODO

$\}$

size$\_$t sum$\_$null$\_$levels$()$ const $\{$

return sum$\_$null$\_$levels$($root$\_,0)$;

$\}$

$/**$

$*$ Returns the sum of the levels of each null node in the red$-$black tree

$*$ starting at node.

$*$ For example, the tree

level $0$

$*/\backslash$

level $1$

$*/\backslash /\backslash$

level $2$

$*/\backslash$

level $3$

$*$ has sum $3*2+2*3=12.$

$*/$

size$\_$t sum$\_$null$\_$levels$($Node $*$node$,$ size$\_$t level$)$ const $\{$

$//$ TODO

$\}$

$\}$;

#endif $/*$ RBTREE$\_$H$\_*/$