Question

Part B (BI). Implement a Red-Black tree with only operation Insert(). Your program should read from a file that contain positive integers and should insert those numbers into the RB tree in that order. Note that the input file will only contain distinct integers. Print your tree by level using positive values for Black color and negative values for Red color Do not print out null nodes. Format for a node: , ). For example, the following tree is represented as (12, null 12 (5, 12) (15, 12) 15 (3, 5) -10, 5) 13, 15) (17, 15) 3 10 13 17 (-4, 3) (7, -10) (1, -10) (-14, 13) 7 11 14 (-6, 7) (-8, 7) 6 (B2). Implement a randomized Skip-List with operations Insert(), Delete() and Search). Your program should read from the input file just like in (BI). Print out the skip-list using the format given below 16 16 71 9 2 16 71 89 91 (B2). Implement a randomized Skip-List with operations Insert(), Delete() and Search(). Your program should read from the input file just like in (BI). Print out the skip-list using the format given below 16 16 71 9 16 2 16 71 89 91 89H 2 10 15 16 31 71 86 89 91 96 ** (B3). Implement Dijkstra's algorithm destination "u v" in the first row, and (2) the edge list with the associated weight (of type double) for each edge in the on an undirected graph. The input file would contain (I) the pair of source and graph. Output the sequence of nodes that are on the shortest path from "u" to "V" with the total weight. Provide your own test cases. Turn in your code and test cases (i.e., ".java" or ".c/.cpp" and test files) only. Note: RECURSION is NOT allowed at allI. Your implementation can only contain iterative methods Part C Implement MERGE-SORT() algorithm that reads from a file named "inputHW02.txt" a list of double numbers (max = 3,000,000 numbers), sorts those numbers and indicates time consumption. This programming question will address the advantage of using iteration loops over recursive calls as well as using INSERTION-SORT() as a procedure in MERGE- SORT() Your program must perform the following actions: I. Opens the given file name and reads all double numbers. For simplicity, we assume this file only contains numbers and nothing else. 2. Implements the function INSERTION-SORT() that only sort an array of maximum 25 numbers. The idea is that INSERTION-SORT() will be used as a sub-procedure to sort any sub-array when its size is small enough. 3. Four versions of MERGE-SORT() namely MERGE-SORT-A(): Using recursive calls and NO INSERTION-SORT() as a sub-procedure MERGE-SORT-B(): Using ITERATIVE loops (i.e, NO recursion) and NO INSERTION-SORT() as a sub- procedure. MERGE-SORT-C(): Using recursive calls and INSERTION-SORT() as a sub-procedure. d. a. C. MERGE-SORT-D(): Using ITERATIVE loops (i.e, NO recursion) and INSERTION-SORT() as a sub- procedure

Answer 1

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
class Node
{
    Node left, right;
    int ele;
    int colour;

    public Node (int element)
    {
        this( element, null, null );
    }
    public Node (int theElement, Node lt, Node rt)
    {
        left = lt;
        right = rt;
        ele = theElement;
        colour = 1;
    }
}
class RBTree
{
    private Node curr;
    private Node parent;
    private Node gra;
    private Node gre;
    private Node header;
    private static Node nullNode;
    static
    {
        nullNode = new Node(0);
        nullNode.left = nullNode;
        nullNode.right = nullNode;
    }
    static final int BLACK = 1; // Black - 1 RED - 0
    static final int RED = 0;

    public RBTree(int negInt)
    {
        header = new Node(negInt);
        header.left = nullNode;
        header.right = nullNode;
    }
    public boolean isEmpty()
    {
        return header.right == nullNode;
    }

