use python to solve this problem

Create a red$-$black tree data structure that implements each of the methods using the

pseudocode from the textbook $($included at the end of this document$)$:

rbinsert

rblnsertFixup

leftRotate

rightRotate $($created in class$)$

rbTransplant

rbDelete

rbDeleteFixup

print$/$draw the tree $($make sure you source where you got the method if you don't

create a custom one yourself$).$

Insert the values shown in the RB tree below:

$($b$)$

Explain why when you insert the values they do or do not look like the tree above. pseducode is down below Here is the text transcription of the pseudocode:

LEFT$-$ROTATE$($T$,$ x$)$

go

Copy code

$1$ y $=$ x$.$right $//$ set y

$2$ x$.$right $=$ y$.$left $//$ turn y$\text{'}$s left subtree into x$\text{'}$s right subtree

$3$ if y$.$left $!=$ T$.$nil

$4$ y$.$left.p $=$ x

$5$ y$.$p $=$ x$.$p $//$ link x$\text{'}$s parent to y

$6$ if x$.$p $==$ T$.$nil

$7$ T$.$root $=$ y

$8$ elseif x $==$ x$.$p$.$left

$9$ x$.$p$.$left $=$ y

$10$ else x$.$p$.$right $=$ y

$11$ y$.$left $=$ x $//$ put x on y$\text{'}$s left

$12$ x$.$p $=$ y

RB$-$INSERT$($T$,$ z$)$

lua

Copy code

$1$ y $=$ T$.$nil

$2$ x $=$ T$.$root

$3$ while x $!=$ T$.$nil

$4$ y $=$ x

$5$ if z$.$key $$ x$.$key

$6$ x $=$ x$.$left

$7$ else x $=$ x$.$right

$8$ z$.$p $=$ y

$9$ if y $==$ T$.$nil

$10$ T$.$root $=$ z

$11$ elseif z$.$key $$ y$.$key

$12$ y$.$left $=$ z

$13$ else y$.$right $=$ z

$14$ z$.$left $=$ T$.$nil

$15$ z$.$right $=$ T$.$nil

$16$ z$.$color $=$ RED

$17$ RB$-$INSERT$-$FIXUP$($T$,$ z$)$ RB$-$INSERT$-$FIXUP$($T$,$ z$)$

csharp

Copy code

$1$ while z$.$p$.$color $==$ RED

$2$ if z$.$p $==$ z$.$p$.$p$.$left

$3$ y $=$ z$.$p$.$p$.$right

$4$ if y$.$color $==$ RED

$5$ z$.$p$.$color $=$ BLACK $//$ case $1$

$6$ y$.$color $=$ BLACK $//$ case $1$

$7$ z$.$p$.$p$.$color $=$ RED $//$ case $1$

$8$ z $=$ z$.$p$.$p $//$ case $1$

$9$ else

$10$ if z $==$ z$.$p$.$right

$11$ z $=$ z$.$p $//$ case $2$

$12$ LEFT$-$ROTATE$($T$,$ z$)//$ case $2$

$13$ z$.$p$.$color $=$ BLACK $//$ case $3$

$14$ z$.$p$.$p$.$color $=$ RED $//$ case $3$

$15$ RIGHT$-$ROTATE$($T$,$ z$.$p$.$p$)//$ case $3$

$16$ else $($same as then clause with "right" and "left" exchanged$)$

$17$ T$.$root.color $=$ BLACK

RB$-$TRANSPLANT$($T$,$ u$,$ v$)$

lua

Copy code

$1$ if u$.$p $==$ T$.$nil

$2$ T$.$root $=$ v

$3$ elseif u $==$ u$.$p$.$left

$4$ u$.$p$.$left $=$ v

$5$ else

$6$ u$.$p$.$right $=$ v

$7$ v$.$p $=$ u$.$pRB$-$DELETE$($T$,$ z$)$

scss

Copy code

$1$ y $=$ z

$2$ y$-$original$-$color $=$ y$.$color

$3$ if z$.$left $==$ T$.$nil

$4$ x $=$ z$.$right

$5$ RB$-$TRANSPLANT$($T$,$ z$,$ z$.$right$)$

$6$ elseif z$.$right $==$ T$.$nil

$7$ x $=$ z$.$left

$8$ RB$-$TRANSPLANT$($T$,$ z$,$ z$.$left$)$

$9$ else

$10$ y $=$ TREE$-$MINIMUM$($z$.$right$)$

$11$ y$-$original$-$color $=$ y$.$color

$12$ x $=$ y$.$right

$13$ if y$.$p $==$ z

$14$ x$.$p $=$ y

$15$ else

$16$ RB$-$TRANSPLANT$($T$,$ y$,$ y$.$right$)$

$17$ y$.$right $=$ z$.$right

$18$ y$.$right.p $=$ y

$19$ RB$-$TRANSPLANT$($T$,$ z$,$ y$)$

$20$ y$.$left $=$ z$.$left

$21$ y$.$left.p $=$ y

$22$ y$.$color $=$ z$.$color

$23$ if y$-$original$-$color $==$ BLACK

$24$ RB$-$DELETE$-$FIXUP$($T$,$ x$)$RB$-$DELETE$-$FIXUP$($T$,$ x$)$

scss

Copy code

$1$ while x $!=$ T$.$root and x$.$color $==$ BLACK

$2$ if x $==$ x$.$p$.$left

$3$ w $=$ x$.$p$.$right

$4$ if w$.$color $==$ RED

$5$ w$.$color $=$ BLACK $//$ case $1$

$6$ x$.$p$.$color $=$ RED $//$ case $1$

$7$ LEFT$-$ROTATE$($T$,$ x$.$p$)//$ case $1$

$8$ w $=$ x$.$p$.$right $//$ case $1$

$9$ if w$.$left.color $==$ BLACK and w$.$right.color $==$ BLACK

$10$ w$.$color $=$ RED $//$ case $2$

$11$ x $=$ x$.$p $//$ case $2$

$12$ else

$13$ if w$.$right.color $==$ BLACK

$14$ w$.$left.color $=$ BLACK $//$ case $3$

$15$ w$.$color $=$ RED $//$ case $3$

$16$ RIGHT$-$ROTATE$($T$,$ w$)//$ case $3$

$17$ w $=$ x$.$p$.$right $//$ case $3$

$18$ w$.$color $=$ x$.$p$.$color $//$ case $4$

$19$ x$.$p$.$color $=$ BLACK $//$ case $4$

$20$ w$.$right.color $=$ BLACK $//$ case $4$

$21$ LEFT$-$ROTATE$($T$,$ x$.$p$)//$ case $4$

$22$ x $=$ T$.$root $//$ case $4$

$23$ else $($same as then clause with "right" and "left" exchanged$)$

$24$ x$.$color $=$ BLACK