کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438526 | 690285 | 2007 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The left–right-imbalance of binary search trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We present a detailed study of left–right-imbalance measures for random binary search trees under the random permutation model, i.e., where binary search trees are generated by random permutations of {1,2,…,n}. For random binary search trees of size n we study (i) the difference between the left and the right depth of a randomly chosen node, (ii) the difference between the left and the right depth of a specified node j=j(n), and (iii) the difference between the left and the right pathlength, and show for all three imbalance measures limiting distribution results.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 370, Issues 1–3, 12 February 2007, Pages 265-278
Journal: Theoretical Computer Science - Volume 370, Issues 1–3, 12 February 2007, Pages 265-278