My previous post introduced the Binary Search Tree, we’ve known the binary search tree has great performances in searching for a data. Do you ever think about the downside of the binary search tree? In this post, I’m going to explain the downside of the binary search tree and find a solution to it.
When BSTs fall
Recall the rules of binary search tree: data of the left child is less than the parent node, data of the right child is greater than the parent node. How about we have a sorted data like:
let array = [0, 1, 2, 3, 4, 5, 6]When we insert each element into a binary search tree, the data structure will look like this:
See the problem? The binary search tree here is no longer a ‘tree’, It’s more like a linked list! Recall the average running time for searching an element in a binary search tree is O(log(n)), but here, the running time could be O(n)!
That’s bad!
Solutions for that: balanced trees!
The solution for it is balanced trees! In order to guarantee the O(log(n)) search time, we need some logic to balance the tree every time we insert or remove a node.
There are lots of data structures to implement it! The famous ones include AVL tree, Red-Black tree, Splay tree. They both have particular rules to implement a search tree. In this post, I’m going to introduce the AVL tree, because it’s a relatively easier balanced tree to understand.
Introducing the AVL tree & rules
AVL tree is created by inventors Adelson-Velsky and Landis in 1962. The properties of the AVL tree is different than the BST:
- Each tree node records its own height, and we update the height when we add/remove a node.
- The height o the left and right subtree of every node differ by a height of no more than 1(the height of an empty tree is defined to be −1).
To have a better understanding of rules, you can play with AVL trees use this website.
The properties above mean we need a ‘rotation’ to ‘rebalance’ the tree when the height difference is greater than 1!
Rotation Solutions
In an imbalanced tree, given the grandparent, parent, child node, here we need to specify four cases:
- an insertion into the left subtree of the left child of the tree
- an insertion into the right subtree of the left child of the tree
- an insertion into the left subtree of the right child of the tree
- an insertion into the right subtree of the right child of the tree
The first case and the last case can also be specified as ‘left-left’, and ‘right-right’ condition. These two cases can be solved by a single rotation.
To be brief, The Single Rotation is taking the parent and making it the new grandparent position, the grandparent and child will become the new children.
The second case and the third case is a little bit more complicated compared with the other two cases, these two cases can be solved by a double rotation.
The double rotation, as it sounds like, is doing rotation twice. Basically, it’s done by two calls to the single rotation: once clockwise and other counter-clockwise. But we need to specify them during different cases.
That’s how a balanced binary tree works!
