پیوندهای مفید
آمار
| تعداد نشریات | 13 |
| تعداد شمارهها | 237 |
| تعداد مقالات | 2,406 |
| تعداد مشاهده مقاله | 3,888,047 |
| تعداد دریافت فایل اصل مقاله | 2,826,474 |
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 $$\frac{15 Pn}{11n\ln n}\to 1$$ and $$\frac{15W_n}{14n\ln n}\to 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, TOC. 12(2) (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, TOC. 5(2) (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. https://www. semanticscholar .org/ paper/ Evolution-of-random-search-trees- Mahmoud/ 965a46ba9d339bad3afde4b1468a60ed99c1725e [8] H. M. Mahmoud, M. D. Ward, Asymptotic distribution of two-protected nodes in random binary search trees, Appl. Math. Lett. 25(12) (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(2) (2022) 1–8. https://doi.org/https://doi.org/10.1051/ita/2022002 [10] J. Spiess, Some identities involving harmonic numbers, Math. Comput. 55(192) (1990) 839–863. https://doi.org/10.2307/2008451 [11] L. Yang, S. L. Yang, Weakly protected points in ordered trees, Graphs Combin. 37(3) (2021) 775– 788. https://doi.org/10.1007/s00373-021-02278-w | ||
|
آمار تعداد مشاهده مقاله: 385 تعداد دریافت فایل اصل مقاله: 388 |
||