test with 1 2 3 4 5 6 7 8 9 10

import java.util.NoSuchElementException; public class RedBlackBST { private static final boolean RED = true; private static final boolean BLACK = false; private Node root; // root of the BST // BST helper node data type private class Node { private int key; // key private Node left, right; // links to left and right subtrees private boolean color; // color of parent link private int size; // subtree count public Node(int key, boolean color, int size) { this.key = key; this.color = color; this.size = size; } } public RedBlackBST() { } /*************************************************************************** * Node helper methods. ***************************************************************************/ // is node x red; false if x is null ? private boolean isRed(Node x) { if (x == null) return false; return x.color == RED; } // number of node in subtree rooted at x; 0 if x is null private int size(Node x) { if (x == null) return 0; return x.size; } /** * Returns the number of key-value pairs in this symbol table. * @return the number of key-value pairs in this symbol table */ public int size() { return size(root); } /** * Is this symbol table empty? * @return {@code true} if this symbol table is empty and {@code false} otherwise */ public boolean isEmpty() { return root == null; } /*************************************************************************** * Red-black tree insertion. ***************************************************************************/ /** * Inserts the specified key-value pair into the symbol table, overwriting the old * value with the new value if the symbol table already contains the specified key. * Deletes the specified key (and its associated value) from this symbol table * if the specified value is {@code null}. * * @param key the key * @param val the value * @throws NullPointerException if {@code key} is {@code null} */ public void put(int key) { root = put(root, key); root.color = BLACK; } // insert the key-value pair in the subtree rooted at h private Node put(Node h, int key) { if (h == null) return new Node(key, RED, 1); int cmp = key - h.key; if (cmp  0) h.right = put(h.right, key); else h.key = key; // fix-up any right-leaning links if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (isRed(h.left) && isRed(h.right)) flipColors(h); h.size = size(h.left) + size(h.right) + 1; return h; } /*************************************************************************** * Red-black tree helper functions. ***************************************************************************/ // make a left-leaning link lean to the right private Node rotateRight(Node h) { // assert (h != null) && isRed(h.left); Node x = h.left; h.left = x.right; x.right = h; x.color = x.right.color; x.right.color = RED; x.size = h.size; h.size = size(h.left) + size(h.right) + 1; return x; } // make a right-leaning link lean to the left private Node rotateLeft(Node h) { // assert (h != null) && isRed(h.right); Node x = h.right; h.right = x.left; x.left = h; x.color = x.left.color; x.left.color = RED; x.size = h.size; h.size = size(h.left) + size(h.right) + 1; return x; } // flip the colors of a node and its two children private void flipColors(Node h) { // h must have opposite color of its two children // assert (h != null) && (h.left != null) && (h.right != null); // assert (!isRed(h) && isRed(h.left) && isRed(h.right)) // || (isRed(h) && !isRed(h.left) && !isRed(h.right)); h.color = !h.color; h.left.color = !h.left.color; h.right.color = !h.right.color; } /** * Unit tests the {@code RedBlackBST} data type. * * @param args the command-line arguments */ public static void main(String[] args) { RedBlackBST st = new RedBlackBST(); }

The assignment is to design and implement a program that computes the percentage of red nodes in a given red-black tree (not counting external nodes). You will test your program by running at least 100 trials of the experiment of inserting n random keys into an initially empty tree, for n = 104, 105, and 106. Input: A random sequence of n distinct integers. Output: The percentage of red nodes after inserting all n integers into a red-black tree in the given order. You will accomplish this by using the textbook's RedBlackBST java class as a template. You will only need the code for the Node class, and the put0, isRed(), flipColors), rotateLeft(), and rotateRight0) methods (the delete) methods are not needed.) Your task is to add to this a method called percentRed) which returns the percentage of red nodes in the red-black tree as an integer between 0 and 100. How this is accomplished is up to you. You may alter the other methods as needed to accomplish this goal. Keep in mind, the more efficient your percentRed0 code is at doing this the better You will also need to add a main() method, which should do one of two things: 1. If one exists, read the contents of a text file provided on the command line, for example C:> java RedBlackBST test_file.txt for correctness testing by the marker. 2. Else, generate your own sequences to accomplish your experiments for the different values of n given above