    public void insert(int item ) // Function to insert item
    {
        curr = parent = gra = header;
        nullNode.ele = item;
        while (curr.ele != item)
        {
            gre = gra;
            gra = parent;
            parent = curr;
            curr = item < curr.ele ? curr.left : curr.right;   //conditional statement
            if (curr.left.colour == RED && curr.right.colour == RED)
                handleReorient( item );
        }
        if (curr != nullNode)       //insertion check
            return;
        curr = new Node(item, nullNode, nullNode);
        if (item < parent.ele)
            parent.left = curr;
        else
            parent.right = curr;
        handleReorient( item );
    }
    private void handleReorient(int item)
    {
        curr.colour = RED;
        curr.left.colour = BLACK;
        curr.right.colour = BLACK;

        if (parent.colour == RED)
        {
            gra.colour = RED;
            if (item < gra.ele != item < parent.ele)
                parent = rotate( item, gra );
            curr = rotate(item, gre );
            curr.colour = BLACK;
        }
        header.right.colour = BLACK;
    }
    private Node rotate(int item, Node p)
    {
        if(item < p.ele)
            return p.left = item < p.left.ele ? rotateWithLeftChild(p.left) : rotateWithRightChild(p.left) ;
        else
            return p.right = item < p.right.ele ? rotateWithLeftChild(p.right) : rotateWithRightChild(p.right);
    }
    private Node rotateWithLeftChild(Node k3)   // Rotate binary tree node with left child
    {
        Node k1 = k3.left;
        k3.left = k1.right;
        k1.right = k3;
        return k1;
    }
    private Node rotateWithRightChild(Node k3)   // Rotate binary tree node with right child
    {
        Node k2 = k3.right;
        k3.right = k2.left;
        k2.left = k3;
        return k2;
    }

    public void inorder()   //traverse
    {
        inorder(header.right);
    }
    private void inorder(Node r)   //traverse
    {
        if (r != nullNode)
        {
            inorder(r.left);
            char c = 'b';
            if (r.colour == 0)
                c = 'r';
            System.out.print(r.ele +""+c+" ");
            inorder(r.right);
        }
    }
    public void preorder()   //traverse
    {
        preorder(header.right);
    }
    private void preorder(Node r)   //traverse
    {
        if (r != nullNode)
        {
            char c = 'b';
            if (r.colour == 0)
                c = 'r';
            System.out.print(r.ele +""+c+" ");
            preorder(r.left);
            preorder(r.right);
        }
    }
    public void postorder()   //traverse
    {
        postorder(header.right);
    }
    private void postorder(Node nod)   //traverse
    {
        if (nod != nullNode)
        {
            postorder(nod.left);
            postorder(nod.right);
            char ch = 'B';
            if (nod.colour == 0)
                ch = 'R';
            System.out.print(nod.ele +""+ch+" ");
        }
    }
}

public class MyMain
{
    public static void main(String[] args) throws FileNotFoundException
    {
        Scanner scan = new Scanner(System.in);
        RBTree rbt = new RBTree(Integer.MIN_VALUE);
        Scanner scanner = new Scanner(new File("test.txt"));
        int [] arr = new int [100];
        int i = 0;
        while(scanner.hasNextInt())
        {
            arr[i++] = scanner.nextInt();
        }

        for (i=0; i<arr.length; i++)
        {
            rbt.insert(arr[i]);
        }
        System.out.print("\nPost order : ");
        rbt.postorder();
        System.out.print("\nPre order : ");
        rbt.preorder();
        System.out.print("\nIn order : ");
        rbt.inorder();

        char ch; //use this block of code for user input
        /* do
        {
        System.out.println("\nEnter Your Choice:\n");
        System.out.println("1. Insert ");
        System.out.println("2. Display ");

        int choice = scan.nextInt();
        switch (choice)
        {
        case 1 :
        System.out.println("Enter integer element to insert");
        rbt.insert( scan.nextInt() );
        break;
        case 2 :
        System.out.print("\nPost order : "+rbt.postorder()+"\nPre order : "+rbt.preorder()+"\nIn order : "+rbt.inorder());
        break;

        default :
        System.out.println("Wrong Entry \n ");
        break;
        }
        System.out.println("\nDo you want to continue (Type y or n) \n");
        ch = scan.next().charAt(0);
        } while (ch == 'Y'|| ch == 'y');
        */
    }
}

Svstem out nrint ("\nIn order. 195 Output Recruitersa 7 (run) x Recruitersa_7 (run) #2 x 2. Display 2 Post order 1R 4R 2B 7B 28R 15B 13R 5B Pre order 5B 2B 1R 4R 13R 7B 15B 28R In order :1R 2B 4R 5B 7B 13R 15B 28R Output