فاصله گره‌ها در درخت‌هاي افزايشي

يك درخت اندازه‌ي nافزايشي است هرگاه هر گره آن داراي يك برچسب متعلق به مجموعه‌‌ي{1,2,...n} باشد به‌طوري كه هيچ برچسبي دوبار ظاهر نشود و در هر مسير از ريشه تا يك برگ، برچسب‌ها دنباله‌اي افزايشي تشكيل دهند. دو خانواده‌ي مهم از چنين درخت‌هايي، درخت‌هاي بازگشتي و درخت‌هاي افزايشي دودويي هستند. در اين مقاله، كميت فاصله بين گره j1 و گره j2 در درخت‌هاي افزايشي تصادفي اندازه n مطالعه مي‌شود. فرمول‌هاي بسته‌اي براي توزيع احتمال، اميد‌رياضي و واريانس ارائه مي‌شوند. هم‌چنين، نرمال بودن مجانبي اين كميت نشان داده مي‌شود.