Problems about Binary Search Tree in Clojure (immutable structure)

Question

I have run into problems in writing the code for delete a node from the tree.

given a BST and a key value, find the key in the tree and delete it.

so here is my thought, first, if BST is nil then return nil and if the BST have only one node the root, then return nil as well.

And then if a key in the BST matched the given key, check for the number of leaf that this node have. if the node has no children at all, then recreate a bst from the first predecessor (the root) to the last predecessor of this node, and share all the rest data that was not the predecessor.

if the node have one child, treat as the one without the child, but just add a child to the last predecessor.

for the node has two children, i have to find some node that does not have any children to replace their position.

the hard part comes up when writing the code, i don't really now how to recreate and share the data of the tree.

so can someone offer some hint or clue?

Answer 1

It looks to me like you pretty much have it, but just need a little help with the details. So let's say you have some node structure and following functions to operate on it:

• (left-subtree [node]) - returns the left subtree of node, or nil if node has no left subtree
• (right-subtree [node]) - returns the right subtree of node, or nil if node has no right subtree.
• (value [node]) - returns the value associated with node
• (leaf? [node]) - returns true if node is a leaf, otherwise false.

Now let's write a without-root function that takes a (sub)tree and returns a new tree that contains everything in the original tree except its root node:

(defn without-root [node]
  (cond (leaf? node) nil ; resulting tree is the empty tree, return nil
        (and (left-subtree node) ; two children, "difficult" case
             (right-subtree node)) (handle-difficult-case node)
        ;; cases for single child
        (left-subtree node) (left-subtree node)
        (right-subtree node) (right-subtree node)))

As you state in the question, the "difficult" case is when node has two children. So I've decided to split it out into a separate function to facilitate discussion.

So let's talk about handle-difficult-case. Since there are two children, we somehow need to combine them into a single tree. If you read what Wikipedia has to say about BST Deletion, you basically want to take either the in-order predecessor or successor (i.e., the rightmost node of the left subtree, or the leftmost node of the right subtree) and make it the new root. It doesn't matter which one you choose -- either one will do. For the sake of this discussion, we'll choose the righmost node of the left subtree.

Now we could write a new function, without-rightmost-node, that would accept a tree and return a new tree without its rightmost node. However, we also need the value stored in that node. So we would either need to independently call some find-rightmost-node function to get its value (which would be inefficient) or return the value along with the new tree (which would conflate the purpose of the function).

Instead, let's write a function that accepts a tree and returns a new tree that is equivalent to the original tree, except its root is the rightmost node of the original tree. For fun, lets call this function percolate-rightmost-node because, as we'll see, the rightmost node will recursively "bubble up" to the top of the (sub)tree.

(defn percolate-rightmost-node [node]
  (if-let [right-side (right-subtree node)]
    ;; then (recurse down the right side)
    (let [percolated (percolate-rightmost-node right-side)]
      ;; Construct a new tree from the result.
      (with-left-subtree percolated
                         (with-right-subtree node (left-subtree percolated))))
    ;; else (we are at the rightmost node -- return it!)
    node))

I feel like the "then" side of the if-let expression is not very clear, so let me elaborate a little. Basically, we take the percolated subtree, get it's left subtree (which is the only child of percolated) and substitute it for the right subtree of node. We then take that result and substitute it for the left subtree of percolated (effectively re-rooting the tree), producing the final result.

The output of percolate-rightmost-node will only have a left subtree -- it will never have a right subtree. So after the result has finished "bubbling up", we just need to give it a right subtree. Therefore, we can implement handle-difficult-case as:

(defn handle-difficult-case [node]
  (let [percolated (-> node           ; Find the rightmost node of the left
                       (left-subtree) ; subtree and "percolate" it to the top
                       (percolate-rightmost-node))]
    ;; Now take the percolated tree.  Its right subtree is empty,
    ;; so substitute in the right subtree of node.
    (with-right-subtree percolated
                        (right-subtree node))))

And that should be it. Of course, you will need to adapt this to your code (at minimum, either inline handle-difficult-case or give it a suitable name). But hopefully that gets you started.

Caveat emptor: I have made no attempt to test the code given in this answer. Corrections are welcome!

Answer 2

This would be a long answer, so please let me apologize in advance for pointing you towards a book and not directly answering. I highly recommend looking at Purely Functional Data Structures which is (legally) available as a PDF from the author. Though it's a good book to have in print/ebook anyway.

and the super short answer is use Clojure's built in sorted-map if you want this in practice (though writing your own will of course get nerd-street-cred) because sorted maps use a binary red-black-tree under the hood