Class Notes (1,100,000)
CA (620,000)
Queen's (10,000)
CISC (500)
Lecture 11

CISC 235 Lecture Notes - Lecture 11: Binary Search Tree, Longest Path Problem, Complex Instruction Set Computing


Department
Computing
Course Code
CISC 235
Professor
Robin W Dawes
Lecture
11

This preview shows pages 1-3. to view the full 14 pages of the document.
CISC 235 Lecture 11
Red-Black Trees
As we have seen, the ideal Binary Search Tree has height
approximately equal to log n, where n is the number of values
stored in the tree. Such a BST guarantees that the maximum time
for searching, inserting and deleting values is always in O(log
n). However, if we have no control over the order in which the
values are added and/or deleted, the BST may end up looking like
a linked list, with each vertex having just one child. In this case
the maximum time for searching, inserting and deleting values is in
O(n), which is no better (and in the case of searching, much worse)
than the time required for these operations if we store the set in a
sorted array.
In order to claim that BSTs are better than sorted arrays, we need
to find a way to always attain that desirable O(log n) time for the
three operations. One way would be to rebuild the tree from
scratch after each insertion or deletion ... but that would be a lot of
work.
In the 1960's, people started to use the term "balanced" to describe
trees where each vertex has the property that its left subtree and
right subtree are "about the same height" ... of course "about the
same height" can be interpreted in different ways.
Red-Black trees were invented in 1972 in an effort to create a
binary search tree structure that maintains O(log n) height while
requiring relatively few re-organizations of the tree. In a Red-
Black tree, the idea of balance is "at each vertex, neither subtree is
more than twice as tall as the other". For your own interest you
may want to read about AVL trees, which have similar properties
but a much stricter balance rule.

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

A Red-Black tree is a binary search tree in which each vertex is
coloured either Red or Black. In practice all that is required is a
single bit to indicate if the vertex is Red or Black, but for learning
purposes we can imagine that the vertices are physically painted.
Red-Black trees are usually described as obeying the following
rules (which I might have listed in a different order in class):
1. The root is Black
2. All leaves are empty (i.e. data values are only stored in
internal vertices)
3. All leaves are Black
4. Every internal vertex has 2 children
5. Red vertices cannot have Red children
6. At each vertex, all paths leading down to leaves contain the
same number of Black vertices
This allows for significant differences in height between the left
subtree and the right subtree at any given vertex. For example, the
left subtree might consist entirely of Black vertices and have height
x, while the right subtree might consist of alternating levels of Red
and Black vertices and have height 2*x.
In fact, we can quickly show that in a Red-Black tree each vertex
must have the property that if we look at the longest path down
from this vertex to a leaf, this path cannot be more than twice the
length of the shortest path down from this vertex to a leaf:
Let v be any internal vertex, and let the longest path from v down
to a leaf have length k, and let b be the number of Black vertices in
this path. In this path, every Red vertex must have a Black child,
so the number of Red vertices must be <= k/2. Thus b >= k/2.
Now consider the shortest path from v down to a leaf. Let the
length of this path be k'. Since all paths from v down to a leaf

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

must contain the same number of Black vertices (Rule 6), we know
k' >= b
Putting these together gives k' >= b >= k/2, which gives us k <=
2*k' .... that is, the length of the longest path is <= twice the
length of the shortest path.
At this point I am just going to claim that a tree that satisfies these
rules must have O(log n) height, where n is the number of values in
the tree. We will prove this claim at the end of this page of notes.
The significance of these rules is that they are all "local" in the
sense that we are specifying properties of individual vertices, and
yet by satisfying these local rules, we obtain the desired "global"
property that the whole tree has O(log n) height. This means that
when we do insertions and deletions, as long as our operations on
the tree are such that the local requirements are always satisfied,
we never need to worry that the height of the tree is growing out of
control . As we will see, inserting new values into the tree can be
done in such a way that the requirements are satisfied using only
local changes to the tree. What's more, the balancing operations
are simple.
We will not discuss the details of deleting a value from a Red-
Black tree. The principles are the same, but it is time-consuming
to cover all the details.
From now on in these notes I am going to be lazy and use RB
instead of Red-Black
Inserting A New Value into an RB Tree
As with any binary search tree, there is exactly one legal place for
a new value to be inserted. The RB insertion algorithm starts by
finding this place. Due to the structural requirements of the tree
You're Reading a Preview

Unlock to view full version