I'm a complete newbie to lisp, and I'm going through a tutorial and getting confused. I'm wondering if someone can help me out.

The tutorial is here: http://www.cs.sfu.ca/CC/310/pwfong/Lisp ... rial3.html, and the part I'm having trouble with is this:

- Code: Select all
`(defun BST-remove (B E)`

"Remove E from BST B."

(if (BST-empty-p B)

B

(if (bin-tree-leaf-p B)

(BST-leaf-remove B E)

(BST-node-remove B E))))

(defun BST-leaf-remove (L E)

"Remove E from BST leaf L."

(if (= E (bin-tree-leaf-element L))

(make-empty-BST)

L))

(defun BST-node-remove (N E)

"Remove E from BST node N."

(let

((elmt (bin-tree-node-element N))

(left (bin-tree-node-left N))

(right (bin-tree-node-right N)))

(if (<= E elmt)

(if (bin-tree-leaf-p left)

(if (= E (bin-tree-leaf-element left))

right

N)

(make-bin-tree-node elmt (BST-node-remove left E) right))

(if (bin-tree-leaf-p right)

(if (= E (bin-tree-leaf-element right))

left

N)

(make-bin-tree-node elmt left (BST-node-remove right E))))))

This is an algorithm for removing elements from a binary search tree.

What I don't understand is this part:

- Code: Select all
`(if (<= E elmt)`

(if (bin-tree-leaf-p left)

(if (= E (bin-tree-leaf-element left))

right

N)

It's saying that if E is less than or equal to elmt (a node in the tree) and the branch to the left of elmt is a leaf, then return the right brach if E is equal to that leaf, and return the node (with its branches?) otherwise.

But why would it return the node in that case? If it just returns the node, then it hasn't removed anything. It failed to remove E from the tree!

Am I right in thinking that E must be either the left leaf or the node above it (or both)? In any case, I fail to see how E is removed.

Can anyone explain this?