الگوریتم کمترین والدین مشترک تارجان

الگوریتم کمترین والدین مشترک تارجان در علوم کامپیوتر الگوریتم کمترین جد مشترک Tarjan (یا دقیق تر، پایین‌ترین جد مشترک) الگوریتمی است که بر اساس ساختمان داده‌های مجزا پایین‌ترین جد مشترک بین دو گره را پیدا می‌کند. پایین‌ترین جد مشترک دو گره d و e گره g از درخت ریشه دار T است که از بین گره‌هایی که هم جد e و هم جد d هستند بیشترین عمق را دارد. این الگوریتم به افتخار Robert Tarjan که در سال ۱۹۷۹ این تکنیک را ابداع کرد نام گذاری شده‌است.الگوریتم تارجان آفلاین است به این معنی که هنگام اجرا، تمام جفت گره‌ها باید قابل دسترسی باشند. ساده‌ترین نسخه الگوریتم از ساختمان داده‌های مجموعه استفاده می‌کند که نسبت به دیگر ساختمان داده ها کندتر است. بهینه سازی که توسط ‎(Gabow و Tarjan 1983)‎ ارائه شد سرعت الگوریتم را به سرعت خطی کاهش داد.

الگوریتم

شبه کد زیر پایین‌ترین جد مشترک هر دو جفت گره‌ها از مجموعه P را بدست می‌دهد.n.children فرزندان گره n را بدست می‌دهد. این الگوریتم همچنین از توابع MakeSet، Findو Union از جنگل های مجزا استفاده می‌کند.تابع TarjanOLCA گره ای را به عنوان ورودی دریافت و پایین‌ترین جد مشترک تمام جفت گره‌ها را در خروجی چاپ می‌کند.

 function TarjanOLCA(u)
     MakeSet(u);
     u.ancestor := u;
     for each v in u.children do
         TarjanOLCA(v);
         Union(u,v);
         Find(u).ancestor := u;
     u.colour := black;
     for each v such that {u,v} in P do
         if v.colour == black
             print "Tarjan's Least Common Ancestor of " + u +
                   " and " + v + " is " + Find(v).ancestor + ".";

منطق الگوریتم به این صورت است که در ابتدا تمام گره‌ها سفید هستند، بعد از این که آن گره و تمام فرزندانش بازدید شدند سیاه می‌شود. پایین‌ترین جد مشترک فقط و فقط پس بلافاصله پس از سیاه شدن یک گره بدست می آید.

منابع

• Gabow, H. N.; Tarjan, R. E. (1983), "A linear-time algorithm for a special case of disjoint set union", Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), pp. 246–251, doi:10.1145/800061.808753.
• Tarjan, R. E. (1979), "Applications of path compression on balanced trees", Journal of the ACM, 26 (4): 690–715, doi:10.1145/322154.322161.