In this task you will deal with inserting new nodes into red$-$black trees.

$($a$)$ First, start by implementing the insert method in the AbstractBinarySearchTree class. This method gets a new node and an initial value for the reference to the parent node px$.$ The method then inserts the node at the correct location.

To do this, implement the paste pseudocode from the lecture $($Lecture $03,$ Slide $71).$ Please note that we do not assume a specific implementation and therefore use the initialPX parameter instead of the sentinel node. For normal binary search trees this has the value zero, and for red$-$black trees it corresponds to the sentinel node.

$1$This is also asked about in the public tests.

$076/8$

$($b$)$ Additionally, implement the rotateLeft, rotateRight, and fixColorsAfterInsertion methods in the RBTree class. These methods are also given a start node and rotate or modify the corresponding nodes so that the conditions for a red$-$black tree are met again. For implementation, you can use the pseudocode from the lecture as a guide$2.$

$($c$)$ Finally, implement the insert method in the RBTree class. This method is passed a value and inserts the node into the tree using the previous methods. The insert method is first called and then the fixColorsAfterInsertion methods to fulfill the conditions of the red$-$black tree again. To create a node, use the createNode method.

package p$2.$binarytree;

import p$2.$SearchTree;

import java.util.List;

import java.util.function.Predicate;

import static org.tudalgo.algoutils.student.Student.crash;

$/**$

$*$ A base implementation of a binary search tree containing common methods.

$*$

$*$ It contains the root node of the tree and provides methods for searching and inserting elements.

$*$

$*$ It assumes that only binary nodes are used, i$.$e$.$ every node contains exactly one key and has at most two children,

$*$ where the left child is smaller than the parent and the right child is greater than the parent.

$*$

$*$ @param the type of the keys in the tree.

$*$ @param the type of the nodes in the tree, e$.$g$.,\{$@link BSTNode$\}$ or $\{$@link RBNode$\}.$

$*$ @see SearchTree

$*$ @see AbstractBinaryNode

$*/$

public abstract class AbstractBinarySearchTree, N extends AbstractBinaryNode$>$ implements BinarySearchTree $\{$

$/**$

$*$ The root node of the tree.

$*/$

protected N root;

@Override

public N search$($T value$)\{$

N x $=$ root;

while $($x $!=$ null && x$.$getKey$().$compareTo$($value$)!=0)\{$

if $($x$.$getKey$().$compareTo$($value$)>0)\{$

x $=$ x$.$getLeft$()$;

$\}$ else $\{$

x $=$ x$.$getRight$()$;

$\}$

$\}$

return x;

$\}$

$/**$

$*$ Inserts the given node into the tree.

$*$

$*$ @param node the node to insert.

$*$ @param initialPX The initial value used for the pointer to the parent node.

$*$ This is required for implementations that use a sentinel node. For normal trees, this value

$*$ should be $\{$@code null$\}.$

$*/$

protected void insert$($N node, N initialPX$)\{$

crash$()$; $//$TODO: H$2$ a$)-$ remove if implemented

$\}$

$/**$

$*$ Adds all elements in the subtree represented by the given node to the given list.

$*$

$*$ The elements are added in ascending order.

$*$ The method adds at most $\{$@code max$\}$ elements.

$*$ The method stops traversing the tree if the predicate returns $\{$@code false$\}$ for one of the elements and does

$*$ not add any further elements. The first element which did not satisfy the predicate is also excluded.

$*$ It assumes that the predicate returns $\{$@code false$\}$ for all greater values once it returned $\{$@code false$\}$ for

$*$ one value, i$.$e$.$ it represents a limit check.

$*$

$*$ @param node The root of the subtree to traverse.

$*$ @param result The list to store the elements in$.$

$*$ @param max The maximum number of elements to include in the result.

$*$ @param limit The predicate to test the elements against. If the predicate returns $\{$@code false$\}$ for an element,

$*$ the traversal stops.

$*/$

protected void inOrder$($N node, List result, int max, Predicate limit$)\{$

crash$()$; $//$TODO: H$3$ a$)-$ remove if implemented

$\}$

$/**$

$*$ Adds all elements in the tree that are greater than or equal to the given node to the given list.

$*$

$*$ The elements are added in ascending order.

$*$ The method adds at most $\{$@code max$\}$ elements.

$*$ The method stops traversing the tree if the predicate returns $\{$@code false$\}$ for one of the elements and does

$*$ not add any further elements. The first element which did not satisfy the predicate is also excluded.

$*$ It assumes that the predicate returns $\{$@code false$\}$ for all greater values once it returned $\{$@code false$\}$ for

$*$ one value, i$.$e$.$ it represents a limit check.

$*$

$*$ @param node The node to start the search from. The node itself is incl