Transcript Elementary Data Structures: Binary Search Trees

Analysis & Design of
Algorithms
(CSCE 321)
Prof. Amr Goneid
Department of Computer Science, AUC
Part R2. Binary Search Trees
Prof. Amr Goneid, AUC
1
Dictionaries(2): Binary Search
Trees







Binary Trees
Tree Traversal
The Binary Search Tree (BST)
Deleting Nodes from a BST
Binary Search Tree ADT
Template Class Specification
Other Search Trees
Prof. Amr Goneid, AUC
2
1. Binary Trees
 A Tree is a non-linear, hierarchical one-to-
many data structure. Examples:
Binary Trees, Binary Search Trees (BST)
 Can be implemented using arrays, structs
and pointers
 Used in problems dealing with:




Searching
Hierarchy
Ancestor/descendant relationship
Classification
Prof. Amr Goneid, AUC
3
Tree Terminology
 A tree consists of a finite set of nodes (or vertices)
and a finite set of edges that connect pairs of nodes.
 A node is a container for data
 An edge represents a relationship between two
nodes.
a node
a
a
an edge
b
Prof. Amr Goneid, AUC
4
Tree Terminology
 A non-empty tree has a root node (e.g.node a). Every other
node can be reached from the root via a unique path
(e.g. a-d-f). a is the parent of nodes b and c because there is
an edge going from a down to each. Moreover, b and c are
root
children of a.
a
child of a
b
c
d
e
f
parent of g
Prof. Amr Goneid, AUC
g
5
Tree Terminology
a
b
c
d
Siblings
e

The descendants of a are (b, c, d, and e), nodes that can be
reached by paths from a.
 The ancestors of e are (c and a), nodes found on the path from e
to a.
 Nodes (b, d, and e) are leaf nodes (they have no children).
 Each of the nodes a and c has at least one child and is an
internal node.
Prof. Amr Goneid, AUC
6
Tree Terminology
a
b
d
c
e
f
g
 Each node in the tree (except leaves) may have one or
more subtrees
 For a tree with n nodes there are n-1 edges
Prof. Amr Goneid, AUC
7
The Binary Tree
Level 1
a
A binary tree of height h = 3
Left
Level 2
Level 3
Right
b
d
c
e
f

A binary tree is a tree in which a parent has at most two
children. It consists of a root and two disjoint subtrees (left and
right).
 The root is at level (L = 1) and the height h = maximum level
 The maximum number of nodes in level L is 2L-1
Prof. Amr Goneid, AUC
8
The Full Binary Tree
a
b
d
c
e
f
g
 A binary tree is full iff the number of
nodes in level L is 2L-1
Prof. Amr Goneid, AUC
9
The Full Binary Tree
 A full binary tree of height h has n
nodes, where
n  1  2  4  ... 2
h
n  2
L 1
h 1
 2 1
h
L 1
Henceh  log2 ( n  1 )
Prof. Amr Goneid, AUC
10
The Full Binary Tree
A full binary tree with nint internal
nodes has external nodes :
next  nint  1
Since next  nh  2h1 then nint  2h1  1
The total number of branches
to internal nodes is :
nint Branches  nint  1  2h1  2
Prof. Amr Goneid, AUC
11
The Full Binary Tree
 The cost of search for nodes in level L is L 2L-1
 Hence, the total search cost is
h
c   L 2 L1  ( h  1 )2 h  1
L 1
hence,the averagesearch cost is
( h  1 )2 h 1
T( n )  c / n 

h
2 1
n
For large n, T ( n )  h  1  O( log2 n )
Prof. Amr Goneid, AUC
12
The Balanced Tree
hL
hR
 A balanced binary tree has the property that the heights
of the left and right subtrees differ at most by one level.
 i.e. |hL – hR| ≤ 1
 A Full tree is also a balanced tree
Prof. Amr Goneid, AUC
13
Complete Binary Tree


A binary tree is Complete iff the number of Nodes at level 1 <=
L <= h-1 is 2L-1 and leaf nodes at level h occupy the leftmost
positions in the tree
i.e. all levels are filled except the rightmost of the last level.
Missing Leaves
Missing Leaves
Prof. Amr Goneid, AUC
14
Complete Binary Tree
1
A B C D E
A
2
3
B
C
4
D
E
5
A complete binary tree can be efficiently
implemented as an array, where a node at index i
has children at indexes 2i and 2i+1 and a parent
at index i/2 (with one-based indexing).
Prof. Amr Goneid, AUC
15
Binary Tree as a Recursive Structure



