A Binary Search Tree Implementation - Data Structures and Abstractions with Java - page 654

The notion of balance affects the performance of a particular search tree. In a completely balanced
tree, the subtrees of each node have exactly the same height. The only completely balanced binary trees are
full. Other trees are said to be height balanced , or simply balanced , if the subtrees of each node in the
tree differ in height by no more than 1. A complete binary tree is height balanced, for example, but so are
some trees that are not complete, as Figure 25-14 shows. Moreover, the concept of balance applies to all
trees, not just binary trees or binary search trees.
It happens that the addition, removal, and retrieval operations of a binary search tree will have
O(log n ) performance if the tree is height balanced. Certainly when we create a binary search tree,
we want it to be height balanced. Unfortunately, we can disturb the balance of a binary search tree
by adding or removing entries, since these operations affect the shape of the tree.

FIGURE 25-14

Some binary trees that are height balanced

(a)

Balanced and complete

(b) (d)

(c)

Balanced but not complete

The Order in Which Nodes Are Added
25.42

If you answered Question 7 in Segment 25.12 correctly, you realized that the order in which you
add entries to a binary search tree affects the shape of the tree. This observation is most important
when you create a binary search tree by making additions to an initially empty tree.
For example, suppose that we want to create the full binary search tree in Figure 25-13a
from a given set of data. Often such data sets are sorted, so it is reasonable to assume that we
have the names in alphabetical order. Now imagine that we define an empty binary search tree
and then add the names to it in the following order: Brett , Brittany , Doug , Jared , Jim , Megan ,
Whitney . Figure 25-13b shows the tree that results from these additions. It is as tall as possible and
has the least efficient operations among the trees that we could build.

Note: If you add entries into an initially empty binary search tree, do not add them in
sorted order.