Trees - Discrete Mathematical Structures, Engineering Mathematics Video Lecture - Engineering Mathematics | Best Video for Engineering Mathematics

ah ha ha ha
[Music]
Oh
[Music]
[Music]
you
you
so today we shall consider about trees
and search trees a tree is a digraph
with a non-empty set of nodes such that
there is a exactly one node called the
root of the tree which has degree 0
every node other than the root has in
degree 1 for every node a of the tree
there is a directed path from the root
to a so a tree has a structure something
like this there is a root which has got
in degree 0 and you may have other nodes
like this this is a tree
these are called leaves the other nodes
are called internal nodes
for every node there is a directed path
from the root to the tree now following
are not trees consider this if you have
something like this this is not a tree
because you are having two nodes with in
degree 0 so that is not a tree and look
at this this is also not a tree because
you have a root node out but this node
has in degree 2 and so this is not a
trick and similarly if you take
something like this directed in this
manner this is not a tree because there
is no node within degree 0 there is no
root at all in this so this is not a
tree so a tree has something it has a
structure something like this and you
may have more and more levels you may
have something now for this node these
are the sons say if I label them as a b
c d e f g h i j k c then for C F G H are
the sons and for I H is the father for D
and E D is the father and so on a has to
since B and C C has three sons and so on
now a is an ancestor of AI ancestor of
AI
it in the path it comes before I from
the road see is also an ancestor I use
called a descendant descend and look at
this portion this is called the sub tree
and the sub tree has root at C similarly
you have a if you take this this is a
sub tree and this sub tree has a root at
B so these are some of the terminologies
associated with three and generally when
you draw a tree you do not draw the arcs
you just draw a tree like this
the star like this
it is supposed to be directed in this
way and this is the route now what is
the height of this tree the height of
the tree is the length of the longest
path length of the longest path from the
root longest path to a leaf from from
the root this is called the height of
the tree so look at this the height of
this tree is three height of this now
the root is supposed to be at level zero
these three nodes are at level one this
is these three nodes are at level two
these two are at level 3 the height is
three so these are some terminologies
associated
with a dream
now let us consider this let t be a tree
with root R and a B any node of the tree
then there is a unique directed path
from R to a you have a treaty something
then by definition there is a path a is
any node there is a path to a from the
root but we want to show that that is
unique there is a unique path how do we
prove that that there is a path from
directed path from root to a is clear by
definition it is there and it is also a
simple path can very easily see that it
is a simple path but that path is unique
how do we prove that you can prove by
induction proof by induction
you have a three say some tree like this
it is only a small tree I have drawn but
generally any tree and let s n denote
the set of nodes
fetch that such that if a belongs listen
then the length of the path from Row
three the length of the path from root
to a is less than or equal to n now the
basis class we can prove like this is
zero means it is only the root for the
root there is only a one path of length
zero from itself to itself so that that
is unique if you take s 1 it denotes
nodes which are sons of the root and you
can very easily see that there will be
only one directed path here the path is
unique to that so that is ok now
induction portion
assume that the result is true up to s
my N minus 1 that is up to s SN minus 1
that is if the node is such that the
length of the path from the root to that
node is risen or equal to n minus 1 then
there is a unique directed path from the
root to that node then prove for n here
to prove for n so suppose a belongs to
SN there are two possibilities one is a
belongs to SN minus 1 that is the length
of the path from the root to a is less
than or equal to n minus 1 then by the
induction hypothesis the result hold the
thing is a does not belong to s n minus
1 that means the path from the root to a
is of length n from root the path 3 a is
of length n of length n that means there
is a path like this root for some node
and then to this node
this is a some node B this path is of
length n minus 1 and from T V to a you
have a path suppose this path is not
unique there can be another path say if
there is another path then the in degree
of this will be 2 but you can have only
in degree 1 for this node a so from this
will have only in degree 1 means there
is only one arc like this entering into
a and this node B will belong to SN
minus 1 that is the length of the path
from the root to this node is of length
n minus 1 and this path is unique so
this path is scenic so like that you can
prove and and by induction hypothesis
the result is proto now arithmetic
expressions you can express as trees let
us consider some arithmetic expression
and see how they can be represented as
please look at this tree where the
internal nodes represent operators plus
star star some 4 5
-
six-two
plus 7/5
what does this tree represent this tree
represents an arithmetic expression and
you can write it like this 4 star 5 star
6 minus 2 that is this portion and it
should be added to 7 plus 5 this
arithmetic expression is represented as
a tree like this now how do you evaluate
this level by level you can evaluate so
if you try to evaluate this 4 star 5 is
20 so this will be plus Star Plus and
here the evaluation gives you 20 and
here 6 minus 2 gives you 4 and plus 7/5
you have
so this gives you this evaluates to 20
into 480 and 7 plus 5 is 12 now this
evaluates to 80 plus 12 92 so there is
metric expression evaluates to 92 this
is the way in the compiler a compiler is
a larger program which translates a
machine language in which translates a
source language a high-level language
into a machine code and there are two
parts of the compiler one is the
analysis part and another is the
synthesis part in the analysis part the
source program is analyzed and kept
inside the computer I say the internal
form the internal form could be a triple
or quadruple or a three or a four six
notation some three fixed notation and
something like that let us see what this
postfix notation prefix notation a
little bit later now when it is
represented inside the computer like
this in the internal form and then the
code is generated but essentially the
evaluation is done in this manner and
for that the core proper code is
generated you will learn more about
today the compiler is any design theory
course but the main point to note is
that arithmetic expression is
represented can be represented as a tree
like this and
and the internal nodes are operators
these are numbers or variables whatever
it is it could be something like a b and
then the a can be given a particular
value b can be given a particular value
and so on
now you will see these points very
clearly every directed path in a tree is
a simple path because there are no node
will be repeated there are no loops on
the nodes there are no self loops the
nodes and a tree has no directed simple
cycles of nonzero length so if you have
a tree like this and you should be do
not write the direction of the arcs
explicitly but without them be right but
suppose you also draw the arcs look at
this every path is a simple path and
there are no self loops there is no
directed cycle and
the other thing is every the only cycle
undirected simple cycles of nonzero
length are of length - that is between
these two suppose you have some arc like
this a B you can look at it as a
undirected circle ABA can look at it as
an undirected cycle ABA that is what is
said by the step this is not a major
point the point is there are no cycles
here there are no self loops and every
path is a simple path
now when you look at a tree like this
this has two sons this also has two sons
this has the reasons this has the
reasons this is a ternary tree a ternary
tree will have three each node will have
three sons two sons one son our zero it
will not have more than a no node will
have more than results when you look at
a binary tree this is a binary tree this
is a binary tree each node will have two
sends one Sun are zero sense the leaves
have zero sons this node has got one son
this has got two sons this has got two
sons and so on no node will have more
than two sense that is called the binary
tree in general enery tree means each
node will have n sons are less now what
is a complete n array 3 n re tree means
each node will have
and I sense I can vary from zero to a
complete inner a tree
a complete enery tree means each node
has zero or n cents so if you take the
root it will have say it can have n sons
and if you take any other node it can
have n sons other basically be a leaf
this is called a complete indirectly
what is a complete binary tree complete
binary tree each node has zero or two
sons for example look at this this is a
complete binary tree look at this tree
this is also a complete binary tree look
at this this is not a complete binary
tree because this node has only one Sun
so this is not a complete binary it is a
binary tree but not a complete binary
tree so binary trees are very much used
for search purposes ternary trees are
also used let us see how we can use
binary tree search search trees before
that what can you say about the height
of a binary tree so some results about
the height of the binary tree if T is a
binary tree of height H and with n nodes
then n is between h plus 1 and 2 power h
plus 1 minus 1 moreover there exist
binary trees in which these bones are
attained how do you prove that
you have a binary tree say let me draw
binary see this is a binary tree say how
many nodes are there 1 2 3 4 5 6 7 8
nodes are that what is the height of the
3 3 n is 8 H is 3 here this example now
in general n is between h plus 1 and 2
power h plus 1 minus 1 in the worst let
us consider the worst case scenario you
can have a binary tree like this a
binary tree will have fit has two sons
like this a node has two sons this is
called the left's and this is called the
right son so you can have a tree like
this where there are no right sense at
all then what is the number of nodes
here n is 4 here and hey cheese 3 so n
will the worst case n n can be H plus 1
this is
the one the other way around every node
has got thousands X so at every level so
you may have a tree like this a binary
tree sometimes this is called that this
is a complete binary tree but the this
is a this is a complete binary tree with
height head 3 this is also complete
please remember that this is also a
complete binary tree to distinguish
between complete binary trees like this
and this sometimes this is called a
called a full binary tree but that is
not a very common terminology some books
use that notation so what is the number
of nodes here the number of nodes is 15
n is 15 and H is 3 so what is to power h
plus 1/2 power h plus 1 is 15 16 and to
power h plus 1 minus 1 is 50 so in this
case you get the maximum number of nodes
with that for this site for hi 3 the
minimum number of nodes you can get is
for the maximum number of nodes you can
get is 2 power h plus 1 minus 1 15 you
can have we can also get like if the
height is H at level 0 you have one node
at level level 1 you have 2 at level 2
you have 2 square nodes at level 3 you
have 2 cubed and so on so in general if
the height is H if the height I will
write it here height is H you will have
so maximal node you can have is like
this it is a geometric series some and
it will sum up to 2 power H plus 1 minus
so we have this result and the next one
is a binary tree with no n nodes the
height is at least log n that you can
very easily see if say for the 7 nodes
you can have high 2 3 4 8 nodes the
minimum will be 3 4 9 nodes the minimum
has to be 3 4 15 nodes you can have a
tree with height H for 16 nodes you will
have minimum height is required is 4 if
you have 16 nodes there should be
something like that at one position the
height will become 4 so we can very
easily say that if there are n nodes the
minimum height of the tree will be log n
taking the floor function now all these
things we have seen but how do you
formally define a binary tree how do you
de forma Li define a binary tree
formal definition you can we have seen
that sets can be defined inductively so
we can use an inductive definition to
define a binary tree so the basis part
will be the root node alone like this a
single node single node is a binary
now the induction class you write like
this t1 and t2 are binary trees already
constructed with roots r1 and r2
respectively
then have a new node R take a new node R
then R we can arc to r1 along with t1
this is a binary tree then R with a
right arc to R 2 and the 3 T 2 this is a
binary tree and our along with an arc to
r1 and an r2 r2 with the 3 T 1 and with
the 3 T 2 this is also a binary tree so
the basis class is you take a single
node that is a binary tree with no arcs
and if you have two binary induction
classes depending this if you have two
binary trees t1 and t2 with roots r1 and
r2 respectively taken you know R then R
along with an edge like this and t1 is a
binary tree on along with an edge like
this 2 R 2 and T 2 is a binary tree R
with an edge to directed edge from r2 r1
and r2 r2 along with this t1 and t2 like
this is a binary tree of course when you
define a set inductively you have to
also use what is known as the extremal
class so here we have to mention the
extremal class earlier we have seen that
the extremal class is the same for all
that is all binary trees can be obtained
engine
and nothing else will be obtained so
this is the formal way of defining a
binary tree now these binary trees are
generated they are very useful in
database and they are used as search
trees
data is stored as a record a record will
have several fields for example you have
a record say it will have several fields
for an example employee in a company you
want to store the records of all the
employees if you have employee number
name department whatever it is something
like that if you take us and all you may
also have social security number name
and so now when you want to search for
some record it is better if it is the
records are stored in the form of a tree
so that the search takes less amount of
time if you have it as a linear record
one by one you have to search and it
will take lot of time here we have seen
that you can when you have n nodes the
height can be log in so we can very easy
in log and time you can search whereas
if you store it as linear the card you
will require search time n now when you
want to search you have to search
through a key what is known as a key the
key should be any unique for each record
for example if it is a department number
or something there may be so many
employees in a department so that cannot
serve as a key whereas if you take the
social security number of a person that
is applicable in u.s. that is unique and
in a company or in I even even I eighty
if you take each person has an employee
number employee identity that is unique
no two person will have the same
employee number so you can sure
according to that a employee number
which is serves as the key and you
sought you store the records and you
have to search through the key and you
may use ternary trees or binary trees
first
we see how you can show records using
binary trees for simplicity let us
consider only some integers how we can
let us take only integers there are two
ways of storing their records further as
an example you have this
number 37
five-three
then
eight
each record is stored in a node of the
tree this is the tree and each record is
stored in the node internal node or leaf
so if I want to search whether 9 is
present how will I go about searching
first you go to the root all elements
less than 7 will be in the left subtree
all the element greater than 7 will be
in the right subtree so suppose I want
to search for 9 I go to the root I find
that 7 is less than 9 so the next search
I have to do in the right subtree so you
go here and here when ac-9 9 is less
than 10 so here I have to go to the left
subtree and here I find 8 9 is not that
so that record is not formed now you can
add that 9 here 8 is stored here so if
you want to add a 9 you have to add like
this 9 is greater than 8 so it has to go
to the right subtree of this but then
the there will be some balancing also
done ci next one if you add suppose I
want to add 14 I have lied like this
then 16 I have to add like this the
height of the tree will keep on
increasing so there some balancing also
will be then that will be explained in
the data structures course you'll learn
about that in the data structures course
the main idea is 3 as a structure how it
is used so you can store the record in
each of the nodes and you can search
like this each node will contain the key
value and if you are going to search for
a value which is less than that you have
to go to the left subtree all the nodes
on the left side subtree will have
values less than that and all the nodes
on the right
subtree will have values greater than
that this is a way data are stored
another way of storing is you store the
records only at the leaves and in the
internal nodes you store discriminating
values they are called discriminators
discriminators the records are stored
only at the root let us see how this is
done
take this
the leaves toward the values
the same values we can take it in halva
3/5
so
the values are showed like this the road
will contain a discriminator it could be
something like eight now all values
greater than or equal to eight will be
stored on the right sub thing they are
sold at the leaves all values greater
than or equal to eight are stored in the
right subtree now in this node you must
have a discriminator which tells you
what are the things which should go to
this something like say you can have
twelve here all values greater than or
equal to twelve will go to this subject
and here you can have something like 13
so the value 12 is on this side if the
value is 13 or more it will be on the
right subtree and here you can have a
value like say some 10 this is a
discriminator all values less than 10
will be going to the left subtree
greater than or equal to will go to the
right sub there is no right subtree here
if you have a like record say 11 it will
go here 10 or 11 it will go here and
similarly in this street the left this
value is 3 4 3 5 so you can have a
discriminator 4 here all values greater
than or equal to 4 will go to the right
subtree all values less than 4 go to the
left subtree and here you can have
something like 6 so all values less than
6 go to this subtree all values greater
than or equal to 6 go to the right
subtree but in this case the values are
stored only at the leaves and the
internal nodes contain the
discriminators this is one way of doing
so there are two ways of storing the
records and we have seen how to do that
with binary
please let us consider ternary trees
where the values are stored at the
internal not a data note but only at the
lease this ternary trees are also
frequently used
each node can have two or three sets
so here we can have three it can have
two sons or three sons now again this
can have say this has three sons and
this has two sons this we can take as a
leaf separate and this may have leaves
like this
this may have say three sons like this
this has got one son
and
some records you store here let us see
how they extol
- for
7 10 12 15 20 21
and here
25
thirty thirty to thirty seven something
like that
now when you have three sons this node
will have two discriminators the first
one here in this case it can be
something like 21 all values which are
equal to 21 and the next value X a less
than X we'll go to the middle subtree
here from 25 we can we are having so I
can have something like 23 so all values
which are less than 21 will go to the
left subtree which are equal to 21 and
greater than 21 but less than 23 will go
here which are greater than are equal to
23 will go to the right subtree the
third three and if a node has this two
sons as in this case there will be only
one discriminator here so the least
a31 a32 and 37-year have so one value
can be 31 all values less than 31 will
go here all values greater than or equal
to 31 will go to the subtree now here
you are having 25 and 30 maybe I should
draw it in a slightly different way so
that the left and the right are clearly
seen so here I should have a value such
that it should be more than 25 and less
than or equal to 30 something like 27 I
can have so that the lesser value go to
the red subtree and the right greater
than or equal to value goes to the right
subtree here also we can have there are
only two since so I can have a value say
something like 35 here so that values
less than that if I go here to the left
subtree and I'll just greater than or
equal to that if I go to the right
subtree now this has got three sons so
there should be two discriminating
values here
and the values the middle subtree
contains seven and ten so I can have
something like six here so all values
greater than or equal to six but less
than say twelve go to this subject and
all values greater than or equal to 12
go to the right subtree now look at this
this again has got three sons so here
that there should be two discriminating
values I can have something like 14 and
17 all values less than 14 will go to
the first 3 all values greater than or
equal to 14 but less than 17 we'll go to
the middle subtree greater than or equal
to 17 we'll go to the right side so the
discriminating values we have to choose
something like this here there are only
two sons so I can choose a
discriminating value like this and here
there are only two since they can choose
a discriminating value like this so the
internal nodes only contain the
discriminating values if it has got
three sons it will have two
discriminating values and if it has got
two sons it will have only one
discriminating value so this ternary
trees sometimes they are called a 2 3
trees and this type of a tree is called
a 2 3 3 each node can have two are
recents and it is somewhat this is not
balanced but all the leaves in some
cases you expect all the leaves to be at
the same level in that case it is called
a balanced tree so in general you would
like to have balanced trees and the data
should be stored at the leaves and the
internal nodes will have discriminating
values
this is the main use of trees as a data
structure
next let us consider binary six binary
trees and the way you can search through
the traversal it can can say traversal
method
suppose I have a tree like this
have a tree like this where the nodes
are denoted as a b c d e f g h say there
are three methods in which you can
travel the nodes one is called the
pre-order traversal another is called
the inorder traversal and third is
called the postorder traversal in the
pre-order traversal process the route
are R of the T then if the left subtree
exists then process T 1 in pre-order and
if T 2 exists then process T 2 in
pre-order T 2 is the T 1 is the left
subtree and T 2 is the right subtree
so this is the tree you are having with
node labels a b c d d e f d h
and if you want to traverse the tree in
the pre-order in what order you will
search
the road first then the left subtree
then the right subtree so let us see how
the nodes are Travis in the preorder
marry manner industry so know da will be
visited first then these four nodes will
be visited then these three nodes and in
these four nodes also you should follow
the preorder method the route first the
left subtree and the right subject so B
will be visited first then the left
subtree is this D then the right subtree
E and G have to be visited and here
again you have to follow the preorder
traversal method is the route first left
subtree and the right subtree there is
no right subtree here so E and G
similarly the right subtree also should
be visited in the preorder manner the
route there is no left subtree then the
right subtree so C no left subtree and
the right subtree in the right subtree
again should be visited in the preorder
manner root first left subtree and the
right subtree this F and H so the nodes
will be visited in this order in the
preorder traversal let us see how the
nodes will be visited in the inorder
traversal in order in the inorder
traversal first the left subtree is
visited and that is also visited in the
inorder manner if t1 exists then process
t1 in in order then process the root
then the third one is if t2 exists then
process t2 in in order so in the inorder
traversal left subtree first then root
right subtree so if you want to traverse
this particular tree in the inorder
method in what order will the root will
the nodes we visited first the left
subtree then the root then the right
subtree
and the left sub-tree itself should be
visited in the inorder manner first left
subtree then droop then right subtree
that is d first then be next then these
two and these two again should be
visible in added manner left subtree
root right subtree so G and E will be
you sit in that order now look at the
right subtree this also has to be
visited in the inorder method that is
left subtree root right subtree there is
no left subtree so C will be visited
next then the right subtree and this
right subtree again has to be visited in
the inorder manner so h first then f
then if there is something in the right
subtree there is no sir right subtree
here so it will be h and yeah so the
nodes will be visited in this order in
the inorder traversal method there is
one more method called the postorder
method in the postorder method the left
subtree is visited first then the right
subtree then the so the postorder method
if t one exists then process t one in
post order then if T two exists then
process T two in post order third
process the root node R of that T so
take the same example and if you want to
traverse using post order traversal in
what order the nodes will be visited
first the left subtree then the right
subtree then the root so a will come at
the end the left subtree itself if you
take first the left subtree then the
right subtree then the root so b then
the right subtree that again will be
visited in the post order method so g if
there is something here then
there is nothing here so it will be G
and E then B so in this subtree the
nodes will be visited in this order the
G a B and next the right subtree has to
be stated that also has to be done in
the first order method that is for this
one there is no left subtree right
subtree has to be visited first then the
root so C will come here and this one
again it has to be visited in the post
ordinate that left subtree right subtree
root so there is no right subtree so H
yes so the nodes will be visited in this
order so for binary trees you talk about
these three methods of traversal in
order preorder and postorder now if you
have the sequence of nodes visited in an
inorder method and the pre-order method
from these sequences you can construct
that similarly if you have the sequences
corresponding to in order and post order
you can construct the tree in a unique
manner but if you have the sequence
corresponding to preorder and postorder
you cannot construct the tree in a
unique manner for example I have a four
nodes like this say
ABCD
the in order will be free order will be
here will be a-b-c-d in order will be B
a B C from this you can construct the
tree in a unique manner how can you do
that suppose I do not have this I do not
have this how can you construct the tree
the preorder a is the first so a is the
root in the in order a is the root so
whatever is appearing on this side is
the left subtree and this on that right
subtree so b is on the left subtree
there is only one node so it has to be
like this on the right subtree you have
C and B and C and D have to be the right
subtree the first one will be the root
of the right subtree so C will be here
and where will be D D can be here or
here right but this tells you that in
the inorder left subtree first then root
then right subtree that means d has to
be the left son here so you can draw
like this so from pre-order and inorder
you can draw the tree in a unique manner
but you cannot do that if you have
preorder and postorder for example if
you have something like this
ABCD what is the pre-order the pre-order
is ABCD the postorder is
DC VA from if you are given this this
the tree can be like this or it can be
like this also on ABCD what is the
pre-order for this ABCD postorder is DC
ba so the tree can be this are this so
from these 2 sequences you cannot
construct the tree uniquely whereas if
you are given in order or pre-order
in-order and preorder are in order and
post order you can construct the tree in
a unique manner and if you look at the
expressions are thematic expressions the
use of it will be very clear now we can
see how these are these traversal
methods are useful when you look at the
trees as arithmetic representing
arithmetic expressions we can also see
some of the other concepts about trees
like spanning trees weighted spanning
trees etc in the next lecture
[Music]
you
[Music]
you
[Music]