Problems with the binary search tree in Clojure (immutable structure)

Question

I am having trouble writing code to remove a node from a tree.

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

so here is my thought, firstly, if BST is zero, then return nil and if BST has only one node root, then it also returns zero.

And then, if the key in the BST matches the given key, check the number of sheets that this node has. if the node has no children at all, then recreate bst from the first predecessor (root) to the last predecessor of this node and separate all other data that were not predecessors.

if node has one child, treat it as one that has a child, but just add it to the last predecessor.

for node has two children, I need to find a node that has no children in order to replace their position.

the tricky part comes up when writing code, I really don't know how to recreate and share tree data.

can anyone suggest some kind of hint or hint?

Answer 1

It seems to me that you pretty much have it, but you just need a little help with the details. So, let's say you have a node structure and the following functions for its operation:

• (left-subtree [node]) - returns the left subtree <<21> or nil if the node does not have a left subtree
• (right-subtree [node]) - returns the right subtree <<21> or nil if the node does not have the correct subtree.
• (value [node]) - returns the value associated with the node
• (leaf? [node]) - returns true if node is a leaf, false otherwise.

Now write a without-root function that takes a (sub) tree and returns a new tree containing everything in the source 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 the node has two children. Therefore, I decided to separate it into a separate function to facilitate discussion.

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

Now we could write a new function without-rightmost-node that will take a tree and return a new tree without its rightmost node. However, we also need the value stored in this node. Therefore, we need to either call some find-rightmost-node function on our own to get its value (which would be inefficient), or return the value together with a new tree (which would conflict with the purpose of the function).

Instead, write a function that takes a tree and returns a new tree equivalent to the original tree, except that its root is the rightmost node of the source tree. For fun, call this function percolate-rightmost-node , because, as we will see, the rightmost node will recursively “pop up” at the top of the tree (below).

 (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 that the “then” side of the if-let expression is not very clear, so let me figure it out a bit. Basically, we take the subtree percolated , get its left subtree (which is the only descendant of percolated ) and substitute it for the right subtree node . Then we take this result and substitute it for the left subtree percolated (effectively restoring the tree), creating the final result.

The output of percolate-rightmost-node will have only the left subtree - it will never have the correct subtree. Therefore, after the result ended with “bubbling”, we just need to give it the correct 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 so. Of course, you will need to adapt this to your code (at least inline handle-difficult-case or give it a suitable name). But I hope you get started.

Caveat emptor: I did not try to verify the code provided in this answer. Corrections are welcome!

Answer 2

This will be a long answer, so please allow me to apologize in advance for pointing to the book and not responding directly. I highly recommend looking at Purely functional data structures , which (legally) is available as a PDF from the author. Although this is a good book to print / ebook anyway.

and a super- sorted-map answer is to use Clojure built into sorted-map if you want it in practice (although, in fact, writing your own will, of course, will get nerd-street-cred), since sorted maps use a binary red-black tree under the hood