"ANSI Common Lisp" and bst-remove

I like Lisp. Compared to a lot of other languages, it's pretty damn nice. I don't know it very well, so I'm learning mostly out of textbooks, mostly in my free time. One such textbook is Paul Graham's 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. :)