SwePub
Sök i LIBRIS databas

  Utökad sökning

onr:"swepub:oai:DiVA.org:uu-112234"
 

Sökning: onr:"swepub:oai:DiVA.org:uu-112234" > Novel Characteristi...

Novel Characteristics of Split Trees by use of Renewal Theory

Holmgren, Cecilia, 1984- (författare)
Uppsala universitet,Analys och tillämpad matematik
 (creator_code:org_t)
2012
2012
Engelska.
Ingår i: Electronic Journal of Probability. - 1083-6489. ; 17, s. 5-
  • Tidskriftsartikel (refereegranskat)
Abstract Ämnesord
Stäng  
  • We investigate characteristics of random split trees introduced by Devroye [SIAM J Comput 28, 409-432, 1998]; split trees include e. g., binary search trees, m-ary search trees, quadtrees, median of (2k + 1)-trees, simplex trees, tries and digital search trees. More precisely: We use renewal theory in the studies of split trees, and use this theory to prove several results about split trees. A split tree of cardinality n is constructed by distributing n balls (which often represent data) to a subset of nodes of an infinite tree. One of our main results is a relation between the deterministic number of balls n and the random number of nodes N. In [5] there is a central limit law for the depth of the last inserted ball so that most nodes are close to depth lnn/mu + O(root lnn), where mu is some constant depending on the type of split tree; we sharpen this result by finding an upper bound for the expected number of nodes with depths >= lnn/mu - ln(1/2+epsilon) n or depths <= lnn/mu + ln(1/2+epsilon) n for any choice of epsilon > 0. We also find the first asymptotic of the variances of the depths of the balls in the tree.

Ämnesord

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)
NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

Nyckelord

Random Trees
Split Trees
Renewal Theory
Discrete mathematics
Diskret matematik
Mathematics
Matematik

Publikations- och innehållstyp

ref (ämneskategori)
art (ämneskategori)

Hitta via bibliotek

Till lärosätets databas

Hitta mer i SwePub

Av författaren/redakt...
Holmgren, Cecili ...
Om ämnet
NATURVETENSKAP
NATURVETENSKAP
och Matematik
och Diskret matemati ...
Artiklar i publikationen
Electronic Journ ...
Av lärosätet
Uppsala universitet

Sök utanför SwePub

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy