HW4B

Requirements:

For this assignment, you need to turn in:

• You may work in teams of two persons.
• All code which you submit must be your own.
• Please turn in, a printed listing of your code and test cases showing tree insertions and deletions as an electronic, zipped EMAIL to your instructor.

Binary Search Trees

1. [16 pts] Implement a BST based on our text’s algorithms for MINIMUN, MAXIMUM, SUCCESSOR, PREDECESSOR, INSERT, DELETE, and PRINT.

NOTES: • You do NOT need to implement SEARCH

• Your BST implementation should support an arbitrary object as its key (i.e., not just an integer), so that it will be able to support the RB-Tree implementation below.

• Your BST implementation should use the T.Nil-style nil nodes as described in the RB-Tree chapter, so nil nodes can support the parent, child, and color attributes that an RB-Tree needs.

AND Red-Black Trees

2. [24 pts] Implement RB-INSERT and RB-DELETE.