CSCI 3333
Data Structures
Summer 2008
Homework #6

Due Date: July 23rd (Wednesday)

Goals

Familiarize students with binary trees, searching and binary search trees.

Specification

(1) The following definition is from Wikipedia:

An almost complete binary tree is a tree in which each node that has a right child also has a left child. Having a left child does not require a node to have a right child. Stated alternately, an almost complete binary tree is a tree where for a right child, there is always a left child, but for a left child there may not be a right child.

Consider a binary tree ADT that provides the following methods:

• hasLeft(p): whether p has a left child
• hasRight(p): whether p has a right child
• left(p): return the left child of p, possibly null.
• right(p): return the right child of p, possibly null.

Give the algorithm for isAlmostComplete(p) to check whether p is a nearly complete binary tree.

(2) Show the BST after the insertion of the following records to an initially empty tree: 12, 80, 15, 11, 27, 5, 4, 40, 33, 60, 95

(3) Show the evolution of the BST [[[] 10 [[] 15 18]] 20 [[22 25 []] 30 [[33 40 []] 50 []]]] after the deletion of the nodes 15, 20, 50 and 30 in sequence.

(4) (harder; 50% bonus) As discussed in the classroom, one technique to deal with unbalanced BST is to balance the BST when needed. Provide a linear algorithm balance(r) that takes a BST and returns a balanced BST. A balance BST is defined such that the sizes of the left subtree and right subtree differs by at most 1.

Submission

• Name your solution word file as [LastName_FirstName]_h6.doc. (e.g. Doe_Jenny_h6.doc).
• Upload all files through your WebCT account at
  http://courses.uhcl.edu:8900/.
• Email the solution to both the instructor and the teaching assistant.
• Turn in a hardcopy. All should be included in an envelope. The cover of the envelope should include course name, student name, homework number, instructor name and TA name.
• Failure to follow this guideline may result in reduced grade.