Transcript Binary Search Trees

Binary Search Trees
CS3240
Goals
• Define and use the following terminology:
binary tree
root
descendant
subtree
binary search tree
parent
level
ancestor child
height
• Define a binary search tree at the logical level
• Show what a binary search tree would look
like after a series of insertions and deletions
2
Goals
• Implement the following binary search tree
algorithms in C++
Inserting an element
Deleting an element
Retrieving an element
Modifying an element
Copying a tree
Traversing a tree in preorder, inorder,
postorder
3
Goals
• Discuss the Big-O efficiency of a given
binary search tree operation
• Describe an algorithm for balancing a binary
search tree
• Show how a binary tree can be represented
in an array, with implicit positional links
between the elements
• Define the terms full binary tree and
complete binary tree
4
Trees
Owner
Jake
Manager
Brad
Waitress
Joyce
Chef
Carol
Waiter
Chris
Jake’s Pizza Shop
5
Cook
Max
Helper
Len
Trees
ROOT NODE
Owner
Jake
Manager
Brad
Waitress
Joyce
6
Chef
Carol
Waiter
Chris
Cook
Max
Helper
Len
Trees
Owner
Jake
Manager
Brad
Waitress
Joyce
LEAF NODES
7
Chef
Carol
Waiter
Chris
Cook
Max
Helper
Len
Trees
Owner
Jake
LEVEL 0
Manager
Brad
Waitress
Joyce
8
Chef
Carol
Waiter
Chris
Cook
Max
Helper
Len
Trees
Owner
Jake
Manager
Brad
LEVEL 1
Waitress
Joyce
9
Chef
Carol
Waiter
Chris
Cook
Max
Helper
Len
Trees
Owner
Jake
Manager
Brad
Chef
Carol
LEVEL 2
Waitress
Joyce
10
Waiter
Chris
Cook
Max
Helper
Len
Trees
Owner
Jake
Manager
Brad
Waitress
Joyce
Chef
Carol
Waiter
Chris
LEFT SUBTREE OF ROOT NODE
11
Cook
Max
Helper
Len
Trees
Owner
Jake
Manager
Brad
Waitress
Joyce
12
Chef
Carol
Waiter
Chris
Cook
Max
Helper
Len
RIGHT SUBTREE
OF ROOT NODE
Trees
A structure with a unique starting node (the
root), in which each node is capable of having
zero or more child nodes and a unique path
exists from the root to every other node
Root
The top node of a tree structure; a node with no
parent
Leaf Node
A tree node that has no children
13
Trees can be used…
Trees are data
structures that
can be used for
many different
applications
• Representing
decisions and
logic
• Partitioning of
keys/data in
database/file
systems
14
Trees
• used to store generic data
• possibly improve on generic insertion, removal
and search operations….
• ……Binary Search Tree….
• first, what is a Binary Tree
15
Binary Trees
Binary Tree
A structure with a unique starting node (the
root), in which each node is capable of having
two child nodes and a unique path exists
from the root to every other node
• used to store generic data
• possibly improve on generic insertion, removal
and search operations….
• ……Binary Search Tree….
• first, what is a Binary Tree
16
Trees—some terms
Level
Distance of
a node from
the root
Height
The
maximum
level
17
Trees
Why is
this
not a
tree
?
18
Trees
How many
leaf nodes?
V
Q
L
T
E
K
19
A
S
Trees
Q has how many
descendant?
V
Q
T
E
K
20
L
A
S
Trees
S has how many
ancestors?
V
Q
T
E
K
21
L
A
S
Trees
How many different binary trees can be made
from 2 nodes? 4 nodes? 6 nodes?
22
Answers…you investigate
See…
http://mathworld.wolfram.com/BinaryTree.html
23
Motivation for the Tree
Motivation
How can we implement a table?
•need insert, delete and search operations
A1) Sorted Array
Binary search is fast O(log(N))
Delete and Insert require O(N) steps
A2) Linked List
Search is slow O(N)
Insert and delete are fast, once we find the right spot
Goal
Is there a datastructure to support O(log(N)) search, insert and delete operations?
Problem with Linked List: in search only one path to take.....
what if we had more than one path (link)
Solution: Tree???
Best Case: Fast
Worst Case: Like a Linked List
Better Solution: Constrained Trees (e.g. Binary
Tree)  try the Binary Search Tree
24
Binary Search Trees
Binary Search Trees
A binary tree in which the
• key value in any node is greater than
the key value in the left child and any
of its children and less than the key
value in the right child and any of its
children
A BST is a binary tree with the search
property
25
Binary Search Trees
Each
node is
the
root of a
subtree
26
Recursive Implementation
27
Recursive Count
Let’s start by counting the number of nodes in
a tree
Size?
Base cases(s)?
General case(s)?
28
Recursive Count
Count (Version 1)
if (Left(tree) is NULL) AND (Right(tree) is NULL)
return 1
else
return Count (Left(tree)) + Count(Right(tree)) + 1
Apply to
these trees
29
Recursive Count
Count (Version 2)
if (left(tree) is NULL) AND (Right(tree) is NULL)
return 1
else if (Left(tree) is NULL)
return Count(Right(tree)) + 1
else if (Right(tree) is NULL)
return Count(Left(tree)) + 1
else return Count(Left(tree)) + Count(Right(tree)) + 1
Apply to an empty tree
30
Recursive Count
Count (Version 3)
if (tree is !NULL)
// Version 2
Stop
Count (Version 4)
if (tree is NULL)
return 0
else
return Count(Left(tree)) + Count(Right(tree)) + 1
31
Recursive Count
int TreeType() const
{
return Count(root);
)
int Count(TreeNode* tree)
{
if (tree == NULL)
return 0
else
return Count(tree->left) +
Count(tree->right) + 1;
}
Why do we need two functions?
32
Recursive Search
‘J’
‘T’
‘E’
‘A’
‘D’
‘B’
‘Z’
‘P’
‘K’
‘L’
Are ‘D’, ‘Q’, and ‘N’ in the tree?
33
‘V’
‘M’
‘H’
‘Q’
‘S’
Recursive Search
Retrieve(tree, item, found)
Size?
Base case(s)?
General case(s)?
34
Recursive Search
35
void Retrieve(TreeNode* tree,
ItemType& item,
bool& found)
{
if (tree == NULL)
found = false;
else if (item < tree->info)
Retrieve(tree->left, item, found);
else if (item > tree->info)
Retrieve(tree->right, item, found);
else
{
item = tree->info;
found = true;
}
}
Shape of BST
Shape depends on the order of item insertion
Insert the elements ‘J’ ‘E’ ‘F’ ‘T’ ‘A’
order
in that
The first value inserted is always put in the root
‘J’
36
Shape of BST
Thereafter, each value to be inserted
compares itself to the value in the root node
moves left it is less or
moves right if it is greater
When does the process stop?
‘J’
‘E’
37
Shape of BST
Trace path to insert ‘F’
‘J’
‘E’
‘F’
38
Shape of BST
Trace path to insert ‘T’
‘J’
‘T’
‘E’
‘F’
39
Shape of BST
Trace path to insert ‘A’
‘J’
‘T’
‘E’
‘A’
40
‘F’
Shape of BST
Now build tree by inserting ‘A’ ‘E’ ‘F’ ‘J’ ‘T’
in that order
And the moral is?
41
Recursive Insertion
Insert an item into a tree
Where does each new node get inserted?
Insert(tree, item)
if (tree is NULL)
Get a new node
Set right and left to NULL
Set info to item
42
Recursive Insertion
43
Recursive Insertion –insert 11
44
Recursive Insertion
11
45
How must
the tree
be
passed?
Recursive Insertion
void Insert(TreeNode*& tree, ItemType item)
{
if (tree == NULL)
{// Insertion place found.
tree = new TreeNode;
tree->right = NULL;
tree->left = NULL;
tree->info = item;
}
else if (item < tree->info)
Insert(tree->left, item);
else
Insert(tree->right, item);
}
46
Recursive Deletion
Delete ‘Z’
47
Recursive Deletion
Delete ‘R’
48
Recursive Deletion
Delete ‘Q’
49
Recursive Deletion
Can you summarize the three
deletion cases?
50
Recursive Deletion
DeleteItem(tree, item)
…first assume tree is node containing item
if (Left(tree) is NULL) AND (Right(tree) is NULL)
Set tree to NULL
else if Left(tree) is NULL
Set tree to Right(tree)
else if Right(tree) is NULL
Set tree to Left(tree)
else
Find predecessor
Set Info(tree) to Info(predecessor)
Delete predecessor
51
Recursive Deletion
void Delete(TreeNode*& tree, ItemType item)
{
if (item < tree->info)
Delete(tree->left, item);
else if (item > tree->info)
Delete(tree->right, item);
else
DeleteNode(tree); // Node found
}
52
Recursive Deletion
53
void DeleteNode(TreeNode*& tree)
{
ItemType data;
TreeNode* tempPtr;
tempPtr = tree;
if (tree->left == NULL) {
tree = tree->right;
delete tempPtr; }
else if (tree->right == NULL){
tree = tree->left;
delete tempPtr;}
else{
GetPredecessor(tree->left, data);
tree->info = data;
Delete(tree->left, data);}
}
Recursive Deletion
void GetPredecessor(TreeNode* tree,
ItemType& data)
{
while (tree->right != NULL)
tree = tree->right;
data = tree->info;
}
Why is the code not recursive?
---simple to find predecessor---it is the right
most node of the left subtree that was
54
passed as a parameter
Recursive Deletion
55
Printing the Tree
Apply same algorithm to each tree
56
What is the order of the output?
Least to greatest
A,D,J,M,Q,R,T
Printing the Tree
PrintTree operation
Size?
Base case(s)?
General case(s)?
57
Printing the Tree
void PrintTree(TreeNode* tree,
std::ofstream& outFile)
{
if (tree != NULL)
{
PrintTree(tree->left,
outFile);
outFile << tree->info;
PrintTree(tree->right,
outFile);
}
}
58
Is
that
all
there
is
?
A Question
Do we need a destructor?
Yes to avoid memory leaks
59
Copying a Tree
CopyTree(copy, originalTree)
if (originalTree is NULL)
Set copy to NULL
else
Set copy to new node
Set Info(copy) to Info(originalTree)
CopyTree(Left(copy), Left(originalTree))
CopyTree(Right(copy), Right(originalTree))
How must copy be passed?
How must originalTree be passed?
60
Copying a Tree
void CopyTree(TreeNode*& copy,
const TreeNode* originalTree)
{
if (originalTree == NULL)
copy = NULL;
else
{
copy = new TreeNode;
copy->info = originalTree->info;
CopyTree(copy->left, originalTree->left);
CopyTree(copy->right, originalTree->right);
}
}
61
Traversals
Inorder(tree)
if tree is not NULL
Inorder(Left(tree))
Visit Info(tree)
Inorder(Right(tree))
PostOrder(tree)
if tree is not NULL
Postorder(Left(tree))
Postorder(Right(tree))
Visit Info(tree)
62
PreOrder(tree)
if tree is not NULL
Visit Info(tree)
Preorder(Left(tree))
Preorder(Right(tree))
Traversals
Each node
is visited
three times
63
Traversals
64
Iterator
Approach

The client program passes a parameter to ResetTree
and GetNextItem indicating which of the three
traversals to use

ResetTree generates a queue of node contents in the
indicated order

GetNextItem processes the node contents from the
appropriate queue: inQue, preQue, postQue
65
Iterator
void TreeType::ResetTree(OrderType order)
// Calls function to create a queue of the
tree
// elements in the desired order.
{
switch (order)
{
case PRE_ORDER : PreOrder(root, preQue);
break;
case IN_ORDER
: InOrder(root, inQue);
break;
case POST_ORDER: PostOrder(root, postQue);
break;
}
}
66
Iterator
67
void TreeType::GetNextItem(ItemType& item,
OrderType order,bool& finished)
{
finished = false;
switch (order)
{
case PRE_ORDER : preQue.Dequeue(item);
if (preQue.IsEmpty())
finished = true;
break;
case IN_ORDER
: inQue.Dequeue(item);
if (inQue.IsEmpty())
finished = true;
break;
case POST_ORDER: postQue.Dequeue(item);
if (postQue.IsEmpty())
finished = true;
break;
}
}
Iterative Versions
FindNode(tree, item, nodePtr, parentPtr)
Set nodePtr to tree
Set parentPtr to NULL
Set found to false
while more elements to search AND NOT found
if item < Info(nodePtr)
Set parentPtr to nodePtr
Set nodePtr to Left(nodePtr)
else if item > Info(nodePtr)
Set parentPtr to nodePtr
Set nodePtr to Right(nodePtr)
else
Set found to true
68
Iterative Versions
InsertItem
Create a node to contain the new item
Find the insertion place
Attach new node
Find the insertion place
FindNode(tree, item, nodePtr, parentPtr);
69
Iterative Versions
Insert 13
70
Iterative Versions
71
Iterative Versions
AttachNewNode
if item < Info(parentPtr)
Set Left(parentPtr) to newNode
else
Set Right(parentPtr) to newNode
72
See a
problem
?
What if tree empty
and parentPtr Null
Iterative Version
AttachNewNode(revised)
if parentPtr equals NULL
Set tree to newNode
else if item < Info(parentPtr)
Set Left(parentPtr) to newNode
else
Set Right(parentPtr) to newNode
73
Iterative Version
void TreeType::DeleteItem(ItemType
item)
{
TreeNode* nodePtr;
TreeNode* parentPtr;
FindNode(root, item, nodePtr,
parentPtr);
if (nodePtr == root)
DeleteNode(root);
else
if (parentPtr->left == nodePtr)
DeleteNode(parentPtr->left);
else DeleteNode(parentPtr->right);
}
74
Why not
parentPtr?
Why not
nodePtr?
Iterative Version
parentPtr and nodePtr are external; parentPtr->left is internal
75
Recursion VS Iteration
Compare versions of Tree algorithms
Is the depth of recursion relatively shallow?
Is the recursive solution shorter or cleaner?
Is the recursive version much less efficient?
76
Nonlinked Representation
What is the mapping into the index?
77
Nonlinked Representation
For any node tree.nodes[index]
its left child is in tree.nodes[index*2 + 1]
right child is in tree.nodes[index*2 + 2]
its parent is in tree.nodes[(index - 1)/2]
Can you determine which nodes are leaf nodes?
ANSWER: any index where left and right contain nothing
(represent say with the value -1 or some other unique
number)
78
Nonlinked Representation
Full Binary Tree
A binary tree in which all of the leaves are
on the same level and every nonleaf node
has two children
79
Nonlinked Representation
Complete Binary Tree
A binary tree that is either full or full
through the next-to-last level, with the
leaves on the last level as far to the left as
possible
80
Nonlinked Representation
81
Nonlinked Representation
A
technique
for storing
a noncomplete
tree
82