Self-Balancing Binary Search Tree
Explore the concept of self-balancing binary search trees to understand how they maintain efficiency by limiting tree height. This lesson explains the limitations of standard BSTs and introduces the motivation for using rotations to keep trees balanced, enhancing search and insertion performance in programming contests.
We'll cover the following...
Binary Search Tree
Before we begin our discussion about Self-balancing BST (or Balanced BST). Let’s recall what a BST is and why is there a need for an efficient variation.
BST is a rooted binary tree where:
- The left subtree of a node contains only nodes with smaller keys.
- The right subtree of a node contains only nodes with larger keys.
For example:
Limitation
The order of keys matters while building a BST. That means that the same set of keys can result in different structures of the resulting BST depending on the order of insertion.
Let’s take a simple example with 3 keys in different order: