*ANSI Common Lisp*.

It's a solid book, it's engaging, but what I really like about it is that it leaves just the right amount of room for free thought. Case in point: I reached section 4.7, which is an example implementation of a binary search tree. Everything was going smoothly until I hit

`bst-remove`. I read through the section, and I understood Paul's approach, which was good: I was making progress.

At this point, I'd just been through Lisp "structs" country, and instead of the lame

`:print-function`for the

`node`struct that just printed out the object/number at that node, I decided to roll my own.

So instead of this:

(defstruct (node (:print-function

(lambda (n s d)

(format s "#<~A>" (node-elt n)))))

elt (1 nil) (r nil))

I wrote this:

(defstruct (node (:print-function print-node))

elt (l nil) (r nil))

(defun print-node (n stream depth)

(when n

(print-node (node-r n) stream (1+ depth))

(do ((i 1 (1+ i)))

((>= i depth))

(format stream " "))

(format stream "~a~%" (node-elt n))

(print-node (node-l n) stream (1+ depth))))

Paul mentions in the book that the

`depth`parameter can be safely ignored, but I figured that since it wasn't being used for anything else, I may as well use it myself. Anyway all my version does is print the full sub-tree under the given node with indentation to give it that pseudo-graphical charm. Once I reached

`bst-remove`, this was how I was printing all of my intermediate results with mucking about with my experimental binary search tree.

I stumbled across the error by deleting a node from the far left of the tree, leaving the node above with only a right child, which is fine. It doesn't always happen because the book's algorithm uses

`(random 2)`to try to maintain tree balance. Say if there's a parent node 2 with two children 1 and 3 as left and right sub-trees respectively, then deletion of 2 would pull 1 up, 50% of the time.

Now suppose 2 was the left sub-tree of yet a bigger binary search tree, and the node immediately above 2 is 5. We delete 2 as above, and now let's delete 5, and say 2's successor (1) is chosen to replace 5. There's now a hole where 1 is supposed to be, and the algorithm states that one of the immediate children must take its place. 1 only had one child.

Here's where things go wrong. 1's only child was 3. Since 1 was less than 5, it was a left child to it. Dragging up 1 doesn't cause any problems. However, dragging up 3 to take 1's old place now makes 3 a

*left*child, not a right one like it should be. The tree is broken. It wouldn't have been entirely obvious if I wasn't looking at the tree structure at each point, but I'm happy that I did.

That was last night. Today, a bit of poking around in Paul Graham's website shows this error has been found and corrected in the book's errata. It's the one on page 71. Regardless, I'm happy I spotted that, because it means that I'm learning and paying attention.

My only regret in all this is that I didn't have the tenacity to write a replacement

`bst-remove`before finding the corrected code (linked in the book's errata page.) Thank you intertubes for making me lazy.

*ed: I should have included some*

`M-x artist-mode`diagrams for this. :)
## No comments:

Post a Comment