Transcript Searching: Binary Trees and Hash Tables

Binary Trees
Gordon College
Prof. Brinton
1
Good O’ Linear Search
• Collection of data items to be searched is
organized in a list
Not sorted
x 1, x 2, … x n
Must assume = = and < operators defined for the type
• Linear search begins with item 1
– continue through the list until target found
– or reach end of list
2
Linear Search
Vector based search function
template <typename t>
void LinearSearch (const vector<t> &v,
const t &item,
boolean &found, int &loc)
{ found = false; loc = 0;
for ( ; ; )
{
if (found || loc == v.size()) return;
if (item == x[loc]) found = true;
else loc++; }
usage
}
LinearSearch(vect,num,found,loc);
3
Linear Search
Singly-linked list based search function
template <typename t>
void LinearSearch (NodePointer first,
const t &item,
boolean &found, int &loc)
{ found = false; locptr = first;
for ( ; ; )
{
if (found || locptr == NULL) return;
if (item == locptr->data)
found = true;
else
In both cases, the
loc++; }
worst case computing
}
time is still O(n)
4
Binary Search
Binary search function for vector
template <typename t>
void LinearSearch (const vector<t> &v,
const t &item,
boolean &found, int &loc)
{
found = false;
int first = 0;
last = v.size() - 1;
for ( ; ; )
{ if (found || first > last) return;
loc = (first + last) / 2;
if (item < v[loc])
last = loc + 1;
else if (item > v[loc])
first = loc + 1;
else
/* item == v[loc] */ found = true;
}
}
Sorted
vector
5
Binary Search
• Usually outperforms a linear search
• Disadvantage:
- Only appropriate for direct access structures like
vectors - not linked lists (Why?)
• It is possible to use a linked structure which
can be searched in a binary-like manner
6
Binary Search Tree
•
Consider the following ordered list of integers
13
28
35
49
62
66
80
1. Examine middle element
2. Examine left, right sublist (maintain pointers)
3. (Recursively) examine left, right sublists
7
Binary Search Tree
• Redraw the previous structure so that it has
a treelike shape – a binary tree
8
Trees
• A data structure which consists of
– a finite set of elements called nodes or vertices
– a finite set of directed arcs which connect the
nodes
• If the tree is nonempty
– one of the nodes (the root) has no incoming arc
– every other node can be reached by following a
unique sequence of consecutive arcs
9
Trees
• Tree terminology
Root node
Interior nodes
• Children of the parent (3)
Leaf nodes
• Siblings to each other
10
Trees
• More Tree Terms
• The depth of a node n is the length of the path from
the root to the node.
• The height of a tree is the depth of its furthest leaf.
•Siblings are nodes that share the same parent node.
• If a path exists from node p to node q, where node
p is closer to the root node than q, then p is an
ancestor of q and q is a descendant of p.
• The size of a node is the number of descendants it
has including itself.
• In-degree of a vertex is the number of edges
arriving at that vertex.
• Out-degree of a vertex is the number of edges
leaving that vertex.
Each node in tree
is the root of a
Subtree
Recursive?
11
Tree Levels
Level: 0
A
B
C
E
G
D
F
H
Level: 1
Level: 2
Level: 3
12
Binary Trees
• Each node has at most two children
• Useful in modeling processes where
– a comparison or experiment has exactly two possible
outcomes
– the test is performed repeatedly
• Examples
– multiple coin tosses
– Expert systems (yes/no questions)
– encoding/decoding messages in dots and dashes such
as Morse code
– Expression tree (compiler generates)
13
Binary Trees
A binary tree T is a finite set of nodes with
one of the following properties:
1. T is a tree if the set of nodes is empty.
(An empty tree is a tree.)
2. The set consists of a root, R, and exactly
two distinct binary trees, the left subtree TL
and the right subtree TR. The nodes in T
consist of node R and all the nodes in TL
and TR.
14
Binary Trees
A
B
D
E
Right Subtree
G
H
Left Subtree
15
Binary Trees
A
A
B
C
D
H
E
I
B
D
G
F
C
E
J
Complete Tree (Depth 2)
Full with all possible nodes
Complete Tree (Depth 3)
A
A
B
B
C
D
D
I
Non-Complete Tree (Depth 3)
Level 2 is missing nodes
C
E
E
H
H
G
F
I
F
G
K
Non-CompleteTree (Depth 3)
Nodes at level 3 do not occupy leftmost positions
16
Tree Density
A
B
Total nodes (for top levels)
2d - 1
23-1 = 7
Additional Nodes
3
C
D
H
E
I
G
F
J
A
A
B
B
C
D
D
C
E
F
G
If totally complete tree: 2d - 1 + 2d
complete tree: 2d - 1 + 1 = 2d
17
Tree Density
A
A
B
B
D
C
C
E
F
G
If totally complete tree: 2d - 1 + 2d
D
complete tree: 2d - 1 + 1 = 2d
N nodes of complete tree satisfy inequality
2d <= n <= 2d+1 - 1 < 2d+1
d <= log2 n < d+1
Height (depth) of n node tree: int (log2 n)
18
Array Representation of Binary Trees
• Store the ith node in the ith location of the
array
19
Array Representation of Binary Trees
• Works OK for complete trees, not for sparse
trees
20
Linked Representation of Binary Trees
• Pros:
– Uses space more efficiently
– Provides additional flexibility
• Con: more overhead
• Each node has two links
– one to the left child of the node
– one to the right child of the node
– if no child node exists for a node, the link is set to
NULL
21
Linked Representation of Binary Trees
• Example
22
Binary Trees as Recursive Data Structures
• A binary tree is either empty …
or
• Consists of
– a node called the root
– root has pointers to two
disjoint binary (sub)trees called …
• right (sub)tree
• left (sub)tree
Anchor
Inductive
step
Which is either empty …
or …
Which is either empty …
or …
23
Tree Traversal is Recursive
If the binary tree is empty then
do nothing
Else
N: Visit the root, process data
L: Traverse the left subtree
R: Traverse the right subtree
The "anchor"
The inductive step
24
Traversal Order
Three possibilities for inductive step:
• Left subtree, Node, Right subtree
the inorder traversal
• Node, Left subtree, Right subtree
the preorder traversal
• Left subtree, Right subtree, Node
the postorder traversal
25
Traversal Order
• Given expression
A – B * C + D
• Represent each operand as
– The child of a
parent node
• Parent node,
representing
the corresponding
operator
26
Traversal Order
• Inorder traversal produces infix
expression
A – B * C + D
• Preorder traversal produces
the prefix expression
+ - A * B C D
• Postorder traversal produces
the postfix or RPN expression
A B C * - D +
27
Traversal Order
• Iterative Level-Order Scan
Visit
Visit
Visit
Visit
+
A
B
D
*
C
How is this possible?
28
Traversal Order
• Iterative Level-Order Scan
Visit
Visit
Visit
Visit
+
A
B
D
*
C
How is this possible?
Use a queue as the intermediate storage device
29
Traversal Order
• Iterative Level-Order Scan
Visit
Visit
Visit
Visit
+
A
B
Initialization Step:
node<T> *root;
queue<node<T> *> q;
q.push(root);
D
*
C
Iterative Step:
1. Get node N pointer from Q (if Q empty exit)
2. Delete a node N pointer from Q
3. Visit the node N
4. Push node N’s children onto Q
5. Go to step 1
30
Binary Search Tree (BST)
• Collection of Data Elements
– binary tree
– each node x,
• value in left child of x
• Basic operations

