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.