Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
2014.
Series
TRITA-MAT-E, 2014:56
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-151318OAI: oai:DiVA.org:kth-151318DiVA: diva2:748258
External cooperation
Stockholm University
Subject / course
Mathematics
Educational program
Master of Science - Mathematics
Supervisors
Examiners
Available from: 2014-09-18 Created: 2014-09-17 Last updated: 2014-09-18Bibliographically approved

Open Access in DiVA

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

By organisation
Mathematics (Div.)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 197 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

urn-nbn

Altmetric score

urn-nbn
Total: 213 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf