1 2 3 4 5 6 7 8 | // Remove a given value fron the tree. let rec Remove value = function | Leaf -> Leaf | Node(v, left, right) when value <> v -> Node(v, Remove value left, Remove value right) | Node(v, left, Leaf) -> left | Node(v, Leaf, right) -> right | Node(v, Leaf, Leaf) -> Leaf | Node(_, _, _) as node -> node |
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.
1 2 3 4 5 6 | // Add the provided branch to the most appropriate part of the tree. let rec Append value = function | Leaf -> value | Node(v, left, right) -> match value with | Node(a, _, _) -> if a < v then Node(v, Append value left, right) else Node(v, left, Append value right) | Leaf -> Node(v, left, right) |
So now we can add the case for a populated left and right node into the Remove function.
1 2 3 4 5 6 7 8 9 | // Remove a given value fron the tree. let rec Remove value = function | Leaf -> Leaf | Node(v, left, right) when value <> v -> Node(v, Remove value left, Remove value right) | Node(v, left, right) -> Append right left | Node(v, left, Leaf) -> left | Node(v, Leaf, right) -> right | Node(v, Leaf, Leaf) -> Leaf | Node(_, _, _) as node -> node |
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | /// <summary> /// Adds a Node to the most appropriate place in the tree. /// </summary> /// <param name="node">The <see cref="BSTNode"/> to add.</param> private void Append(BSTNode<t> node) { if (node.Value.CompareTo(Value) == 0) { if (Left != null) { Left.Append(node); return; } Left = node; return; } else { if (Right != null) { Right.Append(node); return; } Right = node; return; } } } |
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | /// <summary> /// Removes a value from a tree. /// </summary> /// <param name="value">The value to remove.</param> /// <returns>null if the value is stored in a child, otherwise if the value is in the root, it returns the new tree.</returns> public BSTNode<t> Remove(int value) { // If the root node is the value, remove it, sort the children and return the new root. if (value.CompareTo(Value) == 0) { // If the left and right nodes have values, make them into 1 tree and return that as the root. if (Left != null && Right != null) { Left.Append(Right); return Left; } else if (Left != null) { return Left; } else { return Right; } } // If the left node has a value. if (Left != null) { // And the left value is equal to the one to be removed. if (Left.Value.CompareTo(value) == 0) { // And it has both child nodes, add the right tree to the left and use the left nodes left node as the left node. if (Left.Right != null && Left.Left != null) { Left.Left.Append(Left.Right); Left = Left.Left; } else if (Left.Right != null) { Left = Left.Right; } else if (Left.Left != null) { Left = Left.Left; } else { Left = null; } } else if (value.CompareTo(Value) < 0) { Left.Remove(value); return null; } } if (Right != null) { if (Right.Value.CompareTo(value) == 0) { if (Right.Right != null && Right.Left != null) { Right.Left.Append(Right.Right); Right = Right.Left; } else if (Right.Right != null) { Right = Right.Right; } else if (Right.Left != null) { Right = Right.Left; } else { Right = null; } } else if (value.CompareTo(Value) > 0) { Right.Remove(value); return null; } } return null; } |
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.