Class Notes (1,100,000)

CA (620,000)

Queen's (10,000)

CISC (500)

CISC 235 (20)

Robin W Dawes (20)

Lecture 11

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

by OC330671

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