Balanced Binary Search Tree

Balanced binary search trees are used as in-memory data structures in the database to store ordered data due to their constant time complexity for inserts and updates.

Introduction

The height of a particular node in a tree is the total number of edges from that specific node to the deepest leaf node. The total height of a tree is computed by calculating the number of edges from the root node to the deepest leaf node.

A balanced binary search tree is an extension of a binary search tree, where the difference between the left subtree's height and the right subtree's height at every node is one of [-1, 0, 1]. This difference is called the balance factor.

The example above demonstrates a balanced BST where-in the Balance factor is always one of [-1, 0, 1] at every subtree.

Since the tree is always balanced, following the left or right subtree always reduces the search space by exactly half. So the time complexity of search and insert is always$O(log_2N)$ ...