Binary Search Tree
What is it? What is it good for?
I want to talk about a very important data structure. The Binary search tree. Despite the fact that the Binary Search tree was first introduced in the 1960’s, it remains one of the most versatile and common data structures.
Why is it so popular? In terms of complexity, the binary search tree ranks quite low, and yet, because of the rules applied to its structure it can pull off some interesting feats in astonishingly low time complexity.
In order to demonstrate the difference in complexity, I’m going to show you some different data structures.
Take this graph for example :
While this graph is undoubtedly useful (And possibly necessary) for that task, I think we can clearly see how even a large binary tree would be more simple. Now, see this unrooted binary tree :
The basic rule of the binary tree is this. Each branch separates into two parts (binary) The keys in the branch to one side is always ordered higher (numerically or alphabetically), the keys in the branch to the other side is always ordered lower. This remains true for every single branch all the way down to the ends of each leaf.
Before we move forward I want to mention that the binary search tree has many versions with different implementations. Also, it can be done in many different ways that change both it’s features and complexity, but for this article, I’m only going to go over the most rudimentary of implementations.
In its basic form, it is necessary to have unique keys, and the keys are typically numbers or strings with an associated value that could be anything. This way the tree can be assembled and searched very quickly and easily without any major complications.
Balance
Lastly, your tree should be balanced at all times unless there is some specific and important reason to the contrary. If your tree is not balanced it makes the time complexity significantly worse. Worst-case scenario your tree becomes more or less the same as a linked list with nearly identical time complexities for all major features.
Time complexities. The reason why balanced Binary trees are so great.
Let’s compare it to an array. An array is an ordered list.
Array
Look up? O(1)
Insert? O(n)
Delete? O(n)
Search? O(n)
The reason why this is the case is that, for an array to maintain it’s status as an ordered list it has to update the entire list. If you delete something from the middle of an array it has to move everything over so the order remains intact. If you insert, the same, and to search for a value you have to iterate through it until you find what you want. The primary advantage is that you can look up any particular value in constant time by using the index.
Balanced Binary Search Tree (AVL)
Lookup? O(log(n))
Insert? O(log(n))
Delete? O(log(n))
Search? O(log(n))
The balanced binary search tree needs to maintain some order, but it’s not quite as strict as an array. The order is partitioned into greater or less than evaluations rather than an ordered key lookup. If the root is 356 and the value you are looking for is 670, the algorithm for search goes directly into the greater than branch, thus eliminating half of the tree from relevance right out of the gate.
In order to delete or insert, you simply need to find the target location which is typically done exactly the same as your search algorithm, then make a constant time operation to add or remove the new element. This is done by changing some pointers around, similar to how you would restructure a linked list.
There also some additional unforseen advantages. You might even be able to pull off dancing links with a binary search tree.
Of course, this is assuming your tree stays balanced. The more unbalanced it becomes the more it will behave like a linked list.
But this is all I have time for right now. I will have to discuss how to build one and some additional details at a later date.
