Write a method countNodes() of class RedBlackTree (from http://users.cis.fiu.edu

Question

Write a method countNodes() of class RedBlackTree
(from http://users.cis.fiu.edu/~weiss/dsaajava2/code/RedBlackTree.java)
that runs in O(n) time and counts the number of red and black nodes in the tree.

Explanation / Answer

See the code below where the method is added using a recursive implementation. The method still runs in O(n) time. // RedBlackTree class // // CONSTRUCTION: with no parameters // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // void remove( x ) --> Remove x (unimplemented) // boolean contains( x ) --> Return true if x is found // Comparable findMin( ) --> Return smallest item // Comparable findMax( ) --> Return largest item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // void printTree( ) --> Print all items // ******************ERRORS******************************** // Throws UnderflowException as appropriate /** * Implements a red-black tree. * Note that all "matching" is based on the compareTo method. * @author Mark Allen Weiss */ public class RedBlackTree

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---