value in x

in right child of x
– Construct an empty BST
– Determine if BST is empty
– Search BST for given item
31
Binary Search Tree (BST)
• Basic operations (continued)
– Insert a new item in the BST
• Maintain the BST property
– Delete an item from the BST
• Maintain the BST property
– Traverse the BST
• Visit each node exactly once
• The inorder traversal must visit the values in the
nodes in ascending order
32
template <class elemType>
class BST
{
private:
template<class T>
struct nodeType
{
T
info;
nodeType<T> *llink;
nodeType<T> *rlink;
};
public:
bool isEmpty();
void inorderTraversal();
void preorderTraversal();
...
binaryTreeType(const binaryTreeType<elemType>& otherTree);
binaryTreeType();
~binaryTreeType();
33
private:
nodeType<elemType> *root;
void copyTree(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* otherTreeRoot);
...
void destroy(nodeType<elemType>* &p);
void inorder(nodeType<elemType> *p);
void preorder(nodeType<elemType> *p);
};
34
BST Traversals
Public method
void inorderTraversal();
Private recursive auxillary method
template<class elemType>
void binaryTreeType<elemType>::inorder(nodeType<elemType> *p)
{
if(p != NULL)
{
inorder(p->llink);
cout<<p->info<<" ";
inorder(p->rlink);
}
}
35
BST Leaf Count
Create a method that returns leaf count…
36
BST Leaf Count
int binaryTreeType<elemType>::treeLeavesCount()
{
return leavesCount(root);
}
template<class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p)
{
if (p != NULL)
{
if (p->llink == NULL && p->rlink == NULL)
return 1;
else
return (leavesCount(p->llink) +
leavesCount(p->rlink));
} else
return 0;
}
37
BST Searches
• Search begins at root
– If that is desired item, done
• If item is less, move down
left subtree
• If item searched for is greater, move down right
subtree
• If item is not found, we
will run into an empty subtree
38
BST Searches
• Search begins at root
– If that is desired item, done
• If item is less, move down
left subtree
• If item
searched for is greater, move down right
Remember: N nodes of complete tree satisfy inequality
subtree 2d <= n <= 2d+1 - 1 < 2d+1
d <=
log2 n < d+1
d is levels
• If item is not
found,
we
will run
into
subtree
Height
of n an
nodeempty
tree: int (log
2 n)
Max compares for complete tree: (int) log2 n + 1
39
Iterative Inserting into a BST
• Insert function – Letter R
– Uses modified version of search
to locate insertion location or
already existing item
R
– Pointer parent trails search
pointer locptr, keeps track of
parent node
– Thus new node can be attached
to BST in proper place
40
(Recursive) Inserting into a BST
• Insert function
– Base case
• Root pointer = null (empty)
30
– Create new node and return
pointer to this new tree
15
10
70
– Recursive case
• If root pointer != null (not empty)
– Compare new item to root’s item
– If item > root item then insert into
right subtree (insert root->rllink)
– If item < root item then insert into
left subtree
– If item = root item then don’t insert
41
(Recursive) Inserting into a BST
30
15
70
10
42
Recursive Deletion
Three possible cases to delete a node, x, from
a BST
1. The node,
x, is a leaf
43
Recursive Deletion
2. The node, x has one child
44
Recursive Deletion
• x has two children
Delete node pointed to by
xSucc as described for
cases 1 and 2
Replace contents of x with
inorder successor
K
45
Problem of Lopsidedness
• Tree can be balanced
– each node except leaves has exactly 2 child
nodes
46
Problem of Lopsidedness
• Trees can be unbalanced
– not all nodes have exactly 2 child nodes
47
Problem of Lopsidedness
• Trees can be totally lopsided
– Suppose each node has a right child only
– Degenerates into a linked list
Processing time
affected by
"shape" of tree
48
Threaded Binary Search Trees
• Use special links in a BST
– These threads provide efficient nonrecursive
traversal algorithms
– Build a run-time stack into the tree for recursive
calls
49
Threaded Binary Search Trees
• Note the sequence
of nodes visited
– Left to right
• A right threaded BST
– Whenever a node, x, with null right pointer is
encountered, replace right link with thread to inorder
successor of x
– Inorder successor of x is its parent if x is a left child
– Otherwise it is nearest ancestor of x that contains x in its
left subtree
50
Threaded Binary Search Trees
Traversal algorithm
1. Initialize a pointer, ptr, to the root of tree
2. While ptr != null
a. While ptr->left not null
replace ptr by ptr->left
b. Visit node pointed to by ptr
c. While ptr->right is a thread do following
i. Replace ptr by ptr->right
ii. Visit node pointed to by ptr
d. Replace ptr by ptr->right
End while
51
Threaded Binary Search Trees
public:
Additional field,
DataType data;
rightThread
bool rightThread;
required
BinNode * left;
BinNode * right;
// BinNode constructors
// Default -- data part is default DataType value
//
-- right thread is false; both links are null
BinNode()
: rightThread(false, left(0), right(0) { }
//Explicit Value -- data part contains item; rightThread
//
-- is false; both links are null
BinNode (DataType item)
: data(item), rightThread(false), left(0), right(0) { }
}; // end of class BinNode declared
52