שאלה במבנה נתונים
עץ הפוך הוא עץ שבו כל המצביעים אינם הולכים מהורה לבנים, אלא להיפך, מהבנים להורה, ז"א לכל קודקוד בעץ יש מצביע אחד, לאביו, כאשר מצביע שיוצא מהשורש הוא NULL. בהינתן מצביע לקודקוד בעץ ניתן בקלות להגיע לשורש של העץ. עצים כאלו לאו דוקא בינריים ומספר בניו של קודקוד אינו מוגבל. אוסף של עצים הפוכים מנוהל ע"י כך שממזגים מדי פעם שני עצים הפוכים T1 ו-T2 ע"י כך שהופכים את T1 כתת-עץ (נוסף) של שורשו של T2, ז"א משנים את המצביע NULL שיוצא משורשו של T1 להצביע על T2. התנאי לאיחוד כזה הוא שב-T1 יהיה מספר קודקודים קטן או שווה למספר הקודקודים ב-T2, ז"א תולים תמיד את העץ הקטן (מבחינת מספר קודקודים) בעץ הגדול. איך ניתן לממש את מבני הנתונים כדי לאפשר, בהינתן מצביעים לשורשים של T1 ו-T2, איחוד של העצים בזמן קבוע (לא תלוי בגודל העץ)? תאר\י את מבני הנתונים והאלגוריתם המתאימים. שימו לב שבמבנה כפי שתואר לעיל, אין אפשרות לגלות נתונים על העץ כשיש רק מצביע לשורש, היות ומהשורש אין אפילו דרך להגיע לבניו. תודה מראש למי שיכול לעזור
עץ הפוך הוא עץ שבו כל המצביעים אינם הולכים מהורה לבנים, אלא להיפך, מהבנים להורה, ז"א לכל קודקוד בעץ יש מצביע אחד, לאביו, כאשר מצביע שיוצא מהשורש הוא NULL. בהינתן מצביע לקודקוד בעץ ניתן בקלות להגיע לשורש של העץ. עצים כאלו לאו דוקא בינריים ומספר בניו של קודקוד אינו מוגבל. אוסף של עצים הפוכים מנוהל ע"י כך שממזגים מדי פעם שני עצים הפוכים T1 ו-T2 ע"י כך שהופכים את T1 כתת-עץ (נוסף) של שורשו של T2, ז"א משנים את המצביע NULL שיוצא משורשו של T1 להצביע על T2. התנאי לאיחוד כזה הוא שב-T1 יהיה מספר קודקודים קטן או שווה למספר הקודקודים ב-T2, ז"א תולים תמיד את העץ הקטן (מבחינת מספר קודקודים) בעץ הגדול. איך ניתן לממש את מבני הנתונים כדי לאפשר, בהינתן מצביעים לשורשים של T1 ו-T2, איחוד של העצים בזמן קבוע (לא תלוי בגודל העץ)? תאר\י את מבני הנתונים והאלגוריתם המתאימים. שימו לב שבמבנה כפי שתואר לעיל, אין אפשרות לגלות נתונים על העץ כשיש רק מצביע לשורש, היות ומהשורש אין אפילו דרך להגיע לבניו. תודה מראש למי שיכול לעזור