Trees

Main and Savitch

Chapter 10
 Binary
Binary Trees
Trees
• A binary tree has nodes, similar to nodes in a
linked list structure.
• Data of one sort or another may be stored at each
node.
• But it is the connections between the nodes which
characterize a binary tree.
 A
A Binary
Binary Tree
Tree of
of States
States

In this example,
the data
contained at
each node is
one of the 50
states.
 A
A Binary
Binary Tree
Tree of
of States
States

Each tree has a

special node
called its root,
usually drawn
at the top.
 A
A Binary
Binary Tree
Tree of
of States
States

Each tree has a

special node
called its root,
usually drawn
at the top. The
Theexample
exampletreetree
has
hasWashington
Washington
as
asits
itsroot.
root.
 A
A Binary
Binary Tree
Tree of
of States
States

Each node is
permitted to
have two links
to other nodes,
called the left
child and the
right child.
 A
A Binary
Binary Tree
Tree of
of States
States

Children are
usually drawn
below a node.

The The
Theright
right child
childof
of
Theleft
leftchild
childof
of Washington
Washington Washingtonisis
Washingtonisis Colorado.
Arkansas. Colorado.
Arkansas.
 A
A Binary
Binary Tree
Tree of
of States
States

Some nodes
have only one
child.

Arkansas
Arkansashas hasaa
left
leftchild,
child, but
butnono
right
right child.
child.
 A
A Quiz
Quiz

Some nodes
have only one
child.

Which
Which nodenode has
has
only
only aa right
right child?
child?
 A
A Quiz
Quiz

Some nodes
have only one
child.

Florida
Floridahas
has
only
onlyaaright
rightchild.
child.
 A
A Binary
Binary Tree
Tree of
of States
States

A node with no
children is
called a leaf.
 A
A Binary
Binary Tree
Tree of
of States
States

Each node is
called the
parent of its
children.

Washington
Washingtonisisthe
the
parent
parentof
ofArkansas
Arkansas
and
andColorado.
Colorado.
 A
A Binary
Binary Tree
Tree of
of States
States

Two rules about parents:

 The root has no

parent.
 Every other node
has exactly one
parent.
 A
A Binary
Binary Tree
Tree of
of States
States

Two nodes with

the same parent
are called
siblings.

Arkansas
Arkansas
and
andColorado
Colorado
are
aresiblings.
siblings.
 Complete
Complete Binary
Binary Trees
Trees
A complete
binary tree is a
special kind of
binary tree
which will be
useful to us.
 Complete
Complete Binary
Binary Trees
Trees
A complete
binary tree is a
special kind of
binary tree
which will be
useful to us. When
Whenaacomplete
complete
binary
binarytree
treeisisbuilt,
built,
its
itsfirst
first node
nodemust
must bebe
the
theroot.
root.
 Complete
Complete Binary
Binary Trees
Trees
The second node of a
complete binary tree
is always the left
child of the root...
 Complete
Complete Binary
Binary Trees
Trees
The second node of a
complete binary tree
is always the left
child of the root...
... and the third node
is always the right
child of the root.
 Complete
Complete Binary
Binary Trees
Trees
The next
nodes must
always fill
the next level
from left to
right.
 Complete
Complete Binary
Binary Trees
Trees
The next
nodes must
always fill
the next level
from left to
right.
 Complete
Complete Binary
Binary Trees
Trees
The next
nodes must
always fill
the next level
from left to
right.
 Complete
Complete Binary
Binary Trees
Trees
The next
nodes must
always fill
the next level
from left to
right.
 Complete
Complete Binary
Binary Trees
Trees
The next
nodes must
always fill
the next level
from left to
right.
 Complete
Complete Binary
Binary Trees
Trees
The next
nodes must
always fill
the next level
from left to
right.
Is
Is This
This Complete?
Complete?
Is
Is This
This Complete?
Complete?
Is
Is This
This Complete?
Complete?
Is
Is This
This Complete?
Complete?
 Is
Is This
This Complete?
Complete?
Yes!
It is called the empty tree,
and it has no nodes,
not even a root.
Implementing
Implementing aa Complete
Complete Binary
Binary
Tree
Tree
• We will store the data from the nodes
in a partially-filled array.
3 An integer to keep
track of how many nodes are in the tree

An array of data
We don't care what's in
this part of the array.
Implementing
Implementing aa Complete
Complete Binary
Binary
Tree
Tree
• We will store the date from the nodes
in a partially-filled array.
3 An integer to keep
track of how many nodes are in the tree

Read
ReadSection
Section10.2
10.2 to
to
see
seedetails
detailsof
of how
how
the
theentries
An array of data entriesare
arestored.
stored.
We don't care what's in
this part of the array.
 Depth
Depth of
of Binary
Binary Tree
Tree

This example, depth = 3

 Depth
