Transcript Chapter 5



What is a “Tree”?
For Example :
◦ Figure 5.1 (a)
◦ Figure 5.1 (b)
 The ancestry of
modern Europe
languages

root
A tree is a finite set of one or more nodes such that :
◦ (1) There is a specially designated node called the
root.
◦ (2) The remaining nodes are partitioned into n ≥ 0
disjoint sets T1, …, Tn, where each of these sets is
a tree.
We call T1, …, Tn, the sub-trees of the root.
…
T1
T2
Tn


The root of this tree is node A. (Fig. 5.2)
Definitions:
◦
◦
◦
◦
◦
Parent (A)
Children (E, F)
Siblings (C, D)
Root (A)
Leaf / Leaves
 K, L, F, G, M, I, J…

The degree of a node is the number of sub-trees of
the node.

The degree of A is 3; the degree of C is 1.

The level of a node:
◦ Initially letting the root be at level one
◦ For all other nodes, the level is the level of the node’s
parent plus one.
◦ The height or depth of a tree is the maximum level of any
node in the tree.

The node with degree 0 is a leaf or terminal node.


A node that has subtrees is the parent of the roots of the subtrees.
The roots of these subtrees are the children of the node.

Children of the same parent are siblings.

The ancestors of a node are all the nodes along the path from the
root to the node.

List Representation
◦ The root comes first, followed by a list of sub-trees
◦ Example: (A(B(E(K,L),F),C(G),D(H(M),I, J)))
data
link 1 link 2 ...
link n
A node must have a varying number of link
fields depending on the number of branches

Left Child-Right Sibling
Representation
◦ Fig.5.5

A Degree Two Tree
◦ Rotate clockwise by 45°
◦ A Binary Tree
data
left child right sibling


A binary tree is a finite set of nodes that is either
empty or consists of a root and two disjoint binary
trees called the left sub-tree and the right sub-tree.
Any tree can be transformed into a
binary tree.


root
By using left child-right sibling
representation
The left and right subtrees are
distinguished
The left
sub-tree
The right
sub-tree
Left child-right child tree representation of a tree is
transformed into binary tree
A
B
C
E
F
K
D
G
H
L
M
I
J
Structure Binary_Tree (abbreviated BinTree) is:
Objects: a finite set of nodes either empty or consisting of
a root node, left Binary_Tree, and right Binary_Tree.
Functions:
For all bt, bt1, bt2  BinTree, item  element
Bintree Create()::= creates an empty binary tree
Boolean IsEmpty(bt)::= if (bt==empty binary
tree) return TRUE else return FALSE
BinTree MakeBT(bt1, item, bt2)::= return a binary tree
whose left subtree is bt1, whose right subtree is bt2, and
whose root node contains the data item
Bintree Lchild(bt)::= if (IsEmpty(bt)) return error else return
the left subtree of bt
element Data(bt)::= if (IsEmpty(bt)) return error
else return the data in the root node of bt
Bintree Rchild(bt)::= if (IsEmpty(bt)) return error
else return the right subtree of bt

Skewed Binary Trees
◦ Fig.5.9 (a)

Complete Binary Trees
◦ Fig.5.9 (b)
Binary Tree Representations
If a complete binary tree with n nodes (depth =
⌊ log n + 1 ⌋) is represented sequentially, then for
any node with index i, 1<=i<=n, we have:
– parent(i) is at ∟i/2 ⌋ if i!=1. If i=1, i is at the root
and has no parent.
– left_child(i) is at 2i if 2i<=n. If 2i>n, then i has no
left child.
– right_child(i) is at 2i+1 if 2i +1 <=n. If 2i +1 >n,
then i has no right child.

[Maximum number of nodes] :
◦ (1) The maximum number of nodes on level i of a binary tree is
2i -1, i ≥ 1.
◦ (2) The maximum number of nodes in a binary tree of depth k is is
2k -1, k ≥ 1.
◦ The proof is by induction on i.

