Binary Search Tree Implementation(Java) In the binary search tree implementation, which is completely unrelated to the linked list implementation above, you will use an unbalanced binary search tree. Since duplicates are allowed, each node will have to store a singly-linked list of all the entries that are considered identical. Two values are identical if the comparator returns 0, even if the objects are unequal according to the equals method.
Binary Search Tree Implementation(Java)
In the binary search tree implementation, which is completely unrelated to the linked list implementation above, you will use an unbalanced binary search tree. Since duplicates are allowed, each node will have to store a singly-linked list of all the entries that are considered identical. Two values are identical if the comparator returns 0, even if the objects are unequal according to the equals method. A sketch of the private representation looks something like this:
private Comparator<? super AnyType> cmp;
private Node<AnyType> root = null;
private void toString( Node<AnyType> t, StringBuffer sb )
{ ... the recursive routine to be called by toString ... }
private static class Node<AnyType>
{
private Node<AnyType> left;
private Node<AnyType> right;
private ListNode<AnyType> items;
private static class ListNode<AnyType>
{
private AnyType data;
private ListNode<AnyType> next;
public ListNode( AnyType d, ListNode<AnyType> n )
{ data = d; next = n; }
}
public Node( AnyType data )
{
left = right = null;
items = new ListNode<AnyType>( data, null );
}
}
In accessing objects of type ListNode from the TreeDoubleEndedPriorityQueue class, it may be necessary to use Node.ListNode as the qualified class name, depending on the context. Of course, ListNode cannot be viewed from outside TreeDoubleEndedPriorityQueue.
Observe that when you insert or remove into the double-ended priority queue, (tree) nodes are created only when you add an element that does not compare to 0 with any other element in the tree. Tree nodes are removed only when the item to be removed was the only item in its node.
You will definitely need to use recursion to implement toString, and you must use string buffers with appends to avoid quadratic behavior. The other routines do not necessarily require recursion but the use of recursion is at your discretion and may simplify some logic.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
