DS chapter7.ppt.................................

ppt

1. BINARY TREES
It is a non-linear data structure.
It is a hierarchical data structure. ( OS file maintenance)
Most general form of a tree can be defined as an
“connected acyclic graph “.

2. TREES
Trees are normally divided into two groups
General trees :
Binary trees : or or
10
812 20
10
12 20
10
10
20
10
20

3. Binary Trees:
A binary is a tree which is a collection of zero
or more nodes. A tree can be empty or partitioned into three
subgroups namely root , left sub tree and right sub tree.
In general, a tree in which each node has either
zero, one or two sub trees is called a binary tree.
or or
Root:
If tree is not empty, the first node is called root node.
10
12 20
10
10
20

4.  
Left sub tree:
It is a tree which is connected to the left of root & it
is called left sub tree.
 
Right sub tree:
It is a tree which is connected to the right of the root
& it is called right sub tree.
In general, a tree in which the out degree of node
has either zero, one or two is called a binary tree.

5. Different terminologies normally associated with trees:
 
Root node:
A node with in degree O is called root node it is
the first node in the tree. ( A root is a node without parent )
Child:
The nodes , which are all reachable from a node X using
only one edge are called children.
Siblings:
Two or more nodes having the same parent are called
siblings.

6. Parent :
A node having left sub tree or right sub tree or both is
said to be a parent node.
Leaf :
A node in a tree that has an out degree of Zero is
called a leaf nodes. ( Leaves are nodes without children )
Internal nodes :
The nodes except leaf nodes in a tree are called
internal nodes.

7. Level:
The distance of a node from the root is called level of
the node.
In a tree, the root has a level 0(zero) and level of any
other node is one more than the level of its father.
Height : (depth) :
The height of the tree is defined as the maximum level
of any leaf in the tree.

8. Types of binary trees:
The binary trees are classified as follows,
Strictly binary tree
Complete binary tree
Almost Complete binary tree
An expression tree
Binary search tree
AVL trees.

9. Strictly binary tree :
If the out degree of every node in a tree is either 0
or 2 , then the tree is said to be strictly binary tree.
Eg : OR
10
12 20
10
12
10
12 20
10
12

10. Complete binary tree:
A strictly binary tree in which the number of nodes
at any level i is 2 pow i, is said to be a complete binary
tree.
Eg :
10
12 20
10
12
1012

11. Almost Complete binary tree:
It is a strictly binary tree, except the last level.
Eg :
10
12 20
10
12
12

12. Storage representation of a binary tree :
The storage representation of binary trees can be
classified as shown below,

Sequential allocation technique (static allocation )
Linked allocation technique( Dynamic allocation)

13. Sequential allocation technique:
A tress can also be represented using an array
which is called sequential representation.
0
1 2
3 4 5 0 1 2 3 4 5
10
12 20
10
12
12
10 12 20 12 10 12

14. Linked allocation technique:
In a linked allocation technique a node in
a tree has three fields,
Info : Which contains actual information
Llink : which contains address of the left sub tree.
Rlink : which contains address of the right sub tree.

15. So, a node can be represented using structure as shown
below,
Struct node
{
int info;
Struct node * llink;
Struct node * rlink;
};
 
typedef struct node * NODE;

16. A pointer variable “root” can be used to point to
the root node always .
If the tree is empty , the pointer variable root
points to NULL indicating the tree is empty,
i.e., NODE root = NULL;

17. Various operations on binary trees:
Insertion
Traversal
Search
Display

18. Insertion :
temp
Now, I want to insert a “ temp “ node for the above
tree .
10
12 20
10
12
12
12
12
10

19. Insertion :
temp
if you want to insert a “ temp “ node we have to give
the direction as “ RLR “.
10
12 20
10
12
12
12
12
10

20. //Algorithm to insert an item into a binary tree based on
direction.
Step 1 : Create a node temp and insert info and null to left
and right fields
Step 2 : If empty tree return temp as first node.
Step3 : Accept the direction to insert and find the place to
insert based on direction string.
Step 4 : If proper place not found, then invalid direction
delete temp node and return back.
Step 5 : Otherwise insert node and return back.