[No. of leaf nodes] :
◦ For any nonempty binary tree, T, if n0 is the number of leaf nodes
and n2 the number of nodes of degree 2, then n0 = n2 +1.
Full BT VS Complete BT
A full binary tree of depth k is a binary tree of
k
depth k having 2 -1 nodes, k>=0.
A binary tree with n nodes and depth k is
complete iff its nodes correspond to the nodes
numbered from 1 to n in the full binary tree of
depth k.
A
A
B
D
H
B
C
E
F
G
I
Complete binary tree
C
H
F
E
D
I
J
K
L
G
M
N
Full binary tree of depth 4
O



A full binary tree (sometimes proper binary tree or 2tree) is a tree in which every node other than the leaves
has two children.
A complete binary tree is a binary tree in which every
level, except possibly the last, is completely filled, and
all nodes are as far left as possible.
A binary tree of depth d is an almost complete binary
tree if:
◦ Each leaf in the tree is either at level d or at level d – 1.
◦ For any node nd in the tree with a right descendant at level d,
all the left descendants of nd that are leaves are also at level d.




(1) waste space
(2) insertion/deletion
problem
TREE REFER TO FIG 5.9
Array Representation (Fig. 5.11)
Linked Representation (Fig. 5.13) : Better than array representation

For complete and full binary trees, this representation
is ideal since it wastes no space. However, for the
skewed tree, less than half of the array is utilized.
typedef struct node *tree_pointer;
typedef struct node {
int data;
tree_pointer left_child,
right_child;
};


Instead of printf use cout in the code snippets
Traversing order : L, V, R
◦ L : moving left
◦ V : visiting the node
◦ R : moving right



Inorder Traversal : LVR
Preorder Traversal : VLR
Postorder Traversal : LRV



Inorder Traversal : A / B * C * D + E
Preorder Traversal : + * * / A B C D E
Postorder Traversal : A B / C * D * E +
◦ A recursive function starting from the root
 Move left Visit node Move right
In-order Traversal :
A/B*C*D+E
◦ A recursive function starting from the root
 Visit node Move left  Move right
◦ A recursive function starting from the root
 Move left Move right Visit node

Iterative Inorder Traversal
◦ Using a stack to simulate recursion
◦ Time Complexity: O(n), n is #num of node.

Level Order Traversal
◦ Visiting at each new level from the left-most node to the
right-most
◦ Using Data Structure : Queue
Add “+” in stack
Add “*”
Add “*”
Add “/”
Add “A”
Delete “A” &
Print
Delete “/” & Print
Add “B”
Delete “B” &
Print
Delete “*” & Print
Add “C”
Delete “C” & Print
Delete “*” & Print
Add “D”
Delete “D” & Print
Delete “+” & Print
Add “E”
Delete “E” & Print
In-order Traversal :
A/B*C*D+E
Add “+” in
Queue
Deleteq “+”
Addq “*”
Addq “E”
Deleteq “*”
Addq “*”
Addq “D”
Deleteq “E”
Deleteq “*”
Addq “/”
Addq “C”
Deleteq “D”
Deleteq “/”
Addq “A”
Addq “B”
Deleteq “C”
Deleteq “A”
Deleteq “B”
Level-order Traversal :
+*E*D/CAB

Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
In a Preorder sequence, leftmost element is the root of the tree. So we know
‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can
find out all elements on left side of ‘A’ are in left subtree and elements on
right are in right subtree. So we know below structure now.

Recursively follow the steps





Inorder: 4
2
5
(1) 6
7
3
8
Post order: 4 5
2
6
7
8
3
(1)
From the post-order array, we know that last
element is the root. We can find the root in inorder array. Then we can identify the left and right
sub-trees of the root from in-order array.
Using the length of left sub-tree, we can identify
left and right sub-trees in post-order array.
Recursively, we can build up the tree.
For this example, the constructed tree is:




INORDER = {4, 8, 10, 12, 14, 20, 22};
LEVEL ORDER= {20, 8, 22, 4, 12, 10, 14};
In a Level order sequence, the first element is the root of the tree. So
we know ’20’ is root for given sequences. By searching ’20’ in
Inorder sequence, we can find out all elements on left side of ‘20’ are
in left subtree and elements on right are in right subtree. So we know
below structure now.
20
/ \
/
\
{4,8,10,12,14} {22}
Let us call {4,8,10,12,14} as left subarray in Inorder traversal and
{22} as right subarray in Inorder traversal.
◦ In[] = {4, 8, 10, 12, 14}
◦ level[] = {8, 4, 12, 10, 14}
Repeat the above steps for both subtrees

