پیوندهای مفید
آمار
| تعداد نشریات | 15 |
| تعداد شمارهها | 239 |
| تعداد مقالات | 2,430 |
| تعداد مشاهده مقاله | 4,048,054 |
| تعداد دریافت فایل اصل مقاله | 2,939,877 |
Path length of protected nodes in random binary search trees | ||
| Journal of Discrete Mathematics and Its Applications | ||
| مقاله 2، دوره 10، شماره 4، اسفند 2025، صفحه 321-332 اصل مقاله (365.79 K) | ||
| نوع مقاله: Full Length Article | ||
| شناسه دیجیتال (DOI): 10.22061/jdma.2025.12370.1151 | ||
| نویسندگان | ||
| Ramin Kazemi* ؛ Sedigheh Zamani Mehreyan | ||
| Department of Statistics, Faculty of Science, Imam Khomeini International University, Qazvin, I. R. Iran | ||
| تاریخ دریافت: 18 مرداد 1404، تاریخ بازنگری: 29 مرداد 1404، تاریخ پذیرش: 07 آذر 1404 | ||
| چکیده | ||
| A protected node is a node that is not a leaf and none of its children is a leaf, and also a weakly protected node is not a leaf and at least one of its children is not a leaf. Let Pn and Wn be the path length of the protected and weakly protected nodes in a random binary search tree (BST) of size n, respectively. In this paper, we derive the exact mean and variance of these random variables and show that 15Pn/11n.ln n → 1 and 15Wn/14n.ln n→ 1 in probability. | ||
| کلیدواژهها | ||
| binary search trees؛ path length؛ protected node؛ weakly protected node؛ limiting rule | ||
| مراجع | ||
|
[1] M. Bona, k-protected nodes in binary search trees, Adv. Appl. Math. 53 (2014) 1–11. https://doi.org/10.1016/j.aam.2013.09.003 [2] A. M. Frieze, M. Karonski, Introduction to Random Graphs, 1st Edition, Cambridge University Press, 2016. https://doi.org/10.1017/mag.2017.110 [3] R. Kazemi, On the Zagreb index of random m-oriented recursive trees, Transactions on Combinatorics 12 (2023) 93–105. https://doi.org/10.22108/TOC.2022.132750.1964 [4] R. Kazemi, L. Meimondari, Degree distance and Gutman index of increasing trees, Transactions on Combinatorics 5 (2016) 23–31. https://doi.org/10.22108/toc.2016.9915 [5] D. E. Knuth, The Art of Computer Programming, Second ed., in: Sorting and Searching, vol. 3, Addison-Wesley, Reading, MA, 1998, Originally published in 1973. https://dl.acm.org/doi/book/10.5555/280635 [6] H. M. Mahmoud, Sorting: A Distribution Theory, Wiley, New York, NY, 2000. https://doi.org/10.1002/9781118032886 [7] H. M. Mahmoud, Evolution of Random Search Trees, Wiley, New York, NY, 1992. [8] H. M. Mahmoud, M. D. Ward, Asymptotic distribution of two-protected nodes in random binary search trees, Appl. Math. Lett. 25 (2012) 2218–2222. https://doi.org/10.1016/j.aml.2012.06.005 [9] E. Mohammad Nezhad, M. Javanian, R. Imany Nabiyyi, Weakly protected nodes in random binary search trees, RAIRO-Theor. Inf. Appl. 56 (2022) 1–8. https://doi.org/https://doi.org/10.1051/ita/2022002 [10] J. Spiess, Some identities involving harmonic numbers, Math. Comput. 55 (1990) 839–863. https://doi.org/10.2307/2008451 [11] L. Yang, S. L. Yang, Weakly protected points in ordered trees, Graphs Combin. 37 (2021) 775–788. https://doi.org/10.1007/s00373-021-02278-w | ||
|
آمار تعداد مشاهده مقاله: 425 تعداد دریافت فایل اصل مقاله: 404 |
||