Depth of
of Binary
Binary Tree
Tree

This example, depth = 2

 Depth
Depth of
of Binary
Binary Tree
Tree

This example, depth = 0

 Depth of Complete Binary Tree
Given a complete binary tree of N nodes,
what is the depth?

D=0
N=1 D=1 D=1
N=3 N=2 D=2 D=2
N=7 N=4
 Depth of Complete Binary Tree
Given a complete binary tree of N nodes,
what is the depth?

D=0
N=1 D=1 D=1
N=3 N=2 D=2 D=2
N=7 N=4

D = floor(log N) = O(log N)
 Depth of Binary Tree
Given a binary tree of N nodes, what is the
maximum possible depth?

D=0
N=1 D=2
N=3 D=4
N=5

D = O(N)
 Summary
Summary
• Binary trees contain nodes.
• Each node may have a left child and a right child.
• If you start from any node and move upward, you
will eventually reach the root.
• Every node except the root has one parent. The
root has no parent.
• Complete binary trees require the nodes to fill in
each level from left-to-right before starting the
next level.
Binary
Binary Search
Search Trees
Trees

• One of the tree applications in

Chapter 10 is binary search trees.
• In Chapter 10, binary search trees
are used to implement bags and
sets.
• This presentation illustrates how
another data type called a
dictionary is implemented with
binary search trees.
 The
The Dictionary
Dictionary Data
Data Type
Type

• A dictionary is a collection
of items, similar to a bag.
• But unlike a bag, each item
has a string attached to it,
called the item's key.
 The
The Dictionary
Dictionary Data
Data Type
Type

• A dictionary is a collection
of items, similar to a bag.
• But unlike a bag, each item
has a string attached to it,
called the item's key.
Example:
The items I am
storing are records
containing data
about a state.
 The
The Dictionary
Dictionary Data
Data Type
Type

• A dictionary is a collection
of items, similar to a bag.
• But unlike a bag, each item
has a string attached to it,
called the item's key.
Example:
The key for each
record is the name
of the state.
Washington
 The
The Dictionary
Dictionary Data
Data Type
Type

void Dictionary::insert(The key for the new item, The new item);

• The insertion procedure for a

dictionary has two
parameters.

gt o n
ashin
W
 The
The Dictionary
Dictionary Data
Data Type
Type
• When you want to retrieve an
item, you specify the key...

Item Dictionary::retrieve("Washington");
 The
The Dictionary
Dictionary Data
Data Type
Type
 When you want to retrieve an
item, you specify the
key... ... and the retrieval
procedure returns the item.

Item Dictionary::retrieve("Washington");
 The
The Dictionary
Dictionary Data
Data Type
Type

• We'll look at how a binary

tree can be used as the
internal storage mechanism
for the dictionary.
 A
A Binary
Binary Search
Search Tree
Tree of
of States
States

F lo
ri d a
The data in the
dictionary will
be stored in a Colorado Oklahoma

binary tree,
with each node Mass.
Arizona
containing an Washington

item and a key.

Hampshire
New

Virginia
West
Arkansas
 A
A Binary
Binary Search
Search Tree
Tree of
of States
States

F lo
ri d a
Storage rules:
1. Every key to the left
Colorado Oklahoma
of a node is
alphabetically before
the key of the node. Arizona Mass.

Washington

Hampshire
New

Virginia
West
Arkansas
 A
A Binary
Binary Search
Search Tree
Tree of
of States
States

F lo
ri d a
Storage rules:
1. Every key to the left
Colorado Oklahoma
of a node is
alphabetically before
the key of the node. Arizona Mass.

Washington
Example:
' Massachusetts' and

Hampshire
' New Hampshire'

New

Virginia
West
Arkansas
are alphabetically
before 'Oklahoma'
 A
A Binary
Binary Search
Search Tree
Tree of
of States
States

F lo
ri d a
Storage rules:
1. Every key to the left
Colorado Oklahoma
of a node is
alphabetically before
the key of the node. Arizona Mass.

Washington
2. Every key to the
right of a node is

Hampshire
New
alphabetically after

Virginia
West
Arkansas
the key of the node.
 A
A Binary
Binary Search
Search Tree
Tree of
of States
States

F lo
ri d a
Storage rules:
1. Every key to the left
Colorado Oklahoma
of a node is
alphabetically before
the key of the node. Arizona Mass.

Washington
2. Every key to the
right of a node is

Hampshire
New
alphabetically after

Virginia
West
Arkansas
the key of the node.
 Retrieving
Retrieving Data
Data

F lo
ri d a
Start at the root.
1. If the current node has
the key, then stop and Colorado Oklahoma

retrieve the data.

2. If the current node's Mass.

key is too large, move Arizona

Washington
left and repeat 1-3.

Hampshire
3. If the current node's

New
key is too small, move

Virginia
West
Arkansas
right and repeat 1-3.
 Retrieve
