Initializing a Regex Tree

The Regular Expression Tree

Converting regular expressions (regexes) into trees was the first part of our last assignment. My thought process with starting to solve the problem. I realized that to finish it, I would have to have a method to deal with every part of the regex string. The regexes have 3 operators, '|', '.', and '*' which determine which type of node we would be using, and at the deepest level, the leaves were numbers, either '0', '1', or 'e' (meaning empty). The thing that quickly became apparent was that dealing with these separate operators and leaves was dependent on first dealing with the parentheses that separated the children of a node from their parents. This really stumped me at first. I tried initially to start from the deepest level and work upward from there, but I ran into a lot of problems and had trouble implementing this method. Mainly, I just couldn't figure out how to work backwards in this way. Eventually, it became clear that an easier method was available. The new way was to count up the parentheses while iterating over the string, and when a symbol was encountered after an equal amount of left and right parentheses, the left and right sides of it were then evaluated, excluding the outermost parentheses.

Binary Search Tree Delete

A binary search tree is an ordered tree, where the left child must only contain values smaller than the root and the right child must contain only values larger than the root. This makes searching for values in the tree much more efficient. Instead of potentially having to look at every single node to find some value, you simply compare it to the root. This means the number of comparisons you need to make is equivalent to the depth of the tree where that value is or would be if it were in the tree.

When deleting a value from a binary search tree, there are three cases to account for. The first, and simplest case is deleting a leaf (that is, a node with no children). When deleting a leaf, all you have to do is find that value in the tree, remove it and then replace it with an empty node. The second case is deleting an internal node with one child. This case requires finding and removing the value and then replacing it with its own child, where replacing it refers to giving its parent a new left or right. The final, and most complicated case, involves deleting an internal node with 2 children. In this case, you need to make sure you are replacing it with a value that is higher than everything on the left side and lower than everything on the right side. You are left with two options for what to do. You may either replace the node with the highest value on the left side, or with the lowest value on the right side. In class we learned to replace the node with the maximum node on the left side, because we had already defined a function which would return the maximum node in a tree. However, this is not the only way.

I can't say which method is better, because they appear to be about equivalent.