# Class 39: Dictionaries (3): Binary Search Trees, Revisited

Held: Wednesday, April 12, 2006

Summary: Today we experimentally explore the binary-search-tree implementation of dictionaries.

Related Pages:

Notes:

Overview:

• Balanced Trees.
• Terminology.
• BSTs and Dictionaries.
• Removing Values.
• Lab.

## Search Trees, Revisited

• The definition of balanced is both important and subtle.
• The most important factor of a balanced tree is that the depth is no more than a constant different from the log of the size of the tree.
• However, that is an awkward definition.
• So, what definition should we use?
• Here's are a few. We will critique them.
• Def1: A tree is balanced if the depth of leaves differs by at most 1.
• Def2: A tree is balanced if the size of subtrees differs by at most 1.
• Def3: A tree is balanced if the size of subtrees differs by at most 1 and the subtrees are balanced.
• Def4: A tree is balanced if (a) the depth of the two subtrees differ by at most one; (b) both subtrees are balanced.
• Def1 permits fairly deep trees. (In fact, it permits a linear tree).
• Def2 also permits failry deep trees (Such as a tree that joins two linear trees).
• Def3 gives us the sense of balance we want, but it turns out that it's hard to guarantee that property in practice.
• Therefore, Def4 is the one we tend to use.

## Other Terminology

• Here are some other tree terms as I use them.
• A tree is full if all nodes have either 0 or two children.
• A tree is complete if it is full and all leaves are at the same level.
• Note: Some folks use complete for what I call nearly complete and perfect for what I call complete.
• Questions:
• Using my def'ns, are there full binary trees that are not complete?
• How do you decide which definitions are correct?

## Implementation Issues

• When implementing a dictionary using a binary search tree, the keys, rather than the values, are used to organize the tree.
• The left subtree has smaller keys.
• The right subtree has larger keys.
• How do you determine whether keys are smaller or larger?
• By storing `Comparable` values.
• By including a `Comparator` as part of the tree.
• I prefer the latter to the former.

## Deletion

• Deletion is slightly more complicated than suggested, in that you both need to both move a value up and "slide up" to replace that value.
• Deletion revisited:
• Consider the following:
```      D
/   \
B      Z
/ \    /
A   C  K
/
F
\
I
/ \
H   J
```
• Suppose we delete the D
```      _
/   \
B      Z
/ \    /
A   C  K
/
F
\
I
/ \
H   J
```
• We first need to determine the leftmost (smallest) value in the right subtree. That's F. We move it to the root.
```      F
/   \
B      Z
/ \    /
A   C  K
/
_
\
I
/ \
H   J
```
• We now have a gap where the F was. We know that that node has no left child (because it's the leftmost value). We slide up its right subtree.
```      F
/   \
B      Z
/ \    /
A   C  K
/
I
/ \
H   J
```
• Another complicating factor is what to do when there is no right subtree.
• A worse complicating factor is what to do when there are no subtrees at all.

## Lab

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 9 08:31:49 2006.
The source to the document was last modified on Thu Jan 12 14:58:07 2006.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2006S/Outlines/outline.39.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu