Lab 5
All problems are to be done using DrRacket. You should be using typed racket, meaning that the first line of your definitions window should be #lang typed/racket.Lab 5 is optional. These questions can be somewhat time consuming and I want people to take time to study and review the things that are most difficult for them. Maybe that is 2-3-4 trees or maybe it's something else. Solutions to this lab will be posted with the lecture notes Wednesday night. Please spend some time and make sure you understand 2-3-4 trees: they will appear on the final exam.
You will need to require the following library to work with images in Typed Racket:
(require typed/test-engine/racket-tests) (require "../include/uchicago151.rkt")
2-3-4 Trees
When talking about binary search trees, we found that several algorithms have to walk down exactly one branch of the tree (insert, find, remove). These algorithms are linear in the height of the tree, but for an unbalanced tree that may be just as slow as using a list.
A 2-3-4 tree is a self-balancing tree. That means that we define insert and remove operations so that the tree always remains balanced. I'm not going to describe these operations here, but if your interested search the internet for 2-3-4 trees and you'll find a lot of good tutorials.
The main idea of a 2-3-4 tree is that, unlike binary trees, in which every node has exactly two children, in a 2-3-4 tree nodes may have 2, 3, or 4 children. A 2-node (a node with two children) has one number in it, just like a BST, and it is ordered in the same way: the numbers in the left subtree are all less than the value in the root and the numbers in the right subtree are all greater than the value in the root.
A 3-node has two numbers in it (let's call them a and b) and three children (lets call them left, middle and right). All the numbers in the left subtree are less than a. All the numbers in the middle subtree are greater than a and less than b. All the numbers in the right subtree are greater than a. So overall, left < a < middle < b < right.
A 4-node has 4 children and 3 numbers in it and a similar order. If the children are l, m, n, o and the numbers are a, b, c, then l < a < m < b < n < c < o.
Use the following definition for 2-3-4 trees:
;; A 2-3-4 tree is either (Empty) or ;; - (2-node (a l m)) ;; - (3-node (a b l m n)) ;; - (4-node (a b c l m n o)) ;; Where a, b, c are numbers and l, m, n, o are 2-3-4 trees ;; A 2-3-4 tree must always be perfectly balanced ;; A 2-3-4 tree must always satisfy the condition that l < a < m < b < n < o (define-struct Empty ()) (define-struct 2-node ([e0 : Real] [t0 : Tree] [t1 : Tree])) (define-struct 3-node ([e0 : Real] [e1 : Real] [t0 : Tree] [t1 : Tree] [t2 : Tree])) (define-struct 4-node ([e0 : Real] [e1 : Real] [e2 : Real] [t0 : Tree] [t1 : Tree] [t2 : Tree] [t3 : Tree])) (define-type Tree (U Empty 2-node 3-node 4-node))
You may use the following insert function to make tests, if you choose (not required):
(: 2-3-4-insert (Real Tree -> Tree))
(define (2-3-4-insert i t)
(match t
[(Empty) (2-node i (Empty) (Empty))]
[(2-node a (Empty) (Empty))
(cond
[(< i a) (3-node i a (Empty) (Empty) (Empty))]
[(= i a) t]
[else (3-node a i (Empty) (Empty) (Empty))])]
[(2-node a l m)
(cond
[(< i a)
(match l
[(4-node sa sb sc sl sm sn so)
(cond
[(< i sb)
(3-node sb a (2-3-4-insert i (2-node sa sl sm)) (2-node sc sn so) m)]
[(= i sb) t]
[else
(3-node sb a (2-node sa sl sm) (2-3-4-insert i (2-node sc sn so)) m)])]
[_ (2-node a (2-3-4-insert i l) m)])]
[(= i a) t]
[else
(match m
[(4-node sa sb sc sl sm sn so)
(cond
[(< i sb)
(3-node a sb l (2-3-4-insert i (2-node sa sl sm)) (2-node sc sn so))]
[(= i sb) t]
[else
(3-node a sb l (2-node sa sl sm) (2-3-4-insert i (2-node sc sn so)))])]
[_ (2-node a l (2-3-4-insert i m))])])]
[(3-node a b (Empty) (Empty) (Empty))
(cond
[(< i a) (4-node i a b (Empty) (Empty) (Empty) (Empty))]
[(= i a) t]
[(< i b) (4-node a i b (Empty) (Empty) (Empty) (Empty))]
[(= i b) t]
[else (4-node a b i (Empty) (Empty) (Empty) (Empty))])]
[(3-node a b l m n)
(cond
[(< i a)
(match l
[(4-node sa sb sc sl sm sn so)
(cond
[(< i sb)
(4-node sb a b (2-3-4-insert i (2-node sa sl sm)) (2-node sc sn so) m n)]
[(= i sb) t]
[else
(4-node sb a b (2-node sa sl sm) (2-3-4-insert i (2-node sc sn so)) m n)])]
[_ (3-node a b (2-3-4-insert i l) m n)])]
[(= i a) t]
[(< i b)
(match m
[(4-node sa sb sc sl sm sn so)
(cond
[(< i sb)
(4-node a sb b l (2-3-4-insert i (2-node sa sl sm)) (2-node sc sn so) n)]
[(= i sb) t]
[else
(4-node a sb b l (2-node sa sl sm) (2-3-4-insert i (2-node sc sn so)) n)])]
[_ (3-node a b l (2-3-4-insert i m) n)])]
[(= i b) t]
[else
(match n
[(4-node sa sb sc sl sm sn so)
(cond
[(< i sb)
(4-node a b sb l m (2-3-4-insert i (2-node sa sl sm)) (2-node sc sn so))]
[(= i sb) t]
[else
(4-node a b sb l m (2-node sa sl sm) (2-3-4-insert i (2-node sc sn so)))])]
[_ (3-node a b l m (2-3-4-insert i n))])])]
[(4-node a b c l m n o)
(cond
[(< i b) (2-node b (2-3-4-insert i (2-node a l m)) (2-node c n o))]
[(= i b) t]
[else (2-node b (2-node a l m) (2-3-4-insert i (2-node c n o)))])]))
Problem 1
Implement (: size (Tree -> Nonnegative-Integer)) that takes a 2-3-4 tree as input and returns the number of data elements in the tree (in this case, our tree stores numbers, so each number in the tree is a data element). Note that the number of data elements may not equal the number of nodes.
Problem 2
Implement (: search (Real Tree -> Boolean)) which returns true if i is in the tree, false otherwise.
Problem 3
Implement (: min (Tree -> Real)) which returns the smallest number in the tree.
Problem 4
Implement (: height (Tree -> Nonnegative-Integer)) that takes a 2-3-4 tree as input and returns the height of the tree.
Problem 5
Implement (: valid-tree? (Tree -> Boolean)) which takes a 2-3-4 tree as input and returns true if the tree is valid and false otherwise.
Problem 6
Implement (: inorder (Tree -> (Listof Real))) which outputs the inorder traversal of the 2-3-4-tree.