please help me understand this lisp function

[gib65]

Hello,

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?

[Konfusius]

If it just returns the node, then it hasn't removed anything. It failed to remove E from the tree!

If you remove E from (:elm k :left E :right subtree) then the result is subtree.

[adam33147]

To help understand what #'BST-node-remove is doing, try to see the following patterns.

*Since the tree is sorted, the program determines to search either the (<= remove-this node-referece) sub-tree, or the (> remove-this node-reference) sub-tree.

*If when checking the left tree, the right-tree is returned, it ment that the left-tree was a leaf which contained the element to be removed....and vise versa.........

*If N is returned, then the element was not found in the tree.

*#'make-bin-tree-node plays a very important role in reconstructing the tree with the one tree known not to contain the element, and the other tree undetermined.

also

*A tree is either a node or a leaf.

*If a tree is not a leaf, then it must be a node.

Further, the E is the element to be removed.

Hope that helps.

[gib65]

If you remove E from (:elm k :left E :right subtree) then the result is subtree.

But what if the situation is like this: (:elmt E :left k :right subtree).

*If N is returned, then the element was not found in the tree.

It's this part that confuses me. It seems like N could be returned if elmt = E.

[adam33147]

I seems the function BST-node-remove returns the right node in that case.

E is removed because it is excluded from the reconstructed tree.

[saulgoode]

*If N is returned, then the element was not found in the tree.

It's this part that confuses me. It seems like N could be returned if elmt = E.

If the left branch of N is a leaf then, by the convention adopted, that leaf's element is equal to N's element (and so if the element of that leaf is equal to E, it is only necessary to return the right branch).

If the left branch of N is a node (and N's element is equal to E) then N is not returned -- you descend deeper into that node searching for the leaf containing E. This descent recurses until that leaf is found (the one whose element equals E). That last (innermost) level of recursion returns the node resulting from removal of that leaf (i.e., the opposite branch); which gets passed back up the chain, getting combined back with the appropriate opposite branches until N is eventually reached, at which point the resulting node gets combined with N's right branch and returned to the caller. If the leaf containing E is never found, then the subtrees are each passed intact up the chain of recursion until N is eventually reached; and this intact subtree is combined with the right branch of N and returned to the caller. In either case, the node N is effectively removed.

Note that (I believe) it is impossible for a node with element E to exist unless also a leaf exists with that same element. Thus the latter scenario of the preceding paragraph can safely be excluded from consideration. (This assuming elements have all been inserted using the provided procedures and that the BST has not otherwise become corrupted.)

[gib65]

Note that (I believe) it is impossible for a node with element E to exist unless also a leaf exists with that same element. Thus the latter scenario of the preceding paragraph can safely be excluded from consideration. (This assuming elements have all been inserted using the provided procedures and that the BST has not otherwise become corrupted.)

That would make sense. So it's impossible to have the following situation: node: 2, left: 1, right: 3.

I think I was confused by the earlier example of inserting 2.5 into the tree. If you look at that example, you do see a case where the node can be a number greater than its left node but less than its right, but then reading what you said, I realized this situation is only possible when the left node is not a leaf.

Is that the gist of what you were trying to say?

[adam33147]

If you used only the defined structure interface functions, that would be correct.
In the insert function group, there is a function called BST-leaf-insert. If you use the convention (make-bin-tree-node reference-element left-tree right-tree),
Notice that the reference element in the node created is always equal to the element in the left leaf.

Code: Select all

(make-bin-tree-node E
               (make-bin-tree-leaf E)
               (make-bin-tree-leaf elmt))
   (make-bin-tree-node elmt
             (make-bin-tree-leaf elmt)
             (make-bin-tree-leaf E))))))


That is where the top part of the triangle comes from

Code: Select all

                reference-element
node =            /         \
           left-tree       right-tree



So once again, according to the code above, the reference-element has to be equal to the element in the left leaf.

Remember that any tree can be a node or a leaf.
So you can get a refence element pointing to a reference element, on and on, till you actually reach a leaf. But at the ends of these branches must be leaves.