Red-Black Tree - Question 4 Answers

\begin{algorithm}
\caption{Red-Black Tree}
\begin{algorithmic}
\REQUIRE T = red-black tree
\REQUIRE node = tree node to delete
\REQUIRE NULL-NODE = global variable representing a black leaf node
\FUNCTION{delete}{T, node}
    \STATE original-color $\gets$ node.color
    \STATE replacement \COMMENT{declare replacement variable}
    \IF{node has 0 or 1 child}
        \STATE child \COMMENT{declare child variable}
        \IF{node.left = NULL-NODE}
            \STATE child $\gets$ node.right \COMMENT{In the case of 0 children, child will equal NULL-NODE}
        \ELSE
            \STATE child $\gets$ node.left
        \ENDIF
        \STATE replacement $\gets$ child
        \STATE child.parent $\gets$ node.parent
        \IF{node.parent.left = node}
            \STATE node.parent.left $\gets$ child
        \ELSE
            \STATE node.parent.right $\gets$ child
        \ENDIF
    \ELSE \COMMENT{branch executed if there are two children}
        \STATE biggest-left $\gets$ \CALL{max}{node.left}
        \STATE original-color $\gets$ biggest-left.color
        \STATE swap values from node and biggest-left \COMMENT{values only, each node retains it's color}
        \STATE \CALL{delete}{T, biggest-left}
    \ENDIF
    \IF{original-color = BLACK}
        \STATE \CALL{balance}{T, replacement}
    \ENDIF
\ENDFUNCTION
\STATE
\REQUIRE T = red-black tree
\REQUIRE node = starting point for rebalancing
\FUNCTION{balance}{T, node}
    \STATE sibling \COMMENT{declare sibling variable}
    \WHILE{node $\neq$ T.root AND node.color = BLACK}
        \IF{node = node.parent.left}
            \STATE sibling = node.parent.right;
            \IF{sibling.color = RED}
                \STATE sibling.color $\gets$ BLACK
                \STATE node.parent.color = RED;
                \STATE \CALL{leftRotate}{T, node.parent}
                \STATE sibling $\gets$ node.parent.right
            \ENDIF
            \STATE
            \IF{sibling.left.color = BLACK AND sibling.right.color = BLACK}
               \STATE sibling.color $\gets$ RED
               \STATE node $\gets$ node.parent
            \ELSE
                \IF{sibling.right.color = BLACK}
                    \STATE sibling.left.color $\gets$ BLACK
                    \STATE sibling.color $\gets$ RED
                    \STATE \CALL{rightRotate}{T, sibling}
                    \STATE sibling $\gets$ node.parent.right
                \ENDIF
                \STATE
                \STATE sibling.color $\gets$ node.parent.color
                \STATE node.parent.color $\gets$ BLACK
                \STATE sibling.right.color $\gets$ BLACK
                \STATE \CALL{leftRotate}{T, node.parent}
                \STATE node $\gets$ tree.root
            \ENDIF
        \ELSE
            \STATE sibling = node.parent.left;
            \IF{sibling.color = RED}
                \STATE sibling.color $\gets$ BLACK
                \STATE node.parent.color = RED;
                \STATE \CALL{rightRotate}{T, node.parent}
                \STATE sibling $\gets$ node.parent.left
            \ENDIF
            \STATE
            \IF{sibling.left.color = BLACK AND sibling.right.color = BLACK}
               \STATE sibling.color $\gets$ RED
               \STATE node $\gets$ node.parent
            \ELSE
                \IF{sibling.left.color = BLACK}
                    \STATE sibling.right.color $\gets$ BLACK
                    \STATE sibling.color $\gets$ RED
                    \STATE \CALL{leftRotate}{T, sibling}
                    \STATE sibling $\gets$ node.parent.left
                \ENDIF
                \STATE
                \STATE sibling.color $\gets$ node.parent.color
                \STATE node.parent.color $\gets$ BLACK
                \STATE sibling.left.color $\gets$ BLACK
                \STATE \CALL{rightRotate}{T, node.parent}
                \STATE node $\gets$ tree.root
            \ENDIF
        \ENDIF
        \STATE
        \STATE node.color $\gets$ BLACK
    \ENDWHILE
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}