A binary tree is a recursive structure
e.g. it can be defined recursively as:
a
if (not empty tree)
1. It has a root
b
2. It has a (Left Subtree)
3. It has a (Right Subtree)
d
e
Recursive structure suggests recursive
processing of trees (e.g. Traversal)
Prof. Amr Goneid, AUC
c
f
16
Binary Tree as a Recursive Structure
Empty
a,b,c,d,e,f
a
d
b,d,e
c,f
b
c
f
e
Prof. Amr Goneid, AUC
17
2. Tree Traversal
 Traversal is to visit every node ( to display,
process, …) exactly once
 It can be done recursively
 There are 3 different binary tree traversal
orders:
 Pre-Order:
Root is visited before its two
subtrees
 In-Order:
Root is visited in between its
two subtrees
 Post-Order: Root is visited after its two
subtrees
Prof. Amr Goneid, AUC
18
Pre-Order Traversal
 Algorithm:
PreOrder ( tree )
{
if ( not empty tree)
2
{
b
Visit (root);
PreOrder (left subtree); 3 d
PreOrder (right subtree);
}
}
 The resulting visit order = {a} {b , d , e} {c , f }
Prof. Amr Goneid, AUC
1 a
5
c
4
e
f 6
19
Pre-Order Traversal
 Pre-Order Traversal is also called Depth-First traversal
1
2
3
5
4
6
Prof. Amr Goneid, AUC
7
20
In-Order Traversal
 Algorithm:
InOrder ( tree )
{
if ( not empty tree)
2
{
b
InOrder (left subtree);
1 d
Visit (root);
InOrder (right subtree);
}
}
 The resulting visit order = {d , b , e} {a} {f , c }
Prof. Amr Goneid, AUC
4 a
6
c
3
e
f 5
21
Post-Order Traversal
 Algorithm:
PostOrder ( tree )
{
if ( not empty tree)
3
{
b
PostOrder (left subtree);
PostOrder (right subtree);1 d
Visit (root);
}
}
 The resulting visit order = {d , e , b} {f , c } {a}
Prof. Amr Goneid, AUC
6 a
5
c
2
e
f 4
22
Example: Expression Tree
 The expression A – B * C + D can be represented as a
tree.
 In-Order traversal gives: A – B * C + D
This is the infix representation
 Pre-Order traversal gives: + - A * B C D
This is the prefix representation
 Post-Order traversal gives:
ABC*-D+
This is the postfix (RPN) representation
Prof. Amr Goneid, AUC
+
-
D
A
*
B
C
23
Binary Tree Traversal Demo
http://www.cosc.canterbury.ac.nz/people/
mukundan/dsal/BTree.html
Prof. Amr Goneid, AUC
24
3. Binary Search Trees
BST
Prof. Amr Goneid, AUC
25
3. The Binary Search Tree
(BST)
 A Binary Search Tree (BST) is a Dictionary
implemented as a Binary Tree. It is a form of
container that permits access by content.
 It supports the following main operations:
 Insert : Insert item in BST
 Remove : Delete item from BST
 Search : search for key in BST
Prof. Amr Goneid, AUC
26
BST
v
w
u
A BST is a binary tree that stores keys or key-data pairs in
its nodes and has the following properties:
 A key identifies uniquely the node (no duplicate keys)
 If (u , v , w) are nodes such that (u) is any node in the left
subtree of (v) and (w) is any node in the right subtree of
(v) then:
key(u) < key(v) < key(w)
Prof. Amr Goneid, AUC
27
Examples Of BST
Prof. Amr Goneid, AUC
28
Examples Of BST
These are NOT BSTs.
Prof. Amr Goneid, AUC
29
Searching Algorithm
if (tree is empty)
target is not in the tree
else if (the target key is the root)
target found in root
else if (target key smaller than the root’s key)
search left sub-tree
else
search right sub-tree
Prof. Amr Goneid, AUC
30
Searching for a key
Search for the node containing e:
Maximum number of comparisons is tree height, i.e. O(h)
Prof. Amr Goneid, AUC
31
BST Demo
http://www.cosc.canterbury.ac.nz/people/
mukundan/dsal/BST.html
Prof. Amr Goneid, AUC
32
Building a Binary Search Tree
 Tree created from root downward
 Item 1 stored in root
 Next item is attached to left tree if value