21. //function to insert an item into a binary tree based on
direction.
NODE insert(int item, NODE root)
{
NODE temp, cur , prev;
char direction [10];
int i;
temp = getnode();
temp->info = item;
temp-> llink = temp->rlink = NULL;
if (root == NULL) return temp;
Printf(“give the directions where you want to
insert”);
Scanf(“%s”, direction);
direction = toupper(direction);

22. Prev = NULL;
Cur = root;
/* find the position to insert */
for (i=0; i < strlen(direction); i++)
{
if (cur == NULL) break;
prev = cur;
if(direction[i] == ’L’)
cur = cur->llink;
else
cur = cur->rlink;
}

23. if (cur != NULL || i! = strlen(direction))
{
printf(“insertion not possible”);
free(temp);
return root;
}
If(direction[i-1]== ’L’ )
Prev->llink = temp;
else
Prev->rlink = temp;
Return root;
}

24. Traversals :
Traversing is a method of visiting each node of
a tree exactly once in a systematic order.
During traversal, we may print the info field
of each node visited.
 
Different types of tree traversals:
Preorder
Inorder
Post order

25. Preorder traversal:
Step 1 : Process the root node
Step 2 : Traverse the left sub tree in preorder
Step 3 : Traverse the right sub tree in preorder
This can be done in two ways,
a) Recursive technique.
b) Iterative procedure.

26. // Recursive function for preorder traversal.
Void preorder(NODE root)
{
if(root == NULL)
return;
printf(“%d”, root->info);
Preorder(root->llink);
Preorder(root->rlink);
}

27. // Iterative function for preorder traversal.
Void preorder ( NODE root )
{
NODE cur, s[20];
int top = -1;
if ( root == NULL )
{
printf ( “ Tree is empty “);
return;
}
cur = root;
for ( ; ; )
{

28. while ( cur != NULL )
{
printf ( “ %d “ , cur -> info );
s[++top] = cur;
cur = cur -> llink;
}
if ( top != -1 )
{
cur = s[top--];
cur = cur -> rlink;
}
else
return;
} // end of for loop.
}

29. Inorder traversal :
Step 1 : Traverse the left sub tree in Inorder
Step 2 : Process the root node
Step 3 : Traverse the right sub tree in Inorder
This can be done in two ways,
a) Recursive technique.
b) Iterative procedure.

30. // Recursive function for Inorder traversal
Void inorder(NODE root)
{
if(root == NULL)
return;
Inorder(root->llink);
Printf(“%d”, root->info);
Inorder(root->rlink);
}

31. // Iterative function for inorder traversal.
Void inorder ( NODE root )
{
NODE cur, s[20];
int top = -1;
if ( root == NULL )
{
printf ( “ Tree is empty “);
return;
}
cur = root;
for ( ; ; )
{

32. while ( cur != NULL )
{
s[++top] = cur;
cur = cur -> llink;
}
if ( top != -1 )
{
cur = s[top--];
printf ( “ %d “ , cur -> info );
cur = cur -> rlink;
}
else
return;
} // end of for loop.
}

33. Postorder traversal :
Step 1 : Traverse the left sub tree in postorder
Step 2 : Traverse the right sub tree in postorder
Step 3 : Process the root node
This can be done in two ways,
a) Recursive technique.
b) Iterative procedure.

34. // Recursive function for Inorder traversal
Void postorder(NODE root)
{
if (root == NULL)
return;
postorder(root->llink);
postorder(root->rlink);
printf(“%d”, root->info);
}

35. // Iterative function for post order traversal.
void postorder( NODE root )
{
struct stack
{
NODE address;
int flag; };
NODE cur;
struct stack s[20];
int top = -1;
if ( root == NULL )
{
printf (“ Tree is empty “);
return;
}

36. cur = root;
for (; ;)
{
while ( cur != NULL )
{
top++;
s[top].address = cur;
s[top].flag = 1;
cur = cur -> llink;
}
while ( s[top].flag < 0 )
{
cur = s[top].address;
top--;
printf (“%d”, cur -> info );

37. if ( top == -1 )
return;
}
cur = s[top].address;
cur = cur -> rlink;
s[top].flag = -1;
}
}

38. Example :
Preorder :-> ABDGHCEIF
Postorder :-> GHDBIEFCA
Inorder :-> GDHBAEICF
A
B C
H
D
E
G
F
I

39. // Recursive function to print the tree in tree form.
void display(NODE root, int level)
{
int i;
if (root == NULL) return;
display (root-> rlink; level+1);
for( i=0; i< level; i++)
printf(“ “);
printf(“%d\n”, root->info);
display(root->llink,level+1);
}

