Description

For this assignment you’ll be implementing several tree-based algorithms that we saw in class. Specifically you’re editing only “tree.c”. You shouldn’t need to change any other files. Here are your algorithms to implement:

Huffman Tree – printHuffmanEncoding

Given the root of a Huffman tree and a character, print the sequence of bits used to encode that character based on the tree.

Reminder: Going left in the Huffman tree appends a ‘0’ and going right appends a ‘1’.

AVL Tree – rebalanceTree

Here is a brief outline of algorithm for rebalancing the tree using AVL trees:

Reminder: the balance of x is the height of the left subtree of x – height of the right subtree of x.

• Let x be the node we are starting our rebalance from
• While x is not NULL
  • if the balance of x is −2 or 2
    • Set z equal to the child of x with the greater height
    • if the balance of x and the balance of z have different signs
      • if the sign of the balance of z is + right rotate on z
      • if the sign of the balance of z is − left rotate on z
    • if the balance of x is 2 right rotate on x
    • if the balance of x is −2 left rotate on x
    • Update height of the rotated nodes. (height of a node = height of its taller subtree plus 1).
    • if x was the root before the rotate, update the root to the parent of x
  • Set x equal to the parent of x

To test if your tree is balanced you can uncomment the calls to checkAVLTree in driver.c. This function will inform you if there are any balances in your tree outside of 1, 0, and -1. Likewise there is function printTree which will print the contents and structure of your tree (elements higher up in your tree are printed with more tabs in front of them).

For my implementation of rebalance I created the following helper functions. You don’t have to do this but it may help break this large problem down into several smaller, simpler, problems:

TNode* getTallerSubTree(TNode* x); bool isSameSignBalance(TNode* x, TNode* z);

The function getTallerSubTree finds and returns the subtree of x with the larger height. The function isSameSignBalance returns true if the two given nodes both have balance ≥ 0 or ≤ 0.

Segment Tree – insertSegment and lineStabQuery

Each TNode contains a low and high value. These specify the range of values that this represents on the number line. Each TNode also contains a count, cnt, that represents the number of line segments associated with this node. insertSegment This inserts a new line segment into the tree.

• Go down the the segment tree starting at the root
• If the root is a leaf, return.
• Else if the segment is completely to the left or right of the current node’s range, return.
• Else if the segment is completely covers the range represented by this node: increase cnt by 1 and return.
• Else: Recursively call insertSegment on the left and right children of this node.

lineStabQuery This checks how many line segments cross a given point, queryPoint.

• Go down the the segment tree starting at the root
• If the root is a leaf: return 0.
• Else if the queryPoint is completely to the left or right of the current node’s range: return 0.
• Else: Recursively call lineStabQuery on the left and right children of this node. Return the sum of their return values and current node’s cnt.

Deliverables:

Your solution should be submitted as “tree.c”. Upload this file to Blackboard under Assignment 4. Do not zip your file.

To receive full credit, your code must compile and execute. You should use valgrind to ensure that you do not have any memory leaks.