Path length of protected nodes in random binary search trees
- سال انتشار: 1404
- محل انتشار: مجله ریاضیات گسسته و کاربردهای آن، دوره: 10، شماره: 4
- کد COI اختصاصی: JR_JDMA-10-4_002
- زبان مقاله: انگلیسی
- تعداد مشاهده: 5
نویسندگان
Department of Statistics, Faculty of Science, Imam Khomeini International University, Qazvin, I. R. Iran
Department of Statistics, Faculty of Science, Imam Khomeini International University, Qazvin, I. R. Iran
چکیده
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{۱۵ Pn}{۱۱n\ln n}\to ۱and\frac{۱۵W_n}{۱۴n\ln n}\to ۱in probability.کلیدواژه ها
Binary search trees, path length, protected node, weakly protected node, limiting ruleاطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.