Retrieve '' New
New Hampshire'
Hampshire'

F lo
ri d a
Start at the root.
1. If the current node has the
key, then stop and
Colorado Oklahoma
retrieve the data.
2. If the current node's key is
too large, move left and Mass.
Arizona
repeat 1-3. Washington

3. If the current node's key is

Hampshire
too small, move right

New
and repeat 1-3.

Virginia
West
Arkansas
 Retrieve
Retrieve 'New
'New Hampshire'
Hampshire'

F lo
ri d a
Start at the root.
1. If the current node has the
key, then stop and Colorado Oklahoma
retrieve the data.
2. If the current node's key is
too large, move left and Arizona
Mass.

Washington
repeat 1-3.
3. If the current node's key is

Hampshire
too small, move right

New

Virginia
West
and repeat 1-3. Arkansas
 Retrieve
Retrieve 'New
'New Hampshire'
Hampshire'

F lo
ri d a
Start at the root.
1. If the current node has the
key, then stop and Colorado Oklahoma
retrieve the data.
2. If the current node's key is
too large, move left and Arizona
Mass.

Washington
repeat 1-3.
3. If the current node's key is

Hampshire
too small, move right

New

Virginia
West
and repeat 1-3. Arkansas
 Retrieve
Retrieve 'New
'New Hampshire'
Hampshire'

F lo
ri d a
Start at the root.
1. If the current node has the
key, then stop and Colorado Oklahoma
retrieve the data.
2. If the current node's key is
too large, move left and Arizona
Mass.

Washington
repeat 1-3.
3. If the current node's key is

Hampshire
too small, move right

New

Virginia
West
and repeat 1-3. Arkansas
 Retrieval: Complexity
• Given a complete tree of N items, the depth D =
O(log N).
• What is the maximum number of nodes tested to
retrieve an item from the binary search tree if we
use a complete tree?
• What is the maximum number of nodes tested
(worst case) to retrieve an item from a binary
search tree that is not complete or balanced?
 Adding
Adding aa New
New Item
Item with
with aa
Given
Given Key
Key

F lo
ri d a
1. Pretend that you are
trying to find the key,
but stop when there is Colorado Oklahoma

no node to move to.

2. Add the new node at Arizona
Mass.

the spot where you Washington

would have moved to

Hampshire
if there had been a

New

Virginia
West
Arkansas
node.
 Iowa

Adding
Adding

F lo
ri d a
1. Pretend that you are
trying to find the key,
but stop when there is Colorado Oklahoma

no node to move to.

2. Add the new node at Arizona Mass.

the spot where you Washington

would have moved to

Hampshire
if there had been a

New

Virginia
West
Arkansas
node.
 Iowa

Adding
Adding

F lo
ri d a
1. Pretend that you are
trying to find the key,
but stop when there is Colorado Oklahoma

no node to move to.

2. Add the new node at Arizona Mass.

the spot where you Washington

would have moved to

Hampshire
if there had been a

New

Virginia
West
Arkansas
node.
 Iowa

Adding
Adding

F lo
ri d a
1. Pretend that you are
trying to find the key,
but stop when there is Colorado Oklahoma

no node to move to.

2. Add the new node at Arizona Mass.

the spot where you Washington

would have moved to

Hampshire
if there had been a

New

Virginia
West
Arkansas
node.
 Iowa

Adding
Adding

F lo
ri d a
1. Pretend that you are
trying to find the key,
but stop when there is Colorado Oklahoma

no node to move to.

2. Add the new node at Arizona Mass.

the spot where you Washington

would have moved to

Hampshire
if there had been a

New

Virginia
West
Arkansas
node.
 Iowa

Adding
Adding

F lo
ri d a
1. Pretend that you are
trying to find the key,
but stop when there is Colorado Oklahoma

no node to move to.

2. Add the new node at Arizona Mass.

the spot where you Washington

would have moved to

Hampshire
if there had been a

New

Virginia
West
Arkansas
node.
 Adding
Adding

F lo
ri d a
1. Pretend that you are
trying to find the key,
but stop when there is Colorado Oklahoma

no node to move to.

2. Add the new node at Arizona Mass.

the spot where you Washington

would have moved to Iowa

Hampshire
if there had been a

New

Virginia
West
Arkansas
node.
 Ka
z ak h
st a
n

Adding
Adding

F lo
ri d a
Where
Where would
would youyou Oklahoma
add
add this
this state?
state?
Colorado

Mass.
Arizona
Washington

Iowa

Hampshire
New

Virginia
West
Arkansas
 Adding
Adding

F lo
ri d a
Kazakhstan
Kazakhstan isisthe
the
new
newright
rightchild
child Colorado Oklahoma
of
ofIowa?
Iowa?

Mass.
Arizona
Washington

Iowa

Hampshire
New

