8 Homework 5B
Due:
Thursday, 2/8 at 9PM
This assignment is SOLO, and entirely AUTOGRADED.
What to Download:
Please start with this file, filling in where appropriate, and submit your homework to the HW5B assignment on Gradescope. This page has additional information, and allows us to format things nicely.
8.1 Problem 1
Consider a binary tree, defined as follows:
| (define-struct leaf [value]) |
| (define-struct node [left right]) |
| (define-contract (Tree X) (OneOf (Leaf X) (Node (Tree X) (Tree X)))) |
Trees are often used for fast lookup of sorted data, as if it is sorted, at each node we can continue searching down only one half of the tree. But in order to be fast, they have to be balanced; a degenerate tree that only ever branches down one side will perform the same as a list.
A (height) balanced binary tree has a difference in height of the left and right subtrees of at most 1, where height is the longest path to a leaf. Importantly, this property (or invariant) must be mantained when inserting and removing elements from the tree. This may not be easy: if you have a tree:
| (define T1 (make-node (make-node (make-leaf 2) |
| (make-leaf 3)) |
| (make-leaf 4))) |
And you want to add 1, while mantaining the fact that the tree is sorted (or else, you won’t be able to use it to quickly look up data), you would want to insert it before 2 in the tree. The easiest thing would be to replace the leaf 2 with a node with 1 and 2:
| (define T2 (make-node (make-node (make-node (make-leaf 1) |
| (make-leaf 2)) |
| (make-leaf 3)) |
| (make-leaf 4))) |
This is still sorted, but it is no longer balanced, as now the left side of the top-level node has height 3, but the right side has height 1, which is a difference of 2. Instead, you might have to "rotate" the 3 to the other side to rebalance and get the following tree:
| (define T3 (make-node (make-node (make-leaf 1) |
| (make-leaf 2)) |
| (make-node (make-leaf 3) |
| (make-leaf 4)))) |
There are many different ways of doing this, with different names (AVL trees, Red Black trees, etc), and our goal is not to implement insertion, rebalancing, deletion, etc. What we do want to do is capture the invariant of being balanced.
Your task: define balanced-prop as a predicate. You should test your property on several example trees using check-expect.