Today in class we began to cover binary search trees, binary trees in which the left child of each node (if present) has a value less than that of the node, and the right (if present) one greater than it. We covered some of the operations that one might want to perform on such trees, such as the insertion or deletion of nodes, as well as the necessary helper functions that, for example, return the largest value in a given (sub)tree. We have not yet gotten to what seems to be the primary motivation for such trees' existence, efficiently searching through them for a given value, but it seems to be a simple recursive function that can be easily implemented.
Although these trees do make some things slightly easier, I am not yet convinced that they really help. They appear to me to not be conventional forms of input, rather they are data types created and used to make the programmer's job easier. But if the task is (for example) searching a list (or other iterable) for an element, it seems counter-intuitive to first convert the list into a binary search tree, then search that tree, then locate the found node in the list, rather than simply using a recursive algorithm on successively smaller splices of the list. However, I suspect that there are other benefits to using binary search trees that remain to be seen, and that they are indeed the natural and best representation of some data. Time (and future lectures) will tell just how effective these trees can be. For the time being, they remain an interesting exercise in linked data types and recursion.
No comments:
Post a Comment