Homework 7
Binary Search Tree
So a Binary Search Tree was this week's assignment. It is a data structure that stretches from a primary node called the root. Every node will have a comparable value, and so the tree is a way of helping to store data in a sorted order, and also to find the data quickly. It does this by having every node have up to two children, one for being a lesser value child and one for being a greater or equal value child. This means that the more balanced each tree is (tree defined as all the descendants of a given node), the faster operations run on that tree. Since we did not have a balancing operation, the balance was completely dependant on the order of the input of the data.
These trees have very efficient running time when they are balanced, but poor when unbalanced. I had one running time that turned out to be about triple the other ones when running random high value numbers, and that is obviously a tree that had very extreme numbers at its high branches.
This seems even better than quicksort when operating on a balanced tree. With an implementation of an operation to balance the tree when it becomes too unbalanced, this could be very consistant in its use of large N. My running time graph turned out to look like it is close to O(N) running time.