is smaller or right tree if value is larger
 To insert an item into an existing tree,
we must first locate the item’s parent
and then insert
Prof. Amr Goneid, AUC
33
Algorithm for Insertion
if (tree is empty)
insert new item as root
else if (root key matches item)
skip insertion (duplicate key)
else if (new key is smaller than root)
insert in left sub-tree
else insert in right sub-tree
Prof. Amr Goneid, AUC
34
Example: Building a Tree
Insert: 40,20,10,50,65,45,30
Prof. Amr Goneid, AUC
35
Effect of Insertion Order
 The shape of the tree depends on the order
of insertion. Shape determines the height (h)
of the tree.
 Since cost of search is O(h), the insertion
order will affect the search cost.
 The previous tree is full, and h = log2(n+1) so
that search cost is O(log2n)
Prof. Amr Goneid, AUC
36
Effect of Insertion Order
O(n)
O(log n)
 The previous tree would look like a linked list if we
have inserted in the order 10,20,30,…. Its height
would be h = n and its search cost would be O(n)
Prof. Amr Goneid, AUC
37
Binary Search Tree Demo
http://www.cosc.canterbury.ac.nz/people/
mukundan/dsal/BSTNew.html
Prof. Amr Goneid, AUC
38
Traversing a Binary Search Tree
Recursive inorder traversal of tree with root (t)
traverse ( t )
{
if (t is not empty)
traverse (tleft);
visit (t);
traverse (tright);
}
Prof. Amr Goneid, AUC
39
Find Minimum Key
Find the minimum key in a tree with root (t)
Minkey ( t )
{
if (tleft is not empty) return MinKey(tleft);
else return key(t);
}
Prof. Amr Goneid, AUC
40
Other Traversal Orders
 Pre-order (a.k.a. Depth-First traversal) can be implemented
using an iterative (non-recursive) algorithm. In this case, a
stack is used
 If the stack is replaced by a queue and left pointers are
exchanged by right pointers, the algorithm becomes Levelorder traversal (a.k.a. Breadth-First traversal)
Prof. Amr Goneid, AUC
41
Iterative Preorder Traversal
void iterative_preorder ( )
{
t = root;
Let s be a stack
s.push (t);
while(!s.stackIsEmpty())
{
s.pop(t); process(t->key);
if ( t right is not empty) s.push(t right);
if ( t left is not empty) s.push(t left);
}
}
Prof. Amr Goneid, AUC
42
Pre-Order Traversal
Traversal order: {D,B,A,C,F,E,G}
1
D
2
5
B
3
A
F
C 4
6
Prof. Amr Goneid, AUC
E
7
G
43
Level Order Traversal
void levelorder ( )
{
t = root;
Let q be a queue;
q.enqueue(t);
while(!q.queueIsEmpty())
{
q.dequeue(t); process(t->key);
if ( t left is not empty) q.enqueue(t left);
if ( t right is not empty) q.enqueue(t right);
}
}
Prof. Amr Goneid, AUC
44
Level-Order Traversal
Traversal order: {D,B,F,A,C,E,G}
1
D
2
3
B
F
4
A
C
5
6
7
E
Prof. Amr Goneid, AUC
G
45
4. Deleting Nodes from a BST
Prof. Amr Goneid, AUC
46
Deleting a ROOT Node
Prof. Amr Goneid, AUC
47
Deleting a ROOT Node
Prof. Amr Goneid, AUC
48
Deleting a ROOT Node (Special
Case)
Prof. Amr Goneid, AUC
49
Deleting a ROOT Node (Alternative)
Prof. Amr Goneid, AUC
50
Deleting an Internal Node
Prof. Amr Goneid, AUC
51
Search for Parent of a Node
To delete a node, we need to find its parent.
To search for the parent (p) of a node (x) with key (k)
in tree (t):
Set x = t; p = null; found = false;
While (not found) and (x is not empty)
{
if k < key(x) descend left (i.e. set p = x; x = xleft)
else
if k > key(x) descend right (i.e. set p = x;x = xright)
else found = true
}
Notice that:
P is null if (k) is in the root or if the tree is empty.
If (k) is not found, p points to what should have been
its parent.
Prof. Amr Goneid, AUC
52
Algorithm to remove a Node
Let
k = key to remove its node
t = pointer to root of tree
x = location where k is found
p = parent of a node
sx = inorder successor of x
s = child of x
Prof. Amr Goneid, AUC
53
Algorithm to remove a Node
Remove (t,k)
{
Search for (k) and its parent;
If not found, return;
else it is found at (x) with parent at (p):
Case (x) has two children:
Find inorder successor (sx) and its parent (p);
Copy contents of (sx) into (x);
Change (x) to point to (sx);
Now (x) has one or no children and (p) is its parent
Prof. Amr Goneid, AUC
54
Algorithm to remove a Node
Case (x) has one or no children:
Let (s) point to the child of (x) or null if there
are no children;
If p = null then set root to null;
else if (x) is a left child of (p), set pleft = s;
else set pright = s;
Now (x) is isolated and can be deleted
delete (x);
}
Prof. Amr Goneid, AUC
55
Example: Delete Root
p = null
40
x
20
10
60
30
50
Prof. Amr Goneid, AUC
70
56
Example: Delete Root
40
x
20
10
60
30
p
70
50
sx
Prof. Amr Goneid, AUC
57
Example: Delete Root
50
20
10
60
30
50
x
p
70
S = null
Prof. Amr Goneid, AUC
58
Example: Delete Root
50
20
10
60
30
null
50
Prof. Amr Goneid, AUC
70
x
delete
59
5. Binary Search Tree ADT
 Elements:
