The height of depth-weighted random recursive trees

被引：2

作者：

Leckey, Kevin ^{[1
]}

Mitsche, Dieter ^{[2
,3
,4
]}

Wormald, Nick ^{[5
]}

机构：

[1] Tech Univ Dortmund, Fac Stat, Dortmund, Germany

[2] Inst Camille Jordan, Villeurbanne, France

[3] Univ Lyon, Lyon, France

[4] Univ Jean Monnet, St Etienne, France

[5] Monash Univ, Sch Math, Melbourne, Vic, Australia

来源：

RANDOM STRUCTURES & ALGORITHMS | 2020年 / 56卷 / 03期

基金：

澳大利亚研究理事会;

关键词：

random trees; random recursive trees; height;

D O I：

10.1002/rsa.20901

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this paper, we introduce a model of depth-weighted random recursive trees, created by recursively joining a new leaf to an existing vertex v. In this model, the probability of choosing v depends on its depth in the tree. In particular, we assume that there is a function f such that if v has depth k then its probability of being chosen is proportional to f(k). We consider the expected value of the diameter of this model as determined by f, and for various increasing f we find expectations that range from polylogarithmic to linear.

引用

页码：851 / 866

页数：16