Virginia
West
Arkansas
Ka
z ak h
st a
n
 Adding: Complexity
• Given a complete tree of N items, the depth D =
O(log N).
• What is the maximum number of nodes tested to
add an item to the binary search tree if we use a
complete tree?
• What is the maximum number of nodes tested
(worst case) to add an item from a binary search
tree that is not complete or balanced?
 Removing
Removing an
an Item
Item with
with aa
Given
Given Key
Key

F lo
ri d a
1. Find the item.
2. If necessary, swap the
Colorado Oklahoma
item with one that is
easier to remove.
3. Remove the item. Arizona
Mass.

Washington

Iowa

Hampshire
New

Virginia
West
Arkansas
Ka
za kh
st a
n
 Removing
Removing 'Florida'
'Florida'

F lo
ri d a
1. Find the item.

Colorado Oklahoma

Mass.
Arizona
Washington

Iowa

Hampshire
New

Virginia
West
Arkansas
Ka
za kh
st a
n
 Removing
Removing 'Florida'
'Florida'

F lo
ri d a
Colorado Oklahoma

Mass.
Arizona
Washington
Florida
Floridacannot
cannotbe be
removed
removedatat the
the
Iowa

Hampshire
moment...

New
moment...

Virginia
West
Arkansas
Ka
za kh
st a
n
 Removing
Removing 'Florida'
'Florida'

Colorado Oklahoma

Mass.
Arizona
...
... because
becauseremoving
removing
Washington

Florida
Floridawould
would Iowa

Hampshire
break
breakthe
the tree
tree into
into

New
two
twopieces.

Virginia
pieces.

West
Arkansas
Ka
za kh
st a
n
 Removing
Removing 'Florida'
'Florida'

F lo
ri d a
1. If necessary, do some
rearranging.
Colorado Oklahoma

Mass.
Arizona
The
Theproblem
problem ofof
Washington

breaking
breakingthe
thetree
tree Iowa

Hampshire
happens
happens because
because

New
Florida
Florida has
has22children.

Virginia
children.

West
Arkansas
Ka
za kh
st a
n
 Removing
Removing 'Florida'
'Florida'

F lo
ri d a
If necessary, do some
rearranging.
Colorado Oklahoma

Mass.
Arizona
Washington
For
Forthe
therearranging,
rearranging,
take
takethethe smallest
smallest item
item
Iowa

Hampshire
in
inthe
theright
rightsubtree...

New
subtree...

Virginia
West
Arkansas
Ka
za kh
st a
n
 Removing
Removing 'Florida'
'Florida'
Iowa

If necessary, do some
rearranging.
Colorado Oklahoma

Mass.
Arizona
Washington
...copy
...copythat
thatsmallest
smallest
item
itemonto
ontothe
theitem
item
Iowa

Hampshire
that
thatwe're
we'reremoving...

New
removing...

Virginia
West
Arkansas
Ka
za kh
st a
n
 Removing
Removing 'Florida'
'Florida'
Iowa

If necessary, do some
rearranging.
Colorado Oklahoma

Mass.
Arizona
Washington
...
...and
and then
then remove
remove
the
the extra
extracopy
copyofofthe
the

Hampshire
item
itemwewecopied...

New
copied...

Virginia
West
Arkansas
Ka
za kh
st a
n
 Removing
Removing 'Florida'
'Florida'
Iowa

If necessary, do some
rearranging.
Colorado Oklahoma

Mass.
Arizona
Washington
Ka
... and reconnect za kh
st an

Hampshire
the tree

New

Virginia
West
Arkansas
 Removing
Removing 'Florida'
'Florida'

F lo
ri d a
Colorado Oklahoma

Mass.
Arizona
Why
Why diddid we
we choose
choose
Washington

the
the smallest
smallest item
item

Hampshire
New
in
in the
the right
right subtree?
subtree?

Virginia
West
Arkansas
Ka
za kh
st a
n
 Removing
Removing 'Florida'
'Florida'
Iowa

Colorado Oklahoma

Mass.
Arizona
Washington
Because every key Ka
za
must be smaller than kh
st an

Hampshire
the keys in its

New

Virginia
right subtree

West
Arkansas
 Removing
Removing an
an Item
Item with
with aa
Given
Given Key
Key
1. Find the item.
2. If the item has a right child, rearrange the tree:
1. Find smallest item in the right subtree
2. Copy that smallest item onto the one that you
want to remove
3. Remove the extra copy of the smallest item
(making sure that you keep the tree connected)
3. else just remove the item.
 Summary
Summary
• Binary search trees are a good implementation of
data types such as sets, bags, and dictionaries.
• Searching for an item is generally quick since you
move from the root to the item, without looking at
many other items.
• Adding and deleting items is also quick.
• But as you'll see later, it is possible for the
quickness to fail in some cases -- can you see
why?