August 19, 2024
P63 - Construct a complete binary tree
A complete binary tree with height H is defined as follows: The levels 1,2,3,...,H-1 contain the maximum number of nodes (i.e 2**(i-1) at the level i, note that we start counting the levels from 1 at the root). In level H, which may contain less than the maximum possible number of nodes, all the nodes are "left-adjusted". This means that in a levelorder tree traversal all internal nodes come first, the leaves come second, and empty successors (the nil's which are not really nodes!) come last.
Particularly, complete binary trees are used as data structures (or addressing schemes) for heaps.
We can assign an address number to each node in a complete binary tree by enumerating the nodes in levelorder, starting at the root with number 1. In doing so, we realize that for every node X with address A the following property holds: The address of X's left and right successors are 2*A and 2*A+1, respectively, supposed the successors do exist. This fact can be used to elegantly construct a complete binary tree structure. Write a function complete-binary-tree with the following specification:
(complete-binary-tree N) returns a complete binary tree with N nodes
Test your function in an appropriate way.
lisp
;;; This is a hard problem. One way to think about it: you need an
;;; auxiliary functions for constructing cbt with arbitrary start
;;; label at root. Then you need to know the number of nodes in left
;;; and right subtrees.
;;; A table for that comes handy:
;;; N / left size / p
;;; 1 / 0 /
;;; 2 / 1 / 1
;;; 3 / 1 / 1
;;; 4 / 2 / 2
;;; 5 / 3 / 2
;;; 6 / 3 / 2
;;; 7 / 3 / 2
;;; 8 / 4 / 4
;;; 9 / 5 / 4
;;; 10 / 6 / 4
;;; 11 / 7 / 4
;;; 12 / 7 / 4
;;; 13 / 7 / 4
;;; 14 / 7 / 4
;;; 15 / 7 / 4
;;; 16 / 8 / 8
;;;
;;; Ok, except for the base N = 1, one can see that the left size
;;; depends essentially on the 2 higher-order bits (HOB) of N: if
;;; these two higer-order bits are "10", then left size keeps growing
;;; form a power of 2 by 1 unit; if the HOB are "11", then left size
;;; is constant, equal t the last value from the "10" series.
;;;
;;; These two HOB are just N div p, where p is the value in the third
;;; colimn; and what needs to be added to form the left size in the
;;; "10" case is p + lower order bits, which is p + N mod p. In the
;;; "11" case, this just gets to be p + (p-1).
;;;
;;; The starting label for subtrees is just 2k and 2k+1, if k is the
;;; starting label for the tree.
(defun complete-binary-tree (n)
(cbt-label n 1)
)
;;; cbt-label: complete binary tree with given label k at root;
;;; notice we also need an extra base case for n = 0.
(defun cbt-label (n k)
(cond
((= n 0) nil)
((= n 1) (list k nil nil))
(t (let* ((p (floor (highest-2-power n) 2))
(left (if (= 2 (floor n p))
(+ p (mod n p))
(+ p (1- p)))))
(list k
(cbt-label left (* 2 k))
(cbt-label (- n 1 left) (+ 1 (* 2 k)))
)))
)
)
;;; highest-2-poer: that is less that or equal to n
(defun highest-2-power (n)
(if (<= n 1)
1
(* 2 (highest-2-power (floor n 2)))
)
)