Monday, 20 April 2015

Trees: I still can't be-leaf them

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.


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.