Transcript Oct 14 - Joshua Stough

CSCI 62
Data Structures
Dr. Joshua Stough
October 14, 2008
So far
•
•
•
•
•
•
Object-oriented design
Generics (Vector)
Asymptotics, O notation, recursion
Sorting (insertion, selection, quick, merge)
Lists (singly, doubly, circularly-linked)
Stacks and Queues
To come
• Binary Structures (this week)
• Priority Queues, Heaps, Heap Sort
• Search Trees, Maps, Hash Tables
• Some Graphs
• C++
Today
• Ordered Structures
– Structures that hold data in order.
– Comparable, compareTo.
• Binary Trees
Ordered Structures
• Data structures are commonly used to
keep data in order.
• Objects that can be ordered requires a
means of comparison.
– Ex. Class implements Comparable.
Ordered Structures
• Example, comparable Ratio
Ordered Structures
• Could also define your own equals
Ordered Structures
• You may insist that elements within the
structure be comparable
Ordered Structures
• Use the compareTo of the type K
Ordered Vector
• Allocate the underlying Vector.
– Ensure add, remove maintain order.
OrderedVector
OrderedVector
OrderedList
• OrderedVector complexities:
– O(log n) find, O(n) insert/delete
• OrderedList
– O(n) find, O(n) insert/delete
– Bailey’s purpose is to show off using a
Comparator
BinaryTree
• The way we store data has an effect on
the speed of certain ops.
– OrderedVector allowed O(log n) access
BinaryTree
• Tree – collection of nodes with edges
between them.
– Defined recursive as the means of making
a tree from a set of trees.
• Parent, sibling, root, Node, leaf
BinaryTree
BinaryTree
• Empty node is base case, so that
methods can be applied.
– right() is null.
• Each node of BinaryTree is itself a
BinaryTree type
– Allows methods like setValue, setLeft, to
make sense.
BinaryTree
BinaryTree
• Traversals: in-order, post-order, preorder, level order.
BinaryTree
BinaryTree
20 Questions
• Have it discriminate between
– Singly, Doubly, Circularly-Linked, Stack,
Queue, Vector.
BinaryTree PreOrder
BinaryTree PreOrder
BinaryTree InOrder
BinaryTree In Order
BinaryTree PostOrder
BinaryTree PostOrder
• Level Order
uses Queue.
Why?
BinaryTree
• Traversals
easier to think
about if
reseting can
be linear,
rather than
constant.
BinaryTree – more points