Transcript Binary Trees

IAT 265
Linked Lists,
Binary Search Trees
July 2, 2015
IAT 265
1
Data Structures
 With
a collection of data, we often want
to do many things
– Store and organize data
– Go through the list of data and do X per item
– Add new data
– Delete unwanted data
– Search for data of some value
• “Give me Smith’s phone number”
July 2, 2015
IAT 265
2
Arrays

0
1
2
3
Store data
4

arr[3] = 33



Add
arr[last] = newNumber ;
last++ ;
July 2, 2015
6
Delete i
for( j = i+1 ; j < last ; j++ )
arr[j-1] = arr[j] ;
last -- ;
Iterate (go thru):
for( i = 0 ; i < 10 ; i++)
sum = sum + arr[i] ;
5
IAT 265
Search for 42
for( i = 0 ; i < last ; i++ )
if( arr[i] == 42 )
SUCCESS ;
3
First Pointer
Linked List
0
P
1
P
3
2
P
4
P
P
A chain of nodes, where each node links to the
next
 Node Has:

– Value
– Pointer to Next Node

Inserting a new item is faster than array
– move pointers around
Deleting is also faster than array
 Searching takes time

– Must go link by link from Node to Node
July 2, 2015
IAT 265
4
First Pointer
Linked List
class Node {
int value ;
Node next ;
}
Node n, first ;

Store data

Iterate:
0
P
1
July 2, 2015
3
2
Add

Delete n1

Search 42
IAT 265
P
4
P
P

n.value = 33
n = first ;
while( n!= NULL ) {
sum += n.value ;
n = n.next;
}
P
n = new Node( 12 );
n.next = first ;
first = n ;
n1 = n.next ;
n.next = n1.next ;
n = first ;
while( n!= NULL ) {
if( n.value == 42 )
SUCCESS ;
n = n.next ;
}
5
Runtime
 Often,
we care about the time that
computation takes
 It’s ok if unimportant things run slow
 Important stuff needs to go fast
– Stuff that gets run all the time
– “The Inner Loop” is a slang term I use
July 2, 2015
IAT 265
6
What’s Important
 YOUR
time is important
 Runtime != Creation Time
 If any old algorithm will work,
– AND you’re only going to do it once or twice
– Use it!
 If
you’re going to run it millions of times
– Think about the algorithm!
July 2, 2015
IAT 265
7
Trees
A
Tree is a node-link structure
 It is built to enable fast searching
– What
– Store
– Go Thru
– Add
– Delete
– Search
July 2, 2015
Write
Like linked list
More complex
More complex
More complex
A little complex
IAT 265
Runtime
As fast
As fast
A little slower
A little slower
Much faster
8
Binary Search Tree
July 2, 2015
IAT 265
9
Binary Search Tree
 Each
Root Pointer
LP 3 RP
Node has two links
LP 5 RP
– left and right child
– Top node is root
– Node without children is leaf
 Binary
meaning two children
 Search tree because of the node
arrangement
July 2, 2015
IAT 265
10
Binary Search Tree
Root Pointer
LP 3 RP
LP 5 RP
LP 1 RP
LP 0 RP
July 2, 2015
LP 2 RP
LP 4 RP
IAT 265
LP 6 RP
11
Binary Search Tree
 For
Any node n
– To the left
• All child values are Less Than n
– To the right
• All child values are Greater Than n
 This
July 2, 2015
is a recursive definition!!!
IAT 265
12
Binary Search Tree
July 2, 2015
IAT 265
13
Nodes
 Typically,
each node has 3 or 4 parts:
– The key (names in pictures)
– The payload that goes with the key (not
shown)
– The left child pointer (possibly null)
– The right child pointer (possibly null)
July 2, 2015
IAT 265
14
Binary Search Tree Search
class BNode {
int
key ;
BNode left, right ;
}
BNode root, cursor ;
cursor = root ;
while( cursor != null )
// search for SEARCH
{
if( SEARCH == cursor.key )
SUCCESS ;
if( SEARCH > cursor.key )
cursor = cursor.right ;
else
cursor = cursor.left ;
}
July 2, 2015
IAT 265
15
Delete
July 2, 2015
IAT 265
16
Iterate (In Order)
public void inOrder (BNode cursor)
{
if (cursor == null)
return;
inOrder(cursor.left );
System.out.println(cursor.key );
inOrder(cursor.right );
}
July 2, 2015
IAT 265
17
Things aren’t perfect
 Unbalanced
searches
trees cause slower
– Balancing algorithms manage that
 Inserting
items in order can
cause this problem
July 2, 2015
IAT 265
18
Trees in Java

Use the TreeSet class to get this functionality
– You don’t have to build the structure yourself
– Stores Objects
TreeSet t1 = new TreeSet();
t1.add( “aaa” );
Iterator it1 = t1.iterator();
while( it1.hasNext() ) {
Object o1 =it1.next();
System.out.println( o1 );
}
July 2, 2015
IAT 265
19