40. //c program to create a tree and traversals
 #include<stdio.h>
#include<stdlib.h>
#include<process.h>
#include<string.h>
 
Struct node
{
int info;
Struct node *llink;
Struct node *rlink;
};
typedef struct node * NODE;
/* include all the above functions */

41. Void main()
{
NODE root= NULL;
Int choice, item, flag;
For(;;)
{
printf(“1. Insert 2.preorder 3.inorder
4.Postorder 5. Display 6.exit”);
printf(“enter the choice”);
Scanf(“%d”, &choice);
Switch(choice)
{
Case 1:
printf(“enter the item to be inserted”);
Scanf(“%d”, &item);

42. Root=insert( item, root);
Break;
Case 2:
if(root == NULL)
printf(“tree is empty”);
else
{
printf(“ the given tree is”);
printf(root, 1);
printf(“preorder traversal is”);
preorder(root);
printf(“\n”);
}
break;
 

43. Case 3 :
if(root==NULL)
printf(“tree is empty);
Else
{
printf(“ the given tree is “):
display(root,1);
printf(“inorder traversal is”);
inorder(root);
printf(“\n”);
}
break;

44. case 4:
If(root==NULL)
Printf(“tree is empty”);
Else
{
printf(“the given tree is”);
display(root,1);
printf(“postorder traversal is”);
postorder(root);
printf(‘\n”);
}
break;
 

45. Case 5 :
if(root == NULL)
printf(“ tree is empty”);
else
display(root,1);
default :
exit(0);
}
}
}

46. Examples :
write a binary tree based on the following traversals,
1. preorder : ABDEGHCFIJ
inorder : DBGEHACIFJ
2. Inorder : GHDEACBFI
Postorder :GDABCEIFH

47. Binary Search Tree ( BST ) :
A binary search tree is a binary tree in
which for each node in the tree, elements in the left sub tree
are less than root and elements in the right sub tree are
greater than root.
Ex :
100
70 110
80
60
105
20
10 60
70
40

48. Insertion:
Ex: 100, 50, 200, 90, 80, 25, 300, 150, 180, 140

49. // Algorithm to insert an item into a binary search tree.
Step 1 : Create a node temp and insert info and null to left
and right fields
Step 2 : If empty tree return temp as first node.
Step 3 : Based on info field find out the proper position
to insert temp node.
Step 4 : Insert node and return back.

50. // function to insert an item into a binary search tree
NODE insert ( int item, NODE root )
{
NODE temp, cur, prev;
temp = getnode ();
temp-> infor = item;
temp-> llink = NULL;
temp-> rlink = NULL;
if(root == NULL) return temp;
prev = NULL;
Cur = root;
while (cur !=NULL)
{
Prev = cur;

51. if(item < cur->info)
cur = cur->llink;
else
cur = cur->rlink;
}
if( item < prev->info)
prev->llink = temp;
else
prev->rlink = temp;
return root;
}

52. Searching:
// c function to search an element in BST
NODE iterative search(int item, NODE root)
{
root1 = root;
if(root1 == NULL) return root;
while(root1 != NULL)
{
if(item == root1->info)
break;
if(item < root1->info)
root1 = root1->llink;
else
root1 = root1->rlink;
}

53. if(root == NULL)
{
printf(“item not found”);
return root;
}
printf(“key found”);
return root;
}

54. Disadvantages of Binary trees & BST:
In the above two types the tree can degenerate
into a severely unbalanced one with height equal to n-1
E.g. : Binary tree Binary search tree
This can be overcome by using “AVL” trees.
10
20 30
60
50
40
100
90 200
70
40
60

55.  
AVL Trees:
AVL trees were invented in 1962 by two Russian
scientist G.M Adelson Velsky & E.M Landis.
 
 
Definition:
An AVL tree is a binary search tree in which the
balance factor of every node, which is defined as the
difference b/w the heights of the node’s left & right sub trees
is either 0 or +1 or -1 .
Balance factor = height of left sub tree – height of
right sub tree.

56. Example :

AVL tree BST ( not AVL tree )
1 2
0 1 0 0


1 -1 0 1 -1

0 0 0 0
10
5 20
2
4
7
10
5 20
2
4
8
12
7
8

57.  
If an insertion of a new node makes an AVL tree
unbalanced , we transform the tree by a rotation
 
