Question

Count Red Nodes. Write a program that computes the percentage of red nodes in a given red-black BST. Test your program by running at least 100 trials of the experiment of inserting N random keys into an initially empty tree, for N = 10^4, 10^5, 10^6, and formulate an hypothesis.

*It is experiment from textbook Algorithms, 3.3.42

Answer 1

It wouldn't be too rude if one specifies the programming language and the edition next time.

> It is is experiment from

The most primitive way to do that is perhaps to download the official sample Java code, review the isBalanced() method, and slightly modify the unit loop.

private int count() {
    return count(root);
}

private int count(Node x) {
    if (x == null) return 0;
    return (!isRed(x) ? 1 : 0) + count(x.left) + count(x.right);
}

RedBlackBST<Integer, Integer> st = new RedBlackBST<Integer, Integer>();
for (int i = 1; i <= 1000000; i++) {
    Integer key = StdRandom.uniform(Integer.MAX_VALUE);
    while (st.contains(key)) {
        key = StdRandom.uniform(Integer.MAX_VALUE);
    }
    st.put(key, i);
    if (i == 10000 || i == 100000 || i == 1000000) {
        StdOut.printf("%8d %8.2f\n", i, 100.0 * st.count() / i);
    }
}
StdOut.println();