Change search
ReferencesLink to record
Permanent link

Direct link
Asymptotic Distribution of Two-Protected Nodes in m-ary Search Trees
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
2014 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Asymptotisk Sannolikhetsfordelning for Tvaskyddade Noderi m-ara Soktrad (Swedish)
Abstract [en]

In this report, the number of two-protected nodes in m-ary search trees is studied i.e., nodes with distance at least two to any leaf in the tree. This is of interest since the protected nodes describe local properties close to the leaves of the m-ary search trees. This is done by using a generalised Pólya urn model and relating this urn model to how the tree evolves after each new key is inserted into the tree. It is proven that the number of two-protected nodes in m-ary search trees is asymptotically normally distributed when m = 4, 5, 6 which is the main result. This is in agreement with previously known results for m = 2, 3, which were obtained by using the same approach. The method and algorithms are

presented in such a way that it simpli_es calculations for larger m. Based on the results for m = 2,…, 6 conjectures are made providing a possible way to extend these results for larger m < 26.

Abstract [sv]

I detta examensarbete studeras antalet tvåskyddade noder i m-ära sökträd. En nod kallas tvaskyddad ifall den ar minst två kanter fran ett löv i trädet. Dessa noder är av intresse eftersom de beskriver lokala egenskaper nära löven i de m-ära sökträden. Detta studeras genom att använda en generaliserad Pólya urna och genom att relatera denna urna till hur ett m-ärt sökträd expanderar när nya nycklar placeras in i trädet. Det bevisas att antalet tvåskyddade noder i ett m-ärt sökträd har en asymptotiskt normalfördelad sannolikhetsfördelning för m = 4, 5, 6 när antalet nycklar i trädet går mot oändligheten. Detta stämmer överens med tidigare resultat för m = 2, 3, som har bevisats genom att använda samma metod. Metoden och algoritmerna som används för att beräkna dessa resultat presenteras på ett sådant sätt att de går att applicera på större m utan modifiering. Givet resultaten för m = 2,…, 6 presenteras en möjlig väg för att expandera dessa resultat för större m.

Place, publisher, year, edition, pages
TRITA-MAT-E, 2014:56
National Category
URN: urn:nbn:se:kth:diva-151318OAI: diva2:748258
Subject / course
Educational program
Master of Science - Mathematics
Available from: 2014-09-18 Created: 2014-09-17 Last updated: 2014-09-18Bibliographically approved

Open Access in DiVA

fulltext(580 kB)116 downloads
File information
File name FULLTEXT01.pdfFile size 580 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Mathematics (Div.)

Search outside of DiVA

GoogleGoogle Scholar
Total: 116 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 116 hits
ReferencesLink to record
Permanent link

Direct link