Notes

Unit 7
Trees, Tree Traversals and Binary
Search Trees
King Fahd University of Petroleum & Minerals
College of Computer Science & Engineering
Information & Computer Science Department
2
¾ “Data Structures and Algorithms in Java”, 3rd Edition,
Adam Drozdek, Cengage Learning, ISBN
978-9814239233
¾ Chapter 6 Sections 1-6.
¾ Section 6.4.3 regarding “Stackless Depth-First Traversal” and
“Threaded Trees” is omitted.
Reading Assignment
3
Objectives
Discuss the following topics:
¾ Trees, Binary Trees, and Binary Search Trees
¾ Implementing Binary Trees
¾ Searching a Binary Search Tree
¾ Tree Traversal
¾ Binary Search Tree Insertion
¾ Binary Search Tree Deletion
Definition of a Tree
¾ A tree, is a finite set of nodes together with a finite set of edges
(arcs) that define parent-child relationships. Each edge connects a
parent to its child. Example:
Nodes={A,B,C,D,E,f,G,H}
Edges={(A,B),(A,E),(B,F),(B,G),(B,H),
(E,C),(E,D)}
¾ A path from node m1 to node mk is a list of nodes m1, m2, . . . , mk
such that each is the parent of the next node in the list.
¾ The length of such a path is k - 1.
¾ Example: A, E, C is a path of length 2.
A
E B
D C F H G
4
Definition of a Tree (Cont.)
¾ A tree satisfies the following properties:
1. It has one designated node, called the root, that has no parent.
2. Every node, except the root, has exactly one parent.
3. A node may have zero or more children.
4. There is a unique directed path from the root to each node.
5
2
4 1 6
3
5
2
4 1 6
3
5
2
4
1
6
3
tree Not a tree Not a tree
5
Tree Terminology
• Ordered tree: A tree in which the children of each node are linearly
ordered (usually from left to right).
• Ancestor of a node v: Any node, including v itself, on the path from
the root to the node.
• Proper ancestor of a node v: Any node, excluding v, on the path
from the root to the node.
A
B C
D E F G
Ancestors of G proper ancestors of E
An Ordered Tree
6
Tree Terminology (Contd.)
¾ Descendant of a node v: Any node, including v itself, on any path
from the node to a leaf node (i.e., a node with no children).
¾ Proper descendant of a node v: Any node, excluding v, on any path
from the node to a leaf node.
¾ Subtree of a node v: A tree rooted at a child of v.
Descendants of a node C
A
B C
D E F G
Proper descendants
of node B
A
B C
D E F G
subtrees of node A
7
Tree Terminology (Contd.)
A
B
D
H
C
E F G
J I
proper ancestors of node H
proper descendants
of node C
subtrees of A
A
B
D
H
C
E F G
J I
parent of node D
child of node D
grandfather of nodes I,J
grandchildren of node C
8
Tree Terminology (Contd.)
¾ Degree: The number of subtrees of a node
¾ Each of node D and B
has degree 1.
¾ Each of node A and E
has degree 2.
¾ Node C has degree 3.
¾ Each of node F,G,H,I,J has degree 0.
¾ Leaf: A node with degree 0.
¾ Nonterminal or internal node: a node with degree greater than 0.
¾ Siblings: Nodes that have the same parent.
¾ Size: The number of nodes in a tree.
A
B
D
H
C
E
F
G
J I
An Ordered Tree
with size of 10
Siblings
of E
Siblings of A
9
Tree Terminology (Contd.)
¾ Level (or depth) of a node v: The length of the path from
the root to node v plus one.
¾ Same as the number of nodes in the path.
¾ Height of a nonempty tree: The maximum level of a
node in a tree.
¾ By definition the height of an empty tree is 0.
A
B
D
H
C
E F G
J I
k
Level 1
Level 2
Level 3
Level 4
Level 5
• The height of the tree is
10
5
11
Example Trees

Figure 6-1 Examples of trees
Importance of Trees
¾ Trees are very important data structures in computing.
¾ They are suitable for:
¾ Hierarchical structure representation, e.g.,
¾ File directory.
¾ Organizational structure of an institution.
¾ Class inheritance tree.
¾ Problem representation, e.g.,
¾ Expression tree.
¾ Decision tree.
¾ Efficient algorithmic solutions, e.g.,
¾ Search trees.
¾ Efficient priority queues via heaps.
12
13
Hierarchical Structure Representation

