[go: up one dir, main page]
Scribd
Upload
31 views4 pages

B Tree

Uploaded by

Himanshu Tyagi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
31 views4 pages

B Tree

Uploaded by

Himanshu Tyagi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 4
BHURee on) asst is AGOb er) > A Betvee Ts a footed chee (whese having. ave fe ollowing. pRoperdtes ae 0) Srey rede > har Lhe folloiny fields »- stowed fr necle x ® vfxd | the yo: ( keys ewnraedy wy decreasing ® the nlx] Keys poomeelves , slowed tn ne Ovdey , &e {rot Keys Or) S KyaG & key 09 <= eA Key ag GQ Leaf lr], a boolean valve. fs TRUE of fsa wee a false uf x fs an brtethal node. le algo contains nfa)+) Points ® Each Internal ne [x] fo is clitdyen. abi, ene] . ie Cupgay Leaf podes have no clildyen , S° fusiy c¢ fille aie ercier Unde Rrect + @ -the veye Key p(x) separate phe ~winge Keys Atored Pe er bee ul esc Gite) fan Ki < Koy, txJ $k SF Key 20x] < ~- Ske yy gOS Knee @ pel tenves have Brie Kame depth, which fe Ke tree's beige A. ©] There are lower. and upper. bounde en tte No- 4 i node can contatn These bounds ard expressed fy terms of a Aired énteger t 5% so ter called fre minimum degree af the @ tree @® every node other fran kre eet must have at leask (E-1) keys. _ Every Crlesnel node other. Bhan gue geot hod atleast £ clikdren TF fe tree Fs noremply , the aoot must howe af least ort ky ® Cvory nede Can Contam at most 2t-! keys» Thets fre, an internal node Ginhave atmost 2t clildvens We say Ret a node Ps full ef it containg exactly os voot (T] - sthesaem te if nop}, heh for ng ne Keays 6-Tree T ot hoigt £, and mintmum hegre oes isa) Prevod! the veot contuné abteast erw kay ARL atheh redef contein atleast Jal) kegs . Thee wed atlest 2 nodes ot debth 1 atleact 2t nodes ok dapth 2, atleast 24! jodes gt dopth & ond and pe pedel at chepath f- — Bree of Wirt — 3 1 | OC rte wt -- oe) oS 471 ree 2(t-OCIt ert t rye 4 = eof G4 yr 26 of e-Y) n= pt a 2 ow oe Taking Seq of beth idee, we get ae egy Cm — theosm!- Let T be a B-Twee % order ‘mn’ and wigs 4. | oy tek def | and tet nbe se me of Elrnerls nT (ee ere ‘nth ze (i) log, any oh < \y a(t) +1 {’ woe ae Ges” cy Mintmym no- Cy nodes on levels 1,2, 24 BH fs 2,2, 2d, a ae amd he maxtmurs a mPol The no- 4 null pairdets ° a Mo (c 2m Ie : = nt) h-\ 4 — 2. Dg a ae ay Let pah ly Zn aah! enti 4-4 a c+) £Q%)- be tl s1cles Taking &y G-1) toy ya a (ga(2#) AK toga (at!) +1 New nz mn | hay vn © aking lo both side [59 mn)

You might also like