Rotation :
A Rotation in an AVL tree is a local
transformation of its sub tree rooted at a node whose balance
has become either +2 or -2 ,if there are several such nodes, we
rotate the tree rooted at the unbalanced node that is the
closest to the newly inserted leaf.

58.  
Types of rotations :
Totally there are four types of rotations
1. Single right rotation or R-rotation
2. Single left rotation or L-rotation
3. Double right-left rotation or RL-rotation
4. Double left-right rotation or LR-rotation

59.  
Points to remember to select different rotation technique :
1. Straight line with positive unbalanced.
apply Right rotation for unbalanced node.
+2
0
+1 0 0
0

5
2
4
52
4

60.  
2. Straight line with negative unbalanced.
apply left rotation for unbalanced node.

-2
0
-1 0 0
0

5
9
7
95
7

61.  
3. Curved line with positive unbalanced.
apply left-right rotation.
Right rotation for unbalanced node and left rotation
for the nearest node.
+2
0
-1
0 0
0

5
4
3
53
4

62.  
4. Curved line with negative unbalanced.
apply right-left rotation.
Left rotation for unbalanced node and right rotation
for the nearest node.
-2
0
+1
0 0
0
5
7
8
85
7

63. Red-Black Tree
A red-black tree can also be defined as a binary
search tree that satisfies the following properties:
Root Property: the root is black
External Property: every leaf is black
Internal Property: the children of a red node are black
Depth Property: all the leaves have the same black depth
9
154
62 12
7
21

64. Height of a Red-Black Tree
Theorem: A red-black tree storing n items has
height O(log n)
Proof:
The height of a red-black tree is at most twice the height
of its associated (2,4) tree, which is O(log n)
The search algorithm for a binary search tree is
the same as that for a binary search tree
By the above theorem, searching in a red-black
tree takes O(log n) time

65. Insertion
To perform operation insertItem(k, o), we execute the insertion
algorithm for binary search trees and color red the newly
inserted node z unless it is the root
We preserve the root, external, and depth properties
If the parent v of z is black, we also preserve the internal property
and we are done
Else (v is red ) we have a double red (i.e., a violation of the internal
property), which requires a reorganization of the tree
Example where the insertion of 4 causes a double red:
6
3 8
6
3 8
4
z
v v
z

66. Remedying a Double Red
Consider a double red with child z and parent v, and let w
be the sibling of v
4
6
7
z
vw
2
4 6 7
.. 2 ..
Case 1: w is black

The double red is an incorrect
replacement of a 4-node

Restructuring: we change the
4-node replacement
Case 2: w is red

The double red corresponds
to an overflow

Recoloring: we perform the
equivalent of a split
4
6
7
z
v
2 4 6 7
2
w

67. Restructuring
A restructuring remedies a child-parent double red when the
parent red node has a black sibling
It is equivalent to restoring the correct replacement of a 4-node
The internal property is restored and the other properties are
preserved
4
6
7
z
vw
2
4 6 7
.. 2 ..
4
6
7
z
v
w
2
4 6 7
.. 2 ..

68. Restructuring (cont.)
There are four restructuring configurations depending on
whether the double red nodes are left or right children
2
4
6
6
2
4
6
4
2
2
6
4
2 6
4

69. Recoloring
A recoloring remedies a child-parent double red when the
parent red node has a red sibling
The parent v and its sibling w become black and the
grandparent u becomes red, unless it is the root
It is equivalent to performing a split on a 5-node
The double red violation may propagate to the grandparent u
4
6
7
z
v
2 4 6 7
2
w
4
6
7
z
v
6 7
2
w
… 4 …
2

70. Analysis of Insertion
Recall that a red-black tree
has O(log n) height
Step 1 takes O(log n) time
because we visit O(log n)
nodes
Step 2 takes O(1) time
Step 3 takes O(log n) time
because we perform
O(log n) recolorings, each
taking O(1) time, and
at most one restructuring
taking O(1) time
Thus, an insertion in a red-
black tree takes O(log n) time
Algorithm insertItem(k, o)
1.We search for key k to locate
the insertion node z
2.We add the new item (k, o) at
node z and color z red
3. while doubleRed(z)
if isBlack(sibling(parent(z)))
z  restructure(z)
return
else { sibling(parent(z) is red }
z  recolor(z)

71. Red-Black Tree Reorganization
Insertion remedy double red
Red-black tree action (2,4) tree action result
restructuring
change of 4-node
representation
double red removed
recoloring split
double red removed
or propagated up