On 2-protected nodes in random digital trees

檔案

本條目沒有附加檔案。

至出版者網站查看(DOI) ›

日期

2016-04-04

期刊名稱

THEORETICAL COMPUTER SCIENCE

卷期與頁次

第 622 卷,頁 111–122

ISSN

0304-3975

語言

英文

摘要

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Fuchs, M., Lee, C. K., & Yu, G. R. (2016). On 2-protected nodes in random digital trees. THEORETICAL COMPUTER SCIENCE, 622, 111–122. https://doi.org/10.1016/j.tcs.2016.02.007

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/133423