CMSC 341 -- Spring 2004 -- Project 3 Questions

Copy this file into your directory and edit it to add your answers
to the following questions about Project 3.

These questions count for 10% of your project grade.


1. (10 points) Comparing height-balanced and weight-balanced BST.
   1) Is a height-balanced BST always weight-balanced?
   2) Is a weight-balanced BST always height-balanced?
   Justify your answers.
-A weight balanced tree is one in which the weights of the left and right
subtrees of each node differ by no more then one.  A height balanced tree
is on in which the heights of the left and right subtrees of each node 
differ by no more then one.  
-A height balanced tree is always weight balanced because by the nature
of height balancing, each subtree's height may only differ from it's sibling
by one.  This means that at most there can be only one extra node in either
tree.  The path from the node to the leaf must be balanced as well.  This
means that at most there will be 1 extra node in either subtree.  This 
is the definition of weight balanced.
-A weight balanced tree is always height balanced.  For instance, in this
project we found the median and then inserted remaining nodes.  This 
means that each subtree had 1/2N +/- 1 nodes.  Basically, 1/2 the nodes in
the left and 1/2 the nodes in the right.  As we repeated this process each
node became balanced w/ 1/2 on in the left and 1/2 in the right.  By the time
the recursion is complete the tree is height balanced as well as weight balanced.

2. (10 points) What is the time performance (in big Oh) of your
   1) method for finding the median of a BST?
-To find the median in a worst case scenario my algorithm would require
O(n).  However, after balancing and considering long term this algorithm 
is actually log n.
   2) method for modifying a BST to a weight-balanced BST?
-O(n log^2 n) since the function operates on subtrees a) findMedian on each visit runs log N, b) iteratively insert each node log N, c) weightBalance visits each node.
   If you used algorithms different from the ones outlined 
   in the Project Description, please describe your algorithms
   in pseudo-code here.