taylorialcom/ DataStructures

Binary Search Trees

Left child smaller, right child bigger.

You should start by reading about binary search before reading this page. It assumes you understand that page.

Briefly, we applied binary search by recursively partitioning a sorted array into two pieces, doing one comparison, and then eliminating one (or both, if we found what we were looking for) partition.

Now lets consider a slightly different way of drawing the sorted array:

Figure [array2tree]: Array Redrawn as a Binary Search Tree

Tree Terminology

Figure [treenames]: Tree Terminology

1

Are you wondering what happens if you have two elements with the same value? If not, are you wondering why you are not wondering that? If not, repeat previous statement. Same valued entries are not allowed in a binary search tree. I.e., the values of all elements in a binary search tree must be unique.

2

Although our current textbook defines it as one more than this.

3

Sometimes balanced trees are called height-balanced trees to more clearly specify what about the tree is balanced.