(Code in Java)
Using the binary search tree (BST) data structure, we can sort a sequence of n elements by first calling an
insertion procedure for n times to maintain a BST, and then performing an Inorder-Tree-Walk on the
BST to output the elements in sorted order.
The improved insertion procedure will make
• 2 comparisons to insert a node with key = 1
• 3 comparisons to insert a node with key = 3
• 2 comparisons to insert a node with key = 8
Program Requirements
In this programming assignment, you will implement in Java this sorting algorithm using BST, by using
the improved insertion procedure. Note that each node of a BST is an object containing four attributes:
key (for the value of an element), lef t (for its left child), right (for its right child), and p (for its parent).
Please add a static counter to track the number of key comparisons made by your algorithm. Your program
will output the following
1. The size of the input array,
2. The input array,
3. The list of array elements after sorting, and
4. The number of key comparisons made.
Extracted text: Problem Description Using the binary search tree (BST) data structure, we can sort a sequence of n elements by first calling an insertion procedure for n times to maintain a BST, and then performing an INORDER-TREE-WALK on the BST to output the elements in sorted order. To insert a node, we've discussed the TREE-INSERT procedure in class (also from page 294 of the text- book). This TREE-INSERT procedure can actually be improved to reduce the number of key comparisons so that each node's key is compared with the new node's key for at most once during each insertion. For example, given the following BST, 6. The improved insertion procedure will make 2 comparisons to insert a node with key = 1 8. 3 comparisons to insert a node with key = 3 2 comparisons to insert a node with key = 8 Program Requirements In this programming assignment, you will implement in Java this sorting algorithm using BST, by using the improved insertion procedure. Note that each node of a BST is an object containing four attributes: key (for the value of an element), left (for its left child), right (for its right child), and p (for its parent). Please add a static counter to track the number of key comparisons made by your algorithm. Your program will output the following 1. The size of the input array, 2. The input array, 3. The list of array elements after sorting, and 4. The number of key comparisons made.