Skip to main content

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.

Popular posts from this blog

Constructing a Trie in F#

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 prefix trees (tries) as the next step. A trie is similar to a BST except the search is cumulative. A simple example would be building a spellchecker. The spell checker can use the structure to see if a word exists quickly and efficiently.

It works by creating a new node for each part of the word, using existing nodes if they're already in place. You can see in this diagram an example structure after an insertion of several words.

In the above diagram the words ANT, AND, BATS have been added into the data structure. You'll notice that the word BATS can also be the word BAT and that becomes a part of the structure, setting a value at each node to state if this is a place that a word terminates.

1 2 3 4// Node type for storing a trie. typeTrieNode=|Nodeofchar*TrieNodelist*bool|RootofTrieNodelist
I defined the type to have 2 options. The root node,…

A Docker Experiment

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 work or for various pet projects friends have been working on. I figured it was time to experiment myself and get to grips with what people have been talking about. It seemed like a good idea to find some introductory material that would give me an overview of its uses without delving too far into the details so I could see what it actually was, so I found a PluralSight course about Docker, specifically “Docker and Containers:The Big Picture”. This gave a nice overview of what Docker is, and more importantly what it was trying to achieve and how to use it. With a bit more of an understanding, I wanted to use it for something, preferably something familiar. I decided to try setting up ElasticSearch and Kibana containers, where Kibana would visualize the ElasticSearch data. I used bits of this article along the way as a guide, if you'd prefer a more…

Self-Producing an EP Pt.5: Mixing

After some discussion we opted to mix it ourselves for a few reasons.

It's our first EP, it's not going to be heard by a huge amount of people and while it's important that it sounds good, it's expensive to get done properly and we might be able to manage 'good enough' on our own with a lot of work.Mixing as an online service seems to be the main way to go for small/starting out bands and that seems too creatively detached. There are many stories floating around of people who've sent things off for mixing and the mixer has a much different idea of how it sounds.
Maybe it's not the best choice, but it seemed an acceptable risk that we would at least attempt to have it 'look' how we want and it be a bit wonky than potentially end up with something we're not happy with in a different way. The benefit would have been being able to just ship the stems off and make it someone else's problem instead of weeks of being unsure while swimming in the…