August 19, 2024
P60 - Construct height-balanced binary trees with a given number of nodes
Consider a height-balanced binary tree of height H. What is the maximum number of nodes it can contain?Clearly, MAXN = 2**H - 1. However, what is the minimum number MINN? This question is more difficult. Try to find a recursive statement and turn it into a function minnodes defined as follows:
(min-nodes H) returns the minimum number of nodes in a height-balanced binary tree of height H.
On the other hand, we might ask: what is the maximum height H a height-balanced binary tree with N nodes can have?
(max-height N) returns the maximum height of a height-balanced binary tree with N nodes
Now, we can attack the main problem: construct all the height-balanced binary trees with a given number of nodes.
(hbal-tree-nodes N) returns all height-balanced binary trees with N nodes.
Find out how many height-balanced trees exist for N = 15.
lisp
(defun min-nodes (h)
(cond
((= h -1) 0)
((= h 0) 1)
(t (+ 1 (min-nodes (- h 1)) (min-nodes (- h 2))))
)
)
(defun max-height (n)
(max-height-aux -1 0 1 n)
)
(defun max-height-aux (h fh fh1 n)
(if (< n fh1)
h
(max-height-aux (1+ h) fh1 (+ 1 fh fh1) n)
)
)
;;; hbal-tree-nodes(n): list version
;;; returns a list with all completely balanced binary trees with a
;;; given number of nodes.
;;;
;;; Brute-force approach, using an auxiliary procedure which computes
;;; a list of all such trees with a given height.
;;;
;;; Note: it is possible to improve the performance using
;;; dynamic programming. See function hbal-tree-nodes-dp
(load "p59.lisp")
(defun hbal-tree-nodes (n)
(hbal-tree-nodes-dp n)
)
(defun hbal-tree-nodes-bf (n)
(let ((result nil))
(dotimes (h (1+ (max-height n)) result)
(setf result (append (hbal-tree-aux n h) result))
)
)
)
(defun hbal-tree-aux (n h)
(if (= n 0)
(if (= h -1) '(()) '())
(let ((a nil))
(dotimes (i n a)
(setf a (append (cart-process (hbal-tree-aux i (- h 2))
(hbal-tree-aux (- n i 1) (- h 1))
)
(cart-process (hbal-tree-aux i (- h 1))
(hbal-tree-aux (- n i 1) (- h 1))
)
(cart-process (hbal-tree-aux i (- h 1))
(hbal-tree-aux (- n i 1) (- h 2))
)
a))
)
)
)
)
;;; Faster, dynamic programming implementation
(defun hbal-tree-nodes-dp (n)
(let ((a (hbal-table n (max-height n)))
(result nil))
(dotimes (h (1+ (max-height n)) result)
(setf result (append (list-of-hbal-trees n h a) result))
)
)
)
(defun hbal-table (n h)
(let ((a (make-array (list (1+ n) (1+ h)) :initial-element nil)))
(dotimes (ni (1+ n) a)
(dotimes (hi (1+ h))
(let ((b nil))
(dotimes (i ni b)
(setf b (append
(cart-process (list-of-hbal-trees i (- hi 2) a)
(list-of-hbal-trees (- ni i 1) (- hi 1) a)
)
(cart-process (list-of-hbal-trees i (- hi 1) a)
(list-of-hbal-trees (- ni i 1) (- hi 1) a)
)
(cart-process (list-of-hbal-trees i (- hi 1) a)
(list-of-hbal-trees (- ni i 1) (- hi 2) a)
)
b))
)
(setf (aref a ni hi) b)
)
)
)
)
)
(defun list-of-hbal-trees (n h a)
(cond
((= h -2) nil)
((= h -1) (if (= n 0) '(()) nil))
(t (aref a n h))
)
)
;;; hbal-tree-nodes: print version
;;; call list version and then print each element
(defun hbal-tree-nodes-print (n)
(dolist (tree (hbal-tree n))
(print tree)
)
)