Binary Search Trees
In the field of Computer Science we have a number of Data Structures that are all measured through both Space and Time Complexity which measures the efficiency of the methods. Binary Trees is a data structure that allows for efficient searches in datasets. With its use varying based on data sets, the Space and Time Efficiency of Binary Search Trees is O(log(n)) relative to the size of the full data set.
If you’ve never seen a BST, seeing how one looks can hint to why it has its name. Starting at the top we have a root node and a left and right subtree. In the example above, 25 is the root node. The left subtrees start is 20 and a parent node to it’s two child nodes, same as the right subtrees start is 36 with 30 and 40 being its own child nodes. What determines the start of the these parent nodes and the children nodes to follow?
When building a Binary Search Tree we always start at the root. In the best case scenarios, this root node will be exactly in the middle of all the other nodes. The left subtree will be filled with all nodes less than the value of the root node. Likewise, the right subtree will be filled with all nodes with a greater value than the root node. This trend follows all the way down the left and right subtrees until all nodes are represented making their own miniature subtrees inside of the original binary search tree.
Let’s assume we’re searching for the value in the 8th node of the binary search tree. Traversing down the tree from the root, you check the same way the whole tree was constructed. While moving through each node you check, is the node less than or greater than each subtree, then you move on repeating the process until you reach the node that its the original node you are searching for. When using Binary Search Tree’s in JavaScript you run tests starting with an initial conditional statement. Are these conditions met? If not, we move onto the next conditional statement that will tell us which direction to traverse, the left or right subtree. This process is repeated until we finally reach our destination.
Traversing through the BST is generally straight forwards which explains the time complexity relative to the size of the data set. Knowing how the code to search for values how a BST is constructed is just scratching the surface. While using this data structure, you can delete nodes and insert nodes where appropriate but when this happens, the rest of the tree might have to restructure based on the values left in the tree. Despite all this, this shows the flexibility while using this data structure.
Binary Search Trees Time Complexity simplifies searching through a organized data set through its construction. They are very similar in this sense to Arrays but with its ability to Delete and Insert values on the fly through the code and efficiently search for an exit value. Similar as such, you have the ability to Insert(), Delete(), Search(), as well as do ranged searches for values. This alone gives Binary Search Trees worth a second look the next time you’re given a data set regardless of size that you need to parse through to find what you’re looking for.
