Binary Search Trees

Introduction

• a binary tree that satisfies the BST invariant: left subtree has smaller elements and right subtree has larger elements
• BST operations allow for duplicate values, but most of the time we are only interested in having unique elements inside our tree
• it is called a search tree because it can be used to search for the presence of a number in O(log(n)) time.

Usage

• implementation of Map and Set ADTs
• Red Black Trees, AVL Trees, Splay Trees, etc.
• implementation of Binary Heaps
• Syntax Trees, used by compilers and calculators
• Treap, probabilistic DS, uses a randomized BST
• multilevel indexing in the database
• dynamic sorting
• managing virtual memory areas in Unix kernel

Implementation

Insert Operation