Need to be implemented in Java

A linked list consists of a sequence of nodes where elements (keys) are stored. Each node has a pointer to the next node. The first node is called head, the rest is called tail. Searching in a linked list is recursively starting with the head: if an element is not in the head, we continue to search in the tail. An element is inserted at the end of the list. If we want to delete an element, we need to first find it, and then modify the pointers appropriately.

A binary search tree is an ordered rooted tree, where each node has at most two children. Elements stored in nodes are called keys. In an ordered tree, we have that, for an arbitrary node v, all the elements (keys) in the left subtree are smaller then the key stored in v, while all the elements (keys) in the right subtree are grater then the key stored in v. Searching in a tree is recursively from the root to the leaf: if the searched element (key) is equal to the element (key) in the current node, we return the searched node.

Otherwise, if the searched element (key) is smaller then the element (key) in the current node, we continue to search in the left subtree, otherwise we continue in the right subtree. An element is inserted in the left subtree if it is smaller that the current node or in the right subtree if it is greater. To delete an element we need to first find the node in which it is stored.

Then we consider three different cases: (i) if the node has no successors, we simply delete the node; (ii) if the node has one subtree, we replace the node (and element) with its child; (iii) if the node has both subtrees, we replaced the node with the one in the right subtree that stores the minimal element (such a node is the left-most node in the right subtree).

You need to implement recursive data structures, namely, a linked list and a binary search tree. You should follow the following instructions. - In the class NodeSeznam, you can add the component, say tail, which is of type NodeSeznam, and add a constructor. Integers being inserted in the list are stored as keys in objects of type NodeSeznam. To compare keys (elements) you must use the method compare(NodeSeznam node), because the latter is used to test the correctness and efficiency of your solution.

For this purpose, it is useful to add the methods insert(NodeSeznam node), delete((NodeSeznam node) and search((NodeSeznam node) in this class, which can than be used in the class Seznam. - In the class Seznam you should implement the following methods: 3

(i) insert, which takes an integer and inserts it in the list. The method should return true, if the element is successfully inserted, and false, if the element is already in the data structure;

(ii) search, which takes an integer and finds an element in the list. The method returns true, if the element is already in the list, and false otherwise;

(iii) delete, which takes an integer and deletes an element from the list. The method returns true, if the element is successfully deleted, and false otherwise. - In the class NodeBinarno you can add components, say, left and right child of type NodeBinarno, and add a constructor. Integers being inserted in the tree are stored as keys in objects of type NodeBinarno.

To compare keys (elements) you must use the method compare(NodeBinarno node), because the latter is used to test the correctness and efficiency of your solution. For this purpose, it is useful to add the methods insert(NodeBinarno node), delete(NodeBinarno node) and search(NodeBinarno node) in this class, which can than be used in the class Binarno. - In the class Binarno you should implement the following methods:

(i) insert, which takes an integer and inserts it in the tree. The method should return true, if the element is successfully inserted, and false, if the element is already in the data structure;

(ii) search, which takes an integer and finds an element in the tree. The method returns true, if the element is already in the list, and false otherwise;

(iii) delete, which takes an integer and deletes an element from the tree. The method returns true, if the element is successfully deleted, and false, if the element has not been in the data structure. If the node has both the left and right subtree, you should replaced it with the minimal element in the right subtree. For this purpose, it is useful to add also the method findMin() in the class NodeBinarno.