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

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