suppose MODI goverment asked the family planning commission of india to put limit on having child's (due to rise in the population). assume the planning commssion announced
that a family can have maximum 'N' child.. (it does not means that every1 should have 'N' child's they can have less also //rules for that r mentioned below)now they also posted a
ban that there must be a gap of 1 year between every child(having twin childs & tetra(3) packs are strictly banned ).
child1 |
gap1 |
child2 |
gap2 |
child3 |
gap3 |
child4 |
CONSIDER N= 4 to have four child their must be 3 gaps of 1-1-1 year
They also mentioned some rules for various persons that how many childrens they can have..
1) head of family(assume head as 1st person on earth & it should be female ) can have minimum 2 child's and maximum 'N'(i.e 4 child's as we considered N=4)
2) successors(children' s of head) can have minimum ceil N/2(i.e ceil 4/2 = 2) & maximum N (i.e 4 child's )
3)tail enders(last generation of head) decided they don't want to marry they want to acquire celibacy(bramcharya)....so they don't have any child's
now the time between the two child's of 1 year also called here GAP...in that gap family decided to donate money(may be they want 2 thank god for giving them child)
they have deposited the money in the bank ...the money is saved in box as bundels of 100 rs..then 500 ...then 1000 etc....(order is important )
now in gaps family provides the INFORMATION of first bundulls of notes in the box (here 100) and also the PATH to them...so that they can access...if they can access 100 rupee.....note then they can also access 500 rupee note...etc sequentially..in same box
now rules for having information and path ....
note:-any node can have path///
1) head of family can have minimum one information & 0 PATH and maximum N-1 information and N-1 path
2) successors can have minimum ceil N/2-1 (i.e 4/2-1=1) & 0 path and maximum N-1 information & N-1 Path
3)tail enders can have minimum ceil (m-1)/2 (i.e (4-1)/2=1.5=>2) information & 0 path & maximim N-1 path N-1 information
child1 |
info, path |
child2 |
info2,path2 |
child3 |
info3,path3 |
child4 |
one more rule tail enders should be at same level....
now consider b-tree
here 'N' is the order*(max child)of b-tree the & it will be given in question...as planning commission fixed the number child a family can have i.e 'N'
1) ROOT whch is earlier called (head) can have minimum 2 child's and maximum 'N'(i.e 4 child's as we considered N=4)
2)INTErNAL NODES which is earlier successors(children' s of head) can have minimum ceil N/2(i.e ceil 4/2 = 2) & maximum N (i.e 4 child's )
3)LEAF NODES tail enders(last generation of head) zero child's
INFORAMTION= KEYS ....PATH== DATA RECORD POINTERS ////keys & data record pointers are different
child1 |
key1,record pointe1 |
child2 |
key2,recordpointer |
child3 |
key3,recordpointer4 |
child4 |
anybody can give path/// means anybody can have record data pointers...it does not means every should have record pointers..
money stored in the bank is same data stored in memory.. and saved box is as same record saved in blocks ...100 rs notes is same as the first record of the block which is considered as KEY in the b-tree ...and sequentially they can access next record..of same block....
.one thing must be noted here
1) ROOT (head) can have minimum one KEY (INFORMATION) and zero (DATA RECORD POINTERS) PATH and maximum N-1 KEYS i(nformation) and N-1 DATA RECORD POINTERS ( path)
2) successors can have minimum ceil N/2-1 (i.e 4/2-1=1)KEYS zero DATA RECORD POINTERS and maximum N-1 KEYS & N-1 DATA RECORD POINTERS
3)tail enders can have minimum ceil (m-1)/2 (i.e (4-1)/2=1.5=>2) KEYS & zero DATA RECORD POINTERS & maximim N-1 KEYS & N-1 DATA RECORD POINTERS
1)if we have INFORAMTION then only we can have PATH...i.e if we have keys...then only we can have data record pointers ....
2)we can also have keys alone in the node ...
3) data record pointers are not allowed alone..keys must be there with them...
leaf nodes should be at same level....