標題: On 2-protected nodes in random digital trees
作者: Fuchs, M.
Lee, C. -K.
Yu, G. -R.
應用數學系
Department of Applied Mathematics
關鍵字: Data structures;Digital trees;Analytic combinatorics;Moments;Limit theorems;Abel summability
公開日期: 4-Apr-2016
摘要: In this paper, we consider the number of 2-protected nodes in random digital trees. Results for the mean and variance of this number for tries have been obtained by Gaither et al. (2012) [11] and Gaither and Ward (2013) [10] and for the mean in digital search trees by Du and Prodinger (2012) [5]. In this short note, we show that these previous results and extensions such as the variance in digital search trees and limit laws in both cases can be derived in a systematic way by recent approaches of Fuchs et al. (2012; 2014) [8, 15] and Fuchs and Lee (2014) [9]. Interestingly, the results for the moments we obtain by our approach are quite different from the previous ones and contain divergent series which have values by appealing to the theory of Abel summability. We also show that our tools apply to PATRICIA tries, for which the number of 2-protected nodes has not been investigated so far. (C) 2016 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.tcs.2016.02.007
http://hdl.handle.net/11536/133423
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2016.02.007
期刊: THEORETICAL COMPUTER SCIENCE
Volume: 622
起始頁: 111
結束頁: 122
Appears in Collections:Articles