Notes on protected nodes in digital search trees. (English) Zbl 1244.05055
From the introduction: G.-S. Cheon and L. W. Shapiro [Appl. Math. Lett. 21, No. 5, 516–520 (2008; Zbl 1138.05308)] started the study of 2-protected nodes in trees. A node enjoys this property if its distance to any leaf is at least 2. A simpler notion is 1-protected: exactly the nodes that are not leaves are 1-protected. In the cited paper, the family of ordered trees was considered, and it was found that asymptotically a proportion of \({1\over 6}\) of the nodes is 2-protected. Recently, T. Mansour [Appl. Math. Lett. 24, No. 4, 478–480 (2011; Zbl 1214.05009)] has complemented these results by studying \(k\)-ary trees.
In the present note, we study the analogous quantity for digital search trees, a structure that is important in computer science.
In the present note, we study the analogous quantity for digital search trees, a structure that is important in computer science.
MSC:
| 05C05 | Trees |
Keywords:
digital search treesReferences:
| [1] | Cheon, Gi-Sang; Shapiro, Louis W., Protected points in ordered trees, Appl. Math. Lett., 21, 5, 516-520 (2008) · Zbl 1138.05308 |
| [2] | Mansour, Toufik, Protected points in \(k\)-ary trees, Appl. Math. Lett., 24, 4, 478-480 (2011) · Zbl 1214.05009 |
| [3] | Knuth, Donald E., (The Art of Computer Programming. The Art of Computer Programming, Sorting and Searching, vol. 3 (1998), Addison-Wesley) · Zbl 0895.65001 |
| [4] | Flajolet, Philippe; Sedgewick, Robert, Digital search trees revisited, SIAM J. Comput., 15, 3, 748-767 (1986) · Zbl 0611.68041 |
| [5] | Prodinger, Helmut, External internal nodes in digital search trees via Mellin transforms, SIAM J. Comput., 21, 6, 1180-1183 (1992) · Zbl 0760.68037 |
| [6] | Kirschenhofer, Peter; Prodinger, Helmut, Eine Anwendung der Theorie der Modulfunktionen in der Informatik, Österreich. Akad. Wiss. Math.-Natur. Kl. Sitzungsber. II, 197, 4-7, 339-366 (1988) · Zbl 0675.68038 |
| [7] | Louchard, Guy; Prodinger, Helmut, Asymptotics of the moments of extreme-value related distribution functions, Algorithmica, 46, 3-4, 431-467 (2006) · Zbl 1117.68096 |
| [8] | Hwang, Hsien-Kuei; Fuchs, Michael; Zacharovas, Vytas, Asymptotic variance of random symmetric digital search trees, Discrete Math. Theor. Comput. Sci., 12, 2, 103-165 (2010) · Zbl 1278.68080 |
| [9] | Andrews, George E., The theory of partitions, (Encyclopedia of Mathematics and its Applications, vol. 2 (1976), Addison-Wesley Publishing Co.: Addison-Wesley Publishing Co. Reading, Mass, London, Amsterdam) · Zbl 0996.11002 |
| [10] | Flajolet, Philippe; Sedgewick, Robert, Mellin transforms and asymptotics: finite differences and Rice’s integrals, Theoret. Comput. Sci., 144, 1-2, 101-124 (1995), Special volume on mathematical analysis of algorithms · Zbl 0869.68056 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