EXPRESSION TREES
DECISION TREES: A decision tree is a graph
that uses a branching method to illustrate
every possible outcome of a decision.

An expression tree for an arithmetic, relational, or logical
expression is a binary tree in which:
• The parentheses in the expression do not appear.
• The leaves are the variables or constants in the expression.
• The non-leaf nodes are the operators in the expression:
 A node for a binary operator has two non-empty
subtrees.
 A node for a unary operator has one non-empty subtree.

The operators, constants, and variables are arranged in such
a way that an inorder traversal of the tree produces the
original expression without parentheses.
Expression
Expression Tree
Inorder Traversal Result
+
(a+3)
a
a+3
3
+
3+(4*5-(9+6))
3
-
*
4
3+4*5-9+6
+
9
5
6
log
log(x)
log x
x
!
n!
n
n!



Expression trees are used to remove ambiguity in expressions.
Consider the algebraic expression 2 - 3 * 4 + 5.
Without the use of precedence rules or parentheses, different orders
of evaluation are possible:
((2-3)*(4+5)) = -9
((2-(3*4))+5) = -5
(2-((3*4)+5)) = -15
(((2-3)*4)+5) = 1
(2-(3*(4+5))) = -25

The expression is ambiguous because it uses
infix notation: each operator is placed
between its operands.
Storing a fully parenthesized expression, such as
((x+2)-(y*(4-z))), is wasteful, since the parentheses in the
expression need to be stored to properly evaluate the
expression.
 A compiler will read an expression in a language like Java, and
transform it into an expression tree.
 Expression trees impose a hierarchy on the operations in the
expression. Terms deeper in the tree get evaluated first. This
allows the establishment of the correct precedence of
operations without using parentheses.
 Expression trees can be very useful for:
 Evaluation of the expression.
 Generating correct compiler code to actually compute the
expression's value at execution time.
 Performing symbolic mathematical operations (such as
differentiation) on the expression.


