Just like storing anything else, when it comes to storing our data there are multiple ways that we can organize and store it. Each can have its own unique advantages depending on the situation at hand. In this article I'm going to cover tree data structures; specifically binary search trees, or 'BST's.
A binary search tree is a node-based data structure where each node can have a maximum of two child nodes. The first node of the tree is called the root node, and each child must either be a leaf node (having no child nodes of its own) or the root of another binary search tree. The left sub-tree contains nodes with values less than it's parent node, and the right sub-tree contains nodes with values greater than it's parent node. What determines a node being less than or greater than another node depends on the data type being used.
The sorting of values in BST keys help make operations run as efficiently as possible. BST traversal has an average time complexity of O(log n) when searching for, inserting, or removing data. Each operation reduces the size of the input by half, so we are constantly narrowing and speeding up our search, as long as the tree is properly balanced.
The key to having BSTs operate as efficiently as possible lies in keeping them balanced. The picture above shows a balanced tree on the left and an extremely unbalanced tree on the right. In the balanced tree, element #6 can be reached in three steps, but in the extremely unbalanced tree it takes six steps to reach element #6. There are multiple routes you can take to keep a BST balanced, like periodically balancing it or auto rebalancing after each addition or removal of values.
Above we can see how easy it can be to set up a binary search tree. In this example, I used the prototypal method to set up the tree's nodes and methods for node traversal. We pass the main value to the root node, and set up the left and right nodes for future additions of data. The chosen method should mostly depend on how much data is being stored in your BST, as rebalancing it with every change can get expensive if sorting through massive amounts of data.
Searching for data can also be super easy with BSTs. In the example above, I simply pass the value being searched for into the contains method I built on the tree. If the value is found on the root node, it is returned immediately. If not, and the value is less than the root, we search the left side of the tree recessively, and will search the right the same way if the value is greater than the root. The addition and removal of data can be done almost exactly the same way.
In conclusion BSTs can be a great choice when choosing a data structure for storing data. They allow us to efficiently store and update data efficiently in a sorted order, and offer O(log n) time complexity when traversing them. When in doubt, leaf it to BSTs to do the dirty work for you.
Top comments (0)