COMP9024: Data Structures and Algorithms
COMP9024: Data Structures and
Algorithms
Trees and Binary Search Trees
Contents
• Trees
• Tree traversals
• Binary search trees
Maps and Dictionaries
• A map (dictionary) is a collection of data items each of which is a pair (key, value), and supports
the following major operations:
find(item): find item in the collection
insert(item): insert item into the collection
remove(item): remove item from the collection
• The only difference between a map and a dictionary is that in a map, all keys are distinct while in
a dictionary, there may exist duplicate keys.
• For example, given a list of students, we can use a map to model it if student IDs are the keys, and
we can use a dictionary to model it if students names are the keys.
• A value can be any data structure such as a student record.
Applications: Google, databases, online trading systems, ….
Key question: how to make the above three major operations fast?
Trees
In computer science, a
tree is an abstract model
of a hierarchical
structure
A tree consists of nodes
with a parent-child
relation
Applications:
Organization charts
File systems
Programming
environments
Computers”R”Us
Sales R&DManufacturing
Laptops DesktopsUS International
Europe Asia Canada
Trees Terminology
Root: node without parent (A)
Internal node: node with at least
one child (A, B, C, F)
Leaf node: node without children
(E, I, J, K, G, H, D)
Ancestors of a node: parent,
grandparent, grand-grandparent,
etc.
Depth of a node: number of
ancestors
Height of a tree: maximum depth
of any node (3)
Descendant of a node: child,
grandchild, grand-grandchild, etc.
Preorder Traversal
A traversal visits the nodes of a
tree in a systematic manner
In a preorder traversal, a node is
visited before its descendants
Application: print a structured
document
Postorder Traversal
In a postorder traversal, a
node is visited after its
descendants
Application: compute space
used by files in a directory and
its subdirectories
cs16/
homeworks/ todo.txt1Kprograms/
DDR.java
10K
Stocks.java
25K
h1c.doc
3K
h1nc.doc
2K
Robot.java
20K
9
3
1
7
2 4 5 6
8
Binary Trees
A binary tree is a tree with the
following properties:
Each internal node has at most two
children
A leaf node has no child
The children of a node are an
ordered pair
We call the children of an internal
node left child and right child
Alternative recursive definition: a
binary tree is either
a tree consisting of a single node, or
a tree whose root has an ordered
pair of children, each of which is a
binary tree
Applications:
arithmetic expressions
decision processes
searching
A
B C
F GD E
H I
Arithmetic Expression Tree
Binary tree associated with an arithmetic expression
internal nodes: operators
external nodes: operands
Example: arithmetic expression tree for the
expression (2 × (a − 1) + (3 × b))
+
××
−2
a 1
3 b
Decision Trees
Inorder Traversal
In an inorder traversal a
node is visited after its left
subtree and before its right
subtree
Application: draw a binary
tree
x(v) = inorder rank of v
y(v) = depth of v
3
1
2
5
6
7 9
8
4
Print Arithmetic Expressions
Specialization of an inorder
traversal
print operand or operator
when visiting node
print “(“ before traversing left
subtree
print “)“ after traversing right
subtree
Algorithm printExpression(v)
{ if v has a left child
{ print(“(’’);
printExpression(left(v)); }
print(v.element ());
if v has a Right child
{ printExpression(right(v));
print (“)’’); }
}
((2 × (a − 1)) + (3 × b))
+
××
−2
a 1
3 b
Evaluate Arithmetic Expressions
Specialization of a postorder
traversal
recursive method returning
the value of a subtree
when visiting an internal
node, combine the values
of the subtrees
+
××
−2
5 1
3 2
Algorithm evalExpr(v)
{ if v is a leaf node
return v.element;
else
{ x = evalExpr(leftChild (v));
y = evalExpr(rightChild (v));
◊ = operator stored at v;
return x ◊ y;
}
}
Binary search trees
A binary search tree is a binary tree storing keys (or
key-value entries) at its nodes and satisfying the
following property:
Let u, v, and w be three nodes such that u is in the left
subtree of v and w is in the right subtree of v. We have
key(u) ≤ key(v) ≤ key(w)
An inorder traversal of a binary search trees visits
the keys in non-decreasing order
Binary Search Tree Operations
Operations on BSTs:
• insert(Tree,Item) … add a new item to tree via key
• delete(Tree,Key) … remove item with specified key from tree
• search(Tree,Key) … find item containing key in tree
• plus, “bookkeeping” … new(), free(), show(), …
Representing BSTs in C
Node structure:
typedef struct Node {
int key; // we ignore value here
struct Node *left, *right;
} Node;
Searching in BSTs
TreeSearch(v, k)
Input v (node), k (key)
Output the node containing k or null
if v is null or v.key=k
return v
if k < v.key
return TreeSearch(v.left, k) // search left subtree
else
return TreeSearch(v.right, k) // search right subtree
Time complexity: O(n)
Example: TreeSearch(root, 4)
Insertion in BSTs (1/2)
• To insert a new item with key k, we
search for key k.
• Let w be the node where the search
stops ( the child of w to be visited
does not exist)
• Consider two cases:
k≤w.key: Insert the new item
as the left child of w (insert
equal keys in the left subtree)
K>w.key: Insert the new item
as the right child of w
Time complexity: O(n)
Example: insert 5
Insertion in BSTs (2/2)
TreeInsert(v, k)
Input v (node), k (key)
Output: none
if root= null // empty tree
root=CreateNode(k); // create a new node (root) to store k
else if k <= v.key // insert duplicate keys in left subtree
{ if v.left=null
v.left=CreateNode(k); // insert a new node as the left child of v
else
TreeInsert(v.left, k);
}
else if k> v.key
{ if v.right=null
v.right=CreateNode(k); // insert a new node as the right child of v
else
TreeInsert(v.right, k);
}
Deletion in BSTs (1/3)
To perform operation delete(tree,
k), we search for key k
Assume key k is in the tree, and
let v be the node storing k
If node v has no left child, we
remove v from the tree
If node v has only one child, we
remove v from the tree and make
its child the child of its parent
Example: delete 4
Deletion in BSTs (2/3)
3
1
8
6 9
5
v
w
5
1
8
9
v
2
2
6
If node v has two children,
we find the node w that
follows v in an inorder
traversal.
w is called the immediate
inorder successor of v.
We copy the value and key
of w into node v
We remove node w (must
be a node with no child)
Example: delete 3
Deletion in BSTs (3/3)
3
1
9
v
w
2
2
1
9
v
Alternatively, we find the
node w that precedes v in
an inorder traversal.
w is called the immediate
inorder predecessor of v.
We copy the value and key
of w into node v
We remove node w (must
be a node with no child)
Example: delete 3
5
6
8
5
6
8
Performance
Consider a set of n
entries stored in a
binary search tree of
height h
the space used is O(n)
Operations find, insert
and delete take O(h)
time
The height h is O(n) in
the worst case and
O(log n) in the best
case
Summary
• Trees
• Tree traversals
• Binary search trees (BSTs)
• BST search, insertion and deletion
Sedgewick, Ch.5.4-12.5
COMP9024: Data Structures and Algorithms
Contents
Maps and Dictionaries
Trees
Trees Terminology
Preorder Traversal
Postorder Traversal
Binary Trees
Arithmetic Expression Tree
Decision Trees
Inorder Traversal
Print Arithmetic Expressions
Evaluate Arithmetic Expressions
Binary search trees
Binary Search Tree Operations
Representing BSTs in C
Searching in BSTs
Insertion in BSTs (1/2)
Insertion in BSTs (2/2)
Deletion in BSTs (1/3)
Deletion in BSTs (2/3)
Deletion in BSTs (3/3)
Performance
Summary