Assuming that t is a valid expression tree, a
pseudo code algorithm for evaluating the
expression tree is:
1
2
3
4
5
6
7
8
9
10
evaluate(ExpressionTree t){
if(t is a leaf)
return value of t's operand ;
else{
operator = t.element ;
operand1 = evaluate(t.left) ;
operand2 = evaluate(t.right) ;
return(applyOperator(operand1, operator, operand2) ;
}
}
+
2
Order of evaluation:
3
1
-
2
(2 + ((5 – 1) * 3))
*
5
3
1



A preorder traversal of an expression tree yields the prefix (or
polish) form of the expression.
• In this form, every operator appears before its operand(s).
An inorder traversal of an expression tree yields the infix
form of the expression.
• In this form, every operator appears between its operand(s).
A postorder traversal of an expression tree yields the postfix
(or reverse polish) form of the expression.
• In this form, every operator appears after its operand(s).
Prefix form: + a * - b c d
Infix form: a + b - c * d
Postfix form: a b c - d * +
+
a
*
-
b
d
c

Copying Binary Trees
◦ Program 5.6

Testing for Equality of Binary Trees
◦ Program 5.7

The Satisfiability Problem (SAT)

Equality: 2 binary trees having identical topology and
data are said to be equivalent. They have same
structure and same information in
corresponding nodes.

Formulas
◦ Variables : X1, X2, …, Xn
 Two possible values: True or False
◦ Operators : And (︿), Or (﹀), Not (﹁)
 A variable is an expression.
 If x and y are expressions,
then ﹁ x, x ︿ y, x ﹀y are expressions.
 Parentheses can be used to alter the normal order
of evaluation,
which is ﹁ before ︿ before ﹀.



The SAT problem
◦ Is there an assignment of values to the variables
that causes the value of the expression to be true?
For n variables, there are 2n possible combinations of
true and false.
The algorithm takes O(g 2n) time
◦ g is the time required to substitute the true and false
values for variables and to evaluate the expression.

Node Data Structure for SAT in C

A Enumerated Algorithm
◦ Time Complexity : O (2n)
void post_order_eval(tree_pointer node){
if (node){
post_order_eval(node->left_child);
post_order_eval(node->right_child);
switch(node->data){
case not: node->value=!node->right_child->value;
break;
case and: node->value=node->right_child->value &&
node->left_child->value; break;
case or: node->value=node->right_child->value ||
node->left_child->value; break;
case true: node->value=TRUE; break;
case false: node->value=FALSE; break;
} } }


Linked Representation of Binary Tree
◦ more null links than actual pointers (waste!)
Threaded Binary Tree
◦ Make use of these null links
◦ Threads
 Replace the null links by pointers (called threads)
 If ptr -> left_thread = TRUE
 Then ptr -> left_child is a thread (to the node before ptr)
 Else ptr -> left_child is a pointer to left child
 If ptr -> right_thread = TRUE
 Then ptr -> right_child is a thread (to the node after ptr)
 Else ptr -> right_child is a pointer to right child
typedef struct threaded_tree *threaded_pointer;
typedef struct threaded_tree {
short int left_thread;
threaded_pointer left_child;
char data;
short int right_child;
threaded_pointer right_child;
}
Head node of
the tree
Actual
tree


Threads simplify inorder traversal algorithm
An easy O(n) algorithm (Program 5.11.)
◦ For any node, ptr, in a threaded binary tree
 If ptr -> right_thread = TRUE
 The inorder successor of ptr = ptr -> right_child
 Else (Otherwise, ptr -> right_thread = FALSE)
 Follow a path of left_child links from the right_child of ptr
until finding a node with left_Thread = TRUE
◦ Function insucc (Program 5.10.)
 Finds the inorder successor of any node (without using a
stack)


Insert a new node as a child of a parent node
◦ Insert as a left child (left as an exercise)
◦ Insert as a right child (see examples 1 and 2)
Is the original child node an empty subtree?
◦ Empty child node (parent -> child_thread = TRUE)
 See example 1
◦ Non-empty child node (parent -> child_thread = FALSE)
 See example 2





parent(B) -> right_thread = FALSE
child(D) -> left_thread & right_thread = TRUE
child -> left_child = parent
child -> right_child = parent -> right_child
parent -> right_child = child
(1)
(3)
(2)
(3)
(2)
(4)
(1)
void insert_right(threaded_pointer parent,
threaded_pointer child){
threaded_pointer temp;
child->right_child = parent->right_child;
(1) child->right_thread = parent->right_thread;
child->left_child = parent;
(2) child->left_thread = TRUE;
parent->right_child = child;
parent->right_thread = FALSE;
(3) If (!child->right_thread){/*non-empty
child*/
temp = insucc(child);
temp->left_child = child; } }
(4)




NO null links are present. Hence no wastage
of spaces.
Traversal and finding predecessor and
successor becomes easier.
Thread Links facilitate upward and downward
movement.
Insertion and deletion becomes simpler.


Wastage of memory to store and check if a
link is thread or not.
Time consuming insertion and deletion
operation as many links must be modified to
achieve them.


An application of complete binary tree
Definition
◦ A max (or min) tree
 a tree in which the key value in each node is no smaller (or greater) than the
key values in its children (if any).
◦ A max (or min) heap
 a max (or min) complete binary tree
A min heap
A max heap

Creation of an empty heap
◦ PS. To build a Heap  O( n log n )
Property:
The root of max heap (min heap) contains
the largest (smallest).
 Application of Heap
◦ Priority Queues

machine service
◦ amount of time (min heap)
◦ amount of payment (max heap)
ADT for Max Heap
structure MaxHeap
objects: a complete binary tree of n > 0 elements organized so that
the value in each node is at least as large as those in its children
functions:
for all heap belong to MaxHeap, item belong to Element, n,
max_size belong to integer
MaxHeap Create(max_size)::= create an empty heap that can
hold a maximum of max_size elements
Boolean HeapFull(heap, n)::= if (n==max_size) return TRUE
else return FALSE
MaxHeap Insert(heap, item, n)::= if (!HeapFull(heap,n)) insert
item into heap and return the resulting heap
else return error
Boolean HeapEmpty(heap, n)::= if (n>0) return FALSE
else return TRUE
Element Delete(heap,n)::= if (!HeapEmpty(heap,n)) return one
instance of the largest element in the heap
and remove it from the heap
else return error
class maxheap
{
int key;
public: void insert();
void display();
void delMax();
};
maxheap h[50];// 50 is the maximumum capacity of the
heap
int n=0;
(Figure 5.28)
void maxheap::insert(){
if(n==50)
cout<<"\nHeap Is Full";
else{
maxheap temp;
cout<<"\nEnter the element:";
cin>>temp.key;
int i=++n;
while(i!=1&&temp.key>h[i/2].key){
h[i]=h[i/2];
i=i/2;}
h[i]=temp;
}
display();}

Delete the max (root) from a max heap
◦ Step 1 : Remove the root
◦ Step 2 : Replace the last element to the root
◦ Step 3 : Heapify (Reestablish the heap)
void maxheap::delMax()
{
int temp;
if(n==0)
{
cout<<"Heap is empty";
return;
}
cout<<"Deleted item is"<<h[1].key;
h[1].key=h[n].key;
n--;
int i=1;
while(((2*i)<=n && (2*i+1)<=n) &&
(h[i].key<h[2*i].key ||
h[i].key<h[2*i+1].key))
if(h[2*i].key>=h[2*i+1].key){
temp=h[i].key;
h[i].key=h[2*i].key;
h[2*i].key=temp;
i=i*2;}else{
temp=h[i].key;
h[i].key=h[2*i+1].key;
h[2*i+1].key=temp;
i=2*i+1;}
if(((2*i)<=n) && h[i].key<h[2*i].key){
temp=h[i].key;
h[i].key=h[2*i].key;
h[2*i].key=temp;
i=i*2;}
if(((2*i+1)<=n) && h[i].key<h[2*i+1].key)
{
temp=h[i].key;
h[i].key=h[2*i+1].key;
h[2*i+1].key=temp;
i=i*2+1;
}
}
void maxheap::display()
{
cout<<"\nHeap Is: \n";
for(int i=1;i<=n;i++)
cout<<h[i].key<<"\t";
}


Heap : search / delete arbitrary element
◦ O(n) time
Binary Search Trees (BST)
◦ Searching  O(h), h is the height of BST
◦ Insertion  O(h)
◦ Deletion  O(h)
◦ Can be done quickly by both key value and rank

A binary search tree is a binary tree, that may be empty
or satisfies the following properties :
◦ (1) every element has a unique key.
◦ (2&3) The keys in a nonempty left(/right) sub-tree must be
smaller(/larger) than the key in the root of the sub-tree.
◦ (4) The left and right sub-trees are also binary search trees.
◦ Time Complexity
 search  O(h), h is the height of BST.
 search2  O(h)

Step 1 : Check if the inserting key is different
from those of existing elements
◦ Run search function  O(h)

Step 2 : Run insert_node function
◦ Program 5.17  O(h)
void insert_node(tree_pointer *node, int num) {
tree_pointer ptr, temp = modified_search(*node, num);
if (temp || !(*node)) {
ptr = (tree_pointer) malloc(sizeof(node));
if (IS_FULL(ptr)) {
fprintf(stderr, “The memory is full\n”); exit(1);
}
ptr->data = num;
ptr->left_child = ptr->right_child = NULL;
if (*node)
if (num<temp->data) temp->left_child=ptr;
else temp->right_child = ptr;
else *node = ptr;
}
}

Delete a non-leaf node with two children
◦ Replace the largest element in its left sub-tree
◦ Or Replace the smallest element in its right sub-tree
◦ Recursively to the leaf  O(h)

The Height of the binary search tree is
O(log2n), on the average.
◦ Worst case (skewed)  O(h) = O(n)

Balanced Search Trees
◦ With a worst case height of O(log2n)