Carrying on from the last post, I wanted to add deletion to the BST. My first attempt at this was in F#. I decided the best way to do it was to find the node that contained the value and if it only had one child node, replace it with that otherwise add the tree from the right to the tree from the left. The impact of this decision will be that the height of the tree is increased by an unknown amount and will affect performance, but binary search trees are unbalanced anyway and it's just for fun. All of the cases were simple up until the point where the right tree might need to be added to the left.
For that, I'd need a new function that would do the same as insertion but attach an existing node instead of just a value. To do that, we'd need to decompose the root node of the tree which will be appended so that it's value can be compared to each node of the tree it is being appended to.
So now we can add the case for a populated left and right node into the Remove function.
As previously stated, it will have a varied affect on the performance depending on the size of the trees beneath the value being removed but it was relatively straight forward. On to the C# implementation.
With a similar approach, the Append method is similarly trivial.
It looks very similar to the Insert method from the last post but instead of adding a new node, we're just using the one we already have. The next part is where it would get tricky. As you would expect from object oriented code, the Remove method, like the others would live inside the class. It would operate on itself and conditionally then on it's left and right nodes. This becomes a problem when trying to remove a value, as we have not made room for the idea of a 'parent' node, to go back up the chain.
The functional approach, in a way, goes from the bottom up where the approach taken in the C# implementation goes bottom down. This is fine in almost all cases except for the root node, as we can just operate on the children and hope that the value of 'this' has been processed by the node above. In the case that it was the parent node I opted for returning a node that represented the new base of the tree, containing the concatenation of the left and right nodes. For the cases of the children I applied the same logic that would be applied internally but one level down. A better way of doing this would be to do it outside of the structure itself, but it would be pretty similar.
There is some duplication here, we essentially do the same thing to the left and the right node and it could be simplified by abstracting that out into another method and doing it that way, or having the child nodes as an enumerable and iterating through. There's some new features in C# 6 that would make this much tidier, I'll re-visit it at some point.
The Milton Keynes GDG hosted their December meetup at The National Museum of Computing inside Bletchley Park. We had a detailed demons...
This post might get a bit more context next week, but essentially, in continuation of looking at data structures in F# and C# I picked prefi...
Containers are a topic that have been rising in occurrence for me, for the last year or so. From using them as part of the architecture at ...
While everything was being mixed into the same chain of plug-ins individually, we did at least know that mastering should be a clearly defin...