المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۶:الگوریتم ها:سوال ۵

پسرخاله

در یک درخت دودویی جست‌جو، پسرخاله‌ی گره‌ی ‎$x$‎، گره‌ای است که در صورتی که عناصر درخت را مرتّب کنیم، دقیقاً قبل از ‎$x$‎ قرار بگیرد. برای مثال در د.د.ج‌.ای که اعداد ‎۱‎ تا ‎$n$‎ در آن (به هر ترتیبی) قرار گرفته باشند، پسرخاله‌ی گره‌ای با مقدار ‎$1 < i \leq n$‎، گره‌ی با مقدار ‎$i+1$‎ است.

الگوریتمی با اعلان (Tree-Cousin($x$‎ به‌زبان CLRS‎ بنویسید که پسرخاله‌ی یک گره را برگرداند. دقّت کنید که ‎$x$‎ یک گره (و نه مقدار آن) است و خروجی الگوریتم هم باید یک گره (و نه یک مقدار) باشد. در صورتی که آن گره پسرخاله نداشت (عنصر کمینه بود)، NIL‎ باید برگردانده شود‎.


ابزار صفحه