Transcript Binary Trees

Binary Trees
Chapter 10
Introduction
• Previous chapter considered linked lists
– nodes connected by two or more links
• We seek to organize data in a linked
structure such that
– it can be searched more efficiently
– it can be used in new ways
• We begin with a review of search algorithms
Linear Search
• Collection of data items to be searched is
organized in a list
x 1, x 2, … x n
– 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
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++; }
}
Linear Search
Singly-linked list based search function
template <typename t>
void LinearSearch (NodePointer first,
const t &item,
boolean &found, NodePointer &locptr)
{ found = false; locptr = first;
for ( ; ; )
{
if (found || locptr == 0 ) return;
if (item == locptr->data)
found = true;
else
In both cases, the
locptr = locptr->next; } worst case computing
}
time is still O(n)
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;
}
}
Binary Search
• Usually outperforms a linear search
• Disadvantage:
– Requires a sequential storage
– Not appropriate for linked lists (Why?)
• It is possible to use a linked structure
which can be searched in a binary-like
manner
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
Binary Search Tree
• Redraw the previous structure so that it
has a treelike shape – a binary tree
49
66
28
13
35
62
80
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
Trees
Root node
49
66
28
35
13
Leaf nodes
62
70
80
• Children of the parent (66)
• Siblings to each other
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
• Example
– multiple coin tosses
– encoding/decoding messages in dots and
dashes such as Mores code
Array Representation of Binary Trees
0
3
C
M
2
O
1
4
E
5
P
T
6
U
• Store the ith node in the ith location of the
array
• Works OK for complete trees, not for
sparse trees
Linked Representation of Binary Trees
• Uses space more efficiently
• Provides additional flexibility
• Each node has two links
data
left
right
– one to the left child of the node
right
left
child
child
– one to the right child of the node
– if no child node exists for a node, the link is
set to NULL
ADT Binary Search Tree (BST)
• Collection of Data Elements
– binary tree
– each node x,
• value in left child of x  value in x  in right child of x
• Basic operations
– Construct an empty BST
– Determine if BST is empty
– Search BST for given item
ADT Binary Search Tree (BST)
• Basic operations (ctd)
– 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
BST Class Template
template <typename t>
class BST
{ private:
/* Node structure */
class BinNode
{ public:
t data;
BinNode *left, *right;
BinNode() { left = right = 0; }
BinNode (t item)
{ data = item; left = right = 0; }
}; // end of class BinNode
//
ctd ->
BST Class Template
. . .
typedef BinNode *BinNodePointer;
public: // for BST
BST(); // construct an empty BST
bool Empty() const;
private:
BinNodePointer root;
}; // end of class template declaration
BST Class Template
• Definition of constructor
template <typename t>
BST <t>::BST()
{ root = 0; }
• Definition of Empty()
template <typename t>
bool BST<t>::Empty()
{ return root == 0; }
Searching a BST
template <typename t>
bool BST <t>::Search(const t &item) const
{ BinNodePointer locptr = root;
Reached a leaf node
bool found = false;
without finding a match
for ( ; ; )
{ if found || locptr == 0) break;
if (item < locptr->data)
locptr = locptr->left;
// descend left
else if (item > locptr->data)
locptr = locptr->right;
// descend right
else found = true;
}
return found;
}
Inserting an Item into a BST
template <typename t>
void BST<t>::Insert (const t &item)
{ BinNodePointer locptr = root; parent
bool found = false;
for ( ; ; )
{ if found || locptr == 0) break;
parent = locptr;
if (item < locptr->data)
locptr = locptr->left;
//
else if (item > locptr->data)
locptr = locptr->right;
//
else found = true;
}
if (found) cerr << "Item already in
. . .
=0;
descend left
descend right
the tree\n";
Inserting an Item into a BST
else
{ locptr = new BinNode (item);
// construct node containing item
if (parent == 0) // empty tree
root = locptr;
else if (item < parent->data)
// insert left of parent
parent->left = locptr
else // insert right of parent
parent->right = locptr;
} // end of the else
} end of the Insert
Problem of Lopsidedness
• Tree can be balanced
– each node except leaves has exactly 2 child
nodes
• Trees can be unbalanced
– not all nodes have exactly 2 child nodes
• Trees can be totally lopsided
– each node has a right child only
– degenerates into a linked list
Problem of Lopsidedness
• Balanced tree search has O(log2n)
– best case
• Tree degenerated into linked list has search
O(n)
– worst case
• Other unbalanced trees somewhere in between
• In general
– Not possible to predict how to insert to create
balanced tree
– May require rebalancing algorithm
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 Which is either empty …
or …
Which is either empty …
or …
Anchor
Inductive
step
Tree Traversal is Recursive
If the binary tree is empty then
do nothing
Else
L: Traverse the left subtree
N: Visit the root
R: Traverse the right subtree
The "anchor"
The inductive step
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
Traversal Order
• Given expression
A – B * C + D
• Represent each operand as
– the child of a parent node
– representing the corresponding operator
+
D
*
A
B
C
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 +
Traversing a Binary Tree
Two functions needed:
• We can send a message
to a BST object … but …
template <typename t>
void BST<t>::Inorder(ostream &out)
{ InorderAux (out, root); }
• Cannot send a message
to its root, required by
recursion
•Inorder sends message
to the root
template <typename t>
void BST<t>::InorderAux (ostream& out,
BinNodePointer ptr)
{
if (ptr != 0)
{
InorderAux (opt, ptr->left);
out << ptr-> data << " ";
InorderAux(out, ptr->right);
}
}
Change order of
these three
statements for
different traversals
Recursive Searching
template <typename t>
bool BST<t>::Search (const t &item)
{ return SearchAux (root, item); }
template <typename t>
bool BST<t>::SearchAux (BinNodePointer locptr,
const t &item)
{ if (locptr == 0) return false; // empty tree
if (item < locptr->data)
Author suggests
return SearchAux(locptr->left, item);
iterative approach is
else if (item > locptr->data)
easier, just as efficient
return SearchAux (locptr->right, item);
else
return true;
}
Recursive Insertion
template <typename t>
void
BST<t>::Insert (const t &item)
{ InsertAux (root, item); }
template (typename t>
void BST<t>::InsertAux (BinNodePointer &locptr,
const t &item)
{ if (locptr == 0) locptr = new BSTNode (item);
else if (item < locptr->data)
InsertAux (locptr->left, item);
else if (item > locptr->data)
InsertAux (locptr->right, item);
else cerr << "Item already in tree\n";
}
Deletion
Three possible cases to delete a node, x,
from a BST
• The node, x, is a leaf
• x has one child
• x has two children
• Note the source code for the deletion
function, pgs 548 - 550
Deletion
• What steps must be
done to remove a
leaf node?
class BST
{ private:
/* Node structure */
class BinNode
{ public:
t data;
BinNode *left, *right;
BinNode() { left = right = 0; }
BinNode (t item)
{ data = item; left = right = 0; }
}; // end of class BinNode
...
←x
Deletion
• What steps must be
done to remove a
node with 1 child?
class BST
{ private:
/* Node structure */
class BinNode
{ public:
t data;
BinNode *left, *right;
BinNode() { left = right = 0; }
BinNode (t item)
{ data = item; left = right = 0; }
}; // end of class BinNode
...
x→
Deletion
• What steps must be
done to remove a
node with 2 children?
class BST
{ private:
/* Node structure */
class BinNode
{ public:
t data;
BinNode *left, *right;
BinNode() { left = right = 0; }
BinNode (t item)
{ data = item; left = right = 0; }
}; // end of class BinNode
...
x→
Strategy: Replace with its inorder
successor or predecessor
• Successor – right child, descend left
• Predecessor – left child, descend right