Binary Search Trees

Internal

• Tree Concepts

Overview

A binary search tree is a binary tree that has the Binary Search Tree Property. A binary search tree is represented in memory using three pointers: left child, right child and the parent. More details on binary tree representation in memory are available here:

Binary Tree Representation in Memory

Binary Search Tree Property

The fundamental property of the binary search tree, called the Binary Search Tree Property:

For every single node of a binary search tree, if the node has a key value, then all of the keys stored in the left subtree should be less than the node's key value and all of the keys stored in the right subtree should be bigger than the node's key value. This property holds not only at the root, but in every single node of the three.

Note that the Binary Search Tree Property is different from the Heap Property. Search tree are designed so we can search easily through them, unlike heaps that are designed to find the minimum (or maximum) easily.

TODO CLRS Page 286.

Balanced vs. Unbalanced Binary Search Trees

A binary search tree can be unbalanced or balanced. For the same set of key, the search tree can vary in height between log n and n, where n is the number of keys. Balanced trees are more useful for search because they yield better running times, so techniques to keep the tree balanced while inserting or deleting nodes have been developed.