A BST consists of a collection of elements that are all
of the same type. An element is composed of two
parts: key of <keyType> and data of <dataType>
 Structure:
A node in a BST has at most two subtrees. The key
value in a node is larger than all the keys in its left
subtree and smaller than all keys in its right subtree.
Duplicate keys are not allowed.
Prof. Amr Goneid, AUC
60
Binary Search Tree ADT
 Data members
 root
pointer to the tree root
 Basic Operations
 binaryTree
 insert
 empty
 search
a constructor
inserts an item
checks if tree is empty
locates a node given a
key
Prof. Amr Goneid, AUC
61
Binary Search Tree ADT
 Basic Operations (continued)
 retrieve
 traverse
 preorder
 levelorder
 remove
 graph
retrieves data given key
traverses a tree
(In-Order)
pre-order traversal
Level-order traversal
Delete node given key
simple graphical output
Prof. Amr Goneid, AUC
62
Linked Representation
 The nodes in the BST will be implemented as a
linked structure:
left
element
right
t
32
32
16
45
16
40
45
40
Prof. Amr Goneid, AUC
63
Node Specification
// The linked structure for a node can be
// specified as a Class in the private part of
// the main binary tree class.
class treeNode
// Hidden from user
{
public:
keyType key;
// key
dataType data;
// Data
treeNode *left;
// left subtree
treeNode *right; // right subtree
}; // end of class treeNode declaration
//A pointer to a node can be specified by a type:
typedef treeNode * NodePointer;
NodePointer root;
Prof. Amr Goneid, AUC
64
6. Template Class Specification
 Because node structure is private, all references to pointers
are hidden from user
 This means that recursive functions with pointer
parameters must be private.
 A public (User available) member function will have to call
an auxiliary private function to support recursion.
 For example, to traverse a tree, the user public function will
be declared as:
void traverse ( ) const;
and will be used in the form:
BST.traverse ( );
Prof. Amr Goneid, AUC
65
Template Class Specification
 Such function will have to call a private traverse function:
void traverse2 (NodePointer ) const;
 Therefore, the implementation of traverse will be:
template <class keyType, class dataType>
void binaryTree<keyType, dataType>::traverse() const
{
traverse2(root);
}
 Notice that traverse2 can support recursion via its pointer
parameter
Prof. Amr Goneid, AUC
66
Template Class Specification
 For example, if we use in-order traversal, then the private
traverse function will be implemented as:
template <class keyType, class dataType>
void binaryTree <keyType, dataType>::traverse2
(NodePointer aRoot)
{
if (aRoot != NULL)
{ // recursive in-order traversal
traverse2 (aRoot->left);
cout << aRoot->key << endl;
traverse2 (aRoot->right);
}
} // end of private traverse
Prof. Amr Goneid, AUC
const
67
Template Class Specification
 All similar functions will be implemented using
the same method. For example:
Public Function
Private Function
insert (key,data)
insert2 (pointer,key,data)
search(key)
search2 (pointer,key)
retrieve(key,data)
retrieve2 (pointer,key,data)
traverse( )
traverse2 (pointer)
Prof. Amr Goneid, AUC
68
BinaryTree.h
// FILE: BinaryTree.h
// DEFINITION OF TEMPLATE CLASS BINARY SEARCH
// TREE
#ifndef BIN_TREE_H
#define BIN_TREE_H
// Specification of the class
template <class keyType, class dataType>
class binaryTree
{
Prof. Amr Goneid, AUC
69
BinaryTree.h
public:
// Public Member functions ...
// CREATE AN EMPTY TREE
binaryTree();
// INSERT AN ELEMENT INTO THE TREE
bool insert(const keyType &,
const dataType &);
// CHECK IF THE TREE IS EMPTY
bool empty() const;
// SEARCH FOR AN ELEMENT IN THE TREE
bool search (const keyType &) const;
// RETRIEVE DATA FOR A GIVEN KEY
bool retrieve (const keyType &, dataType &)
const;
Prof. Amr Goneid, AUC
70
BinaryTree.h
// TRAVERSE A TREE
void traverse() const;
// Iterative Pre-order Traversal
void preorder () const;
// Iterative Level-order Traversal
void levelorder () const;
// GRAPHIC OUTPUT
void graph() const;
// REMOVE AN ELEMENT FROM THE TREE
void remove (const keyType &);
.........
Prof. Amr Goneid, AUC
71
BinaryTree.h
private:
// Node Class
class treeNode
{
public:
keyType key;
// key
dataType data;
// Data
treeNode *left;
// left subtree
treeNode *right; // right subtree
}; // end of class treeNode declaration
typedef treeNode * NodePointer;
// Data member ....
NodePointer root;
Prof. Amr Goneid, AUC
72
BinaryTree.h
// Private Member functions ...
// Searches a subtree for a key
bool search2 ( NodePointer , const keyType &)
const;
//Searches a subtree for a key and retrieves data
bool retrieve2 (NodePointer , const keyType & ,
dataType &) const;
// Inserts an item in a subtree
bool insert2 (NodePointer &, const keyType &,
const dataType &);
Prof. Amr Goneid, AUC
73
BinaryTree.h
// Traverses a subtree
void traverse2 (NodePointer ) const;
// Graphic output of a subtree
void graph2 ( int , NodePointer ) const;
// LOCATE A NODE CONTAINING ELEMENT AND ITS
// PARENT
void parentSearch( const keyType &k,
bool &found,
NodePointer &locptr,
NodePointer &parent) const;
};
#endif
// BIN_TREE_H
#include “binaryTree.cpp”
Prof. Amr Goneid, AUC
74
BST Template Class
 The CSCI 321 course web site contains full
definitions and implementations of :
 binaryTree template class: BST class with
linked implementation
Prof. Amr Goneid, AUC
75
Analysis of BST operations
Assuming a balanced BST:
 bool insert
O(log n)
 bool empty()
O(1)
 bool retrieve
O(1)
 bool search
O(log n)
 void traverse
O(n)
 void graph
O(n)
 void remove
O(log n)
Prof. Amr Goneid, AUC
76
7. Other Search Trees
 Binary Search Trees have worst case
performance of O(n), and best case
performance of O(log n)
 There are many other search trees that are
balanced trees.
 Examples are: AVL Trees, Red-Black trees
Prof. Amr Goneid, AUC
77
AVL Trees
 Named after its Russian inventors:
Adel'son-Vel'skii and Landis (1962)
Prof. Amr Goneid, AUC
78
AVL Trees
 An AVL tree is a self balancing
binary search tree in which
 the
heights of the right subtree and left
subtree of the root differ by at most 1
 the left subtree and the right subtree are
themselves AVL trees
 rebalancing is done when insertion or
deletion causes violation of the AVL
condition.
Prof. Amr Goneid, AUC
79
AVL Tree
h
h-2
h-1
Notice that:
N(h) = N(h-1) + N(h-2) + 1
Prof. Amr Goneid, AUC
80
AVL Tree
Also
{N ( h )  1 }  { N ( h  1 )  1 }  { N ( h  2 )  1 }
This is a Fibonacci series and we can use the approximat e
formula for Fibonacci numbers :
1 1 5 


N( h ) 1 

5  2 
Or h  1.44 log( N )
h 3
This is the worst case height of the AVL tree
Prof. Amr Goneid, AUC
81