Figure 6-2 Hierarchical structure of a university shown as a tree
14
Orderly Trees
¾ An orderly tree is where all elements are stored
according to some predetermined criterion of ordering
Figure 6-3 Transforming (a) a linked list into (b) a tree
15
Binary Trees
¾ A binary tree is a tree whose nodes have two children
(possibly empty), and each child is designated as either
a left child or a right child

Figure 6-4 Examples of binary trees
Binary Trees
¾ Definition: A decision tree (full binary tree) is either an empty binary tree or a binary tree in which every node is either a leaf node or an internal node
with two children.
• Definition: A complete binary tree is either an empty binary tree
or a binary tree in which all nonterminal nodes have both their
children, and all leaves are at the same level
16
17
Binary Trees
Figure 6-5 Adding a leaf to tree (a), preserving the relation of the
number of leaves to the number of nonterminal nodes (b)
Theorem: The number of leaves in a non-empty decision tree is one more than
the number of nonterminal nodes.
Binary Trees
¾ What is the maximum height of a binary tree with n
elements?
n
¾ What is the minimum height of a binary tree with n
elements?
⎡lg(n +1)⎤
¾ What is the minimum and maximum heights of a complete binary tree?
Both are ⎡lg(n +1)⎤
¾ What is the minimum and maximum heights of a decision (full binary) tree?
⎡lg(n +1)⎤ and ⎡n/2⎤
18
Binary Search Trees
¾ Definition: A binary search tree (BST) is a binary tree that is
empty or that satisfies the BST ordering property:
1. The key of each node is greater than each key in the left subtree, if
any, of the node.
2. The key of each node is less than each key in the right subtree, if any,
of the node.
¾ Thus, each key in a BST is unique.
19
20
Binary Search Tree Examples
Figure 6-6 Examples of binary search trees
21
Implementing Binary Trees
¾ Binary trees can be implemented in at least two ways:
¾ As arrays
¾ As linked structures
¾ To implement a tree as an array, a node is declared as
an object with an information field and two “reference”
fields
22
Implementing Binary Trees
Figure 6-7 Array representation of the tree in Figure 6.6c
23
Implementing Binary Trees
Figure 6-8 Implementation of a generic binary search tree
/************************ BSTNode.java **************************
* node of a generic binary search tree
*/
public class BSTNode<T extends Comparable<? super T>> {
protected T el;
protected BSTNode<T> left, right;
public BSTNode() {
left = right = null;
}
public BSTNode(T el) {
this(el,null,null);
}
public BSTNode(T el, BSTNode<T> lt, BSTNode<T> rt) {
this.el = el; left = lt; right = rt;
}
}
24
Implementing Binary Trees
Figure 6-8 Implementation of a generic binary search tree
(continued)
/************************ BST.java **************************
* generic binary search tree
*/
public class BST<T extends Comparable<? super T>> {
protected BSTNode<T> root = null;
public BST() {
}
protected void visit(BSTNode<T> p) {
System.out.print(p.el + " ");
}
protected T search(T el) {…}
public void breadthFirst() {…}
public void preorder() {
preorder(root);
}
public void inorder() {
inorder(root);
}
public void postorder() {
postorder(root);
}
25
Implementing Binary Trees
Figure 6-8 Implementation of a generic binary search tree
(continued)
protected void inorder(BSTNode<T> p) {…}
protected void preorder(BSTNode<T> p) {…}
protected void postorder(BSTNode<T> p) {…}
public void deleteByCopying(T el) {…}
public void deleteByMerging(T el) {…}
public void iterativePreorder() {…}
public void iterativeInorder() {…}
public void iterativePostorder2() {…}
public void iterativePostorder() {…}
public void MorrisInorder() {…}
public void MorrisPreorder() {…}
public void MorrisPostorder() {…}
public void balance(T data[], int first, int last) {…}
public void balance(T data[]) {…}
}
26
Searching a Binary Search Tree
Figure 6-9 A function for searching a binary search tree
protected T search(T el) {
BSTNode<T> p = root;
while (p != null)
if (el.equals(p.el))
return p.el;
else if (el.compareTo(p.el) < 0)
p = p.left;
else p = p.right;
return null;
}
27
Searching a Binary Search Tree
¾ The internal path length (IPL) is the sum of all path
lengths of all nodes
¾ It is calculated by summing
Σ(i – 1)Li

over all levels i, where Li is the number of nodes on level L
¾ A depth of a node in the tree is determined by the path
length
¾ An average depth, called an average path length, is
given by the formula IPL/n, which depends on the
shape of the tree
Importance of BSTs
¾ BSTs provide good logarithmic time performance in the best and average
cases.
¾ Average case complexities of using linear data structures compared to
BSTs:
Data Structure Retrieval Insertion Deletion
O(log n)
FAST
O(log n)
FAST
O(log n)
FAST BST
O(n)
SLOW
O(n)
SLOW
O(log n)
FAST* Sorted Array
O(n)
SLOW
O(n)
SLOW
O(n)
SLOW Sorted Linked List
*using binary search
28
29
Tree Traversal (Definition)
¾ The process of systematically visiting every node once in
a tree and performing some computation at each node
in the tree is called a tree traversal.
¾ There are two methods in which to traverse a tree:
1. Breadth-First Traversal.
2. Depth-First Traversal: • Preorder traversal
• Inorder traversal (for binary trees only)
• Postorder traversal
29
30
Breadth-First Traversal
Figure 6-10 Top-down, left-to-right, breadth-first traversal
implementation
public void breadthFirst() {
BSTNode<T> p = root;
Queue<BSTNode<T>> queue = new Queue<BSTNode<T>>();
if (p != null) {
queue.enqueue(p);
while (!queue.isEmpty()) {
p = queue.dequeue();
visit(p);
if (p.left != null)
queue.enqueue(p.left);
if (p.right != null)
queue.enqueue(p.right);
}
}
}
31
Breadth-First Traversal
H
D
B
A C E G I K M O
N
L
F J
H D L B F J N A C E G I K M O
31
32
Depth-First Traversal
¾ Depth-first traversal proceeds as far as possible to
the left (or right), then backs up until the first
crossroad, goes one step to the right (or left), and
again as far as possible to the left (or right)
¾ V — Visiting a node
¾ L — Traversing the left subtree
¾ R — Traversing the right subtree
33
Depth-First Traversals
Name for each Node:
•Visit the node
•Visit the left subtree, if any.
•Visit the right subtree, if any.
Preorder
(V-L-R)
•Visit the left subtree, if any. Visit the
node
•Visit the right subtree, if any.
Inorder
(L-V-R)
•Visit the left subtree, if any.
•Visit the right subtree, if any.
•Visit the node
Postorder
(L-R-V)
33
34
Depth-First Traversal (continued)
Figure 6-11 Depth-first traversal implementation
protected void inorder(BSTNode<T> p) {
if (p != null) {
inorder(p.left);
visit(p);
inorder(p.right);
}
}
protected void preorder(BSTNode<T> p) {
if (p != null) {
visit(p);
preorder(p.left);
preorder(p.right);
}
}
protected void postorder(BSTNode<T> p) {
if (p != null) {
postorder(p.left);
postorder(p.right);
visit(p);
}
}
35
Depth-first Preorder Traversal
H D B A C F E G L J I K N M O
V-L-R
35
H
D
B
A C E G I K M O
N
L
F J
36
Depth-first Inorder Traversal
L-V-R
A B C D E F G H I J K L M N O
Note: An inorder traversal of a BST visits the keys sorted in increasing order.
36
H
D
B
A C E G I K M O
N
L
F J
37
Depth-first Postorder Traversal
H
D
B
A C E G I K M O
N
L
F J
L-R-V
A C B E G F D I K J M O N L H
37
38
Iterative Preorder Traversal
Figure 6-15 A nonrecursive implementation of preorder tree traversal
public void iterativePreorder() {
BSTNode<T> p = root;
Stack<BSTNode<T>> travStack = new Stack<BSTNode<T>>();
if (p != null) {
travStack.push(p);
while (!travStack.isEmpty()) {
p = travStack.pop();
visit(p);
if (p.right != null)
travStack.push(p.right);
if (p.left != null) // left child pushed after right
travStack.push(p.left);// to be on the top of the
stack;
}
}
}
39
BST Insertion
Figure 6-22 Inserting nodes into binary search trees
40
Insertion (continued)
Figure 6-23 Implementation of the insertion algorithm
public void insert(T el) {
BSTNode<T> p = root, prev = null;
while (p != null) { // find a place for inserting new node;
prev = p;
if (el.compareTo(p.el) < 0)
p = p.left;
else p = p.right;
}
if (root == null) // tree is empty;
root = new BSTNode<T>(el);
else if (el.compareTo(prev.el) < 0)
prev.left = new BSTNode<T>(el);
else prev.right = new BSTNode<T>(el);
}
41
Deletion
¾ There are three cases of deleting a node from the
binary search tree:
¾ The node is a leaf; it has no children
¾ The node has one child
¾ The node has two children
42
Deletion (continued)
Figure 6-26 Deleting a leaf
Figure 6-27 Deleting a node with one child
43
Deletion by Merging
¾ Making one tree out of the two subtrees of the node
and then attaching it to the node’s parent is called
deleting by merging
Figure 6-28 Summary of deleting by merging
44
Deletion by Merging (continued)
Figure 6-29 Implementation of algorithm for deleting by merging
public void deleteByMerging(T el) {
BSTNode<T> tmp, node, p = root, prev = null;
while (p != null && !p.el.equals(el)) { // find the node p
prev = p; // with element el;
if (el.compareTo(p.el) < 0)
p = p.right;
else p = p.left;
}
45
node = p;
if (p != null && p.el.equals(el)) {
if (node.right == null) // node has no right child: its left
node = node.left; // child (if any) is attached to its parent;
else if (node.left == null) // node has no left child: its right
node = node.right; // child is attached to its parent;
else { // be ready for merging subtrees;
tmp = node.left; // 1. move left
while (tmp.right != null) // 2. and then right as far as
tmp = tmp.right; // possible;
tmp.right = // 3. establish the link between
node.right; // the rightmost node of the left
// subtree and the right subtree;
node = node.left; // 4.
}
if (p == root)
root = node;
else if (prev.left == p)
prev.left = node;
else prev.right = node; // 5.
}
else if (root != null)
System.out.println("el " + el + " is not in the tree");
else System.out.println("the tree is empty");
}
Deletion by Merging (continued)
Figure 6-29 Implementation of algorithm for deleting by merging
(continued)
46
Deletion by Merging (continued)
Figure 6-30 Details of deleting by merging
47
Deletion by Merging (continued)
Figure 6-31 The height of a tree can be (a) extended or
(b) reduced after deleting by merging
48
Deletion by Merging (continued)
Figure 6-31 The height of a tree can be (a) extended or
(b) reduced after deleting by merging (continued)
49
Deletion by Copying
¾ If the node has two children, the problem can be
reduced to:
¾ The node is a leaf
¾ The node has only one nonempty child
¾ Solution: replace the key being deleted with its
immediate predecessor (or successor)
¾ A key’s predecessor is the key in the rightmost node in
the left subtree
50
Deletion by Copying (continued)
Figure 6-32 Implementation of an algorithm for deleting by copying
public void deleteByCopying(T el) {
BSTNode<T> node, p = root, prev = null;
while (p != null && !p.el.equals(el)) { // find the node p
prev = p; // with element el;
if (el.compareTo(p.el) < 0)
p = p.left;
else p = p.right;
}
51
node = p;
if (p != null && p.el.equals(el)) {
if (node.right == null) // node has no right child;
node = node.left;
else if (node.left == null) // no left child for node;
node = node.right;
else {
BSTNode<T> tmp = node.left; // node has both children;
BSTNode<T> previous = node; // 1.
while (tmp.right != null) { // 2. find the rightmost
previous = tmp; // position in the
tmp = tmp.right; // left subtree of node;
}
node.el = tmp.el; // 3. overwrite the reference
// to the element being deleted;
if (previous == node) // if node's left child's
previous.left = tmp.left; // right subtree is null;
else previous.right = tmp.left; // 4.
}
if (p == root)
root = node;
else if (prev.left == p)
prev.left = node;
else prev.right = node;
}
else if (root != null)
System.out.println("el " + el + " is not in the tree");
else System.out.println("the tree is empty");
}
Figure 6-32 Implementation of an algorithm for deleting by copying
(continued)
52
Deletion by Copying (continued)
Figure 6-33 Deleting by copying