רוטר - שאלה במבני נתונים - קביעה האם קודקוד u הוא אב קדמון של קודקוד v (או להיפך)

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"שאלה במבני נתונים - קביעה האם קודקוד u הוא אב קדמון של קודקוד v (או להיפך)"

גירסת הדפסה

קבוצות דיון לימודים, מדע ותרבות נושא #21452	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 21452

Amirh
חבר מתאריך 24.9.09
123 הודעות, דרג אמינות חבר זה

22:29 02.06.16

שאלה במבני נתונים - קביעה האם קודקוד u הוא אב קדמון של קודקוד v (או להיפך)

אהלן,
אני לא מצליח להגיע לפתרון, ולא הצלחתי למצוא תשובה לזה ברשת:
http://rotter.name/User_files/nor/5750869613a7494b.png
ממה שהגעתי אליו - צריך בעיבוד המקדים לשמור לכל איבר מחרוזת שמייצגת את המסלול של אותו קודקוד. למשל :
http://rotter.name/User_files/nor/5750883516810b73.png

ואז, כדי לבדוק אם v צאצא של u צריך לבדוק אם המחרוזת של v היא רישא של המחרוזת של u. הבעיה היא שבדיקה כזו תבצע פעולות כעומק העץ, מה שעלול להגיע כם לO(n) במקרה הגרוע.
מה אני מפספס ?
תודה רבה !

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
אתה צודק שיש בעיה בפתרון שלך	Deuce	04.06.16 13:59	1
עדיין מדובר בזמן ריצה שהוא כגודל העץ	Bar	07.06.16 11:20	2
dfs	Dark-Wish	07.06.16 11:37	3
תודה רבה לכם על העזרה! שאלה:	Amirh	08.06.16 14:02	4
מה שDeuce הציע לא יעמוד בזמני הריצה הנדרשים או בסיבוכיות המקום הנדרשת	Bar	09.06.16 07:36	5
למה? רק העיבוד המקדים יקח O(n) פעם אחת לכל סריקה (פעמיים סך הכל)	Amirh	09.06.16 11:55	6
אמיר, הבנת נכון. ו-Deuce, כאמור צודק :-)	Deuce	09.06.16 22:20	7
התשובה היא לא בO(1) אבל	Bar	10.06.16 09:25	8
תודה רבה על העזרה, אין צורך לעבור על הסריקות	Amirh	10.06.16 17:36	9

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

13:59 04.06.16

1. אתה צודק שיש בעיה בפתרון שלך
בתגובה להודעה מספר 0

אתה משלם על הבדיקה במקרה הגרוע O(d) כאשר d הוא עומק העץ. וכפי שאמרת, אם העץ לא מאוזן אתה יכול לשלם על הבדיקה גם O(n).
אני אתן לך רעיון ללא הוכחה ונסה לחשוב בעצמך מדוע זה נכון. תסתכל על המספור של איברי העץ כאשר אתה מבצע מעבר Preorder וכאשר אתה מבצע מעבר Postorder. אני טוען ש-u הוא אב קדמון של v אמ"מ u מופיע לפניו ב-Preoder ואחריו ב-Postorder.
http://www.cs.cmu.edu/~clo/www/CMU/DataStructures/Lessons/lesson4_3_files/image001.gif

בהצלחה!

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Bar

חבר מתאריך 24.3.02
24027 הודעות, 7 פידבק, 14 נקודות

11:20 07.06.16

2. עדיין מדובר בזמן ריצה שהוא כגודל העץ
בתגובה להודעה מספר 1

נשלח ע"י הסלולרי

He who makes a beast out of himself,
gets rid of the pain of being a man.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dark-Wish
חבר מתאריך 25.5.05
12576 הודעות, דרג אמינות חבר זה

11:37 07.06.16

3. dfs
בתגובה להודעה מספר 0

כל קודקוד מחזיק זמן התחלה וזמן סיום
u אבא של v אם זמן ההתחלה של v הוא בין זמן ההתחלה של u לבין זמן הסיום של u

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Amirh
חבר מתאריך 24.9.09
123 הודעות, דרג אמינות חבר זה

14:02 08.06.16

4. תודה רבה לכם על העזרה! שאלה:
בתגובה להודעה מספר 0

אני לא בטוח אם הבנתי את מה ש-Deuce הציע ,
צריך לבצע מעבר preorder ומעבר postorder ובשנינם לתת מספור לקודקודי העץ שמייצג את אינדקס האיבר בכל סוג מעבר , ואז בהנתן פוינטר לקודקוד v , כדי לקבוע אם v אב קדמון של u בודקים ש-preorder(v) קטן מpreorder(u) וש-postorder(v) גדול מpostorder(u) ?
לדעתכם צריך להוכיח את המשפט הזה?
בקשר למה שDark-Wish הציע , לצערי לא למדנו dfs אז אני חושב שהתכוונו שנפתור את השאלה בדרך אחרת...

תודה רבה!!

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Bar

חבר מתאריך 24.3.02
24027 הודעות, 7 פידבק, 14 נקודות

07:36 09.06.16

5. מה שDeuce הציע לא יעמוד בזמני הריצה הנדרשים או בסיבוכיות המקום הנדרשת
בתגובה להודעה מספר 4

He who makes a beast out of himself,
gets rid of the pain of being a man.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Amirh
חבר מתאריך 24.9.09
123 הודעות, דרג אמינות חבר זה

11:55 09.06.16

6. למה? רק העיבוד המקדים יקח O(n) פעם אחת לכל סריקה (פעמיים סך הכל)
בתגובה להודעה מספר 5

ואז , בהינתן פוינטרים לשני קודקודים, ניגשים לpreOrder ולpostOrder של כל קודקוד בO)1( לכל גישה כזו. סיבוכיות המקום היא קבועה, בסך הכל הוספנו 2 מאפיינים נוספים לכל קודקוד, כמו שדורשים בשאלה.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

22:20 09.06.16

7. אמיר, הבנת נכון. ו-Deuce, כאמור צודק :-)
בתגובה להודעה מספר 5

בשאלה אפשר לעשות Preprocessing בעלות לינארית. כפי שאמיר אמר, לכל צומת אתה שומר 2 ערכים וזמן השאילתה הוא O(1).
לגבי הוכחת המשפט, אני לא יודע איפה אתה לומד ומה הדרישות מכם בשיעורי הבית. אני באופן אישי בעד הוכחות ובהעדר הוכחה פורמלית, תסביר במילים את הרעיון.

במקרה שלנו נסה להוכיח על דרך השלילה - זה לא כ"כ קשה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Bar

חבר מתאריך 24.3.02
24027 הודעות, 7 פידבק, 14 נקודות

09:25 10.06.16

8. התשובה היא לא בO(1) אבל
בתגובה להודעה מספר 7

תצטרך לעבור על הסריקות בשביל להחזיר תשובה

נשלח ע"י הסלולרי

He who makes a beast out of himself,
gets rid of the pain of being a man.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Amirh
חבר מתאריך 24.9.09
123 הודעות, דרג אמינות חבר זה

17:36 10.06.16

9. תודה רבה על העזרה, אין צורך לעבור על הסריקות
בתגובה להודעה מספר 8

כי בשאלה דורשים ש"בהינתן שני מצביעים לקודקודים בעץ", כלומר לאחר עיבוד מקדים קיבלנו 2 פוינטרים וניגשנו למידע ששמרנו , הגישה היא ב-o(1) .

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד