שאלה במבני נתונים - עצים בינאריים

[thankful]

שאלה במבני נתונים - עצים בינאריים

הוכח כי ניתן לשחזר עץ *חיפוש* בינארי מהסריקה הסופית (POST-ORDER) שלו : בהינתן סדרה שהיא תוצאת הסריקה הסופית <k1,k2,...kn> , מבנה העץ משוחזר כאשר הסדרה נקראת מימין לשמאל . הניחו שהמפתחות שונים זה מזה . חשבתי על הרעיון הבא , שמישהו אמר לי שהוא *שגוי מיסודו* (אשמח להסבר מדוע) . הרעיון הוא : נכניס את מפתחות הסדרה הנ"ל , מימין לשמאל (בזה אחר זה) , לתוך עץ חיפוש בינארי , באמצעות אלגוריתם ההכנסה לעץ חיפוש בינרי (TREE-INSERT) (הכנסה כעלה לעץ , בהתאם למיקום שהמפתח החדש אמור להיכנס אליו) . שחזור העץ מהסריקה הסופית (באמצעות N פעולות TREE-INSERT) הוא חד משמעי : בעת הכנסת מפתח לעץ החיפוש , הוא יכול להיכנס רק כעלה שהוא בן ימני של אביו , או רק כעלה שהוא בן שמאלי של אביו - זאת לפי הנתון , שכל המפתחות בעץ שונים זה מזה . אז מה כאן שגוי ? (היכן השגיאה/ות ?) בברכה , ליאור .

 

[vinney]

אתה לא משחזר עץ, אתה בונה עץ מחדש

שעם אותם הנתונים יצא לך אותו העץ. הרעיון הוא "לשחזר" את העץ, דהיינו לבנות אותו מבלי לדעת את הלוגיקה של הבניה (המיון, ובכך לחסוך בסיבוכיות), אלא רק לדעת שמדובר בסריקה סופית של עץ בינארי.

 

[thankful]

עכשיו , תגיד לי בבקשה מדוע גם הרעיון הבא אינו

נכון : (מישהו הציע את זה) נוכיח באינדוקציה על מס' הצמתים בעץ . עבור N=1 - ברור . נניח נכונות עבור 1<N , ונוכיח עבור N+1 . k1 הוא עלה בעץ (כי נתונה סריקה סופית ש - k1 הוא המפתח הראשון בה) : נמחק את העלה k1 מהעץ (זכור שכל המפתחות שונים זה מזה) . נותרנו עם עץ חיפוש בינארי בגודל N : עבור עץ זה , מתקיימת הנחת האינדוקציה , וניתן לשחזרו בקריאת הסריקה הסופית מימין לשמאל . נוסיף שוב את העלה k1 לעץ : מבנה העץ לא השתנה (נכון ?) . אז גם את העץ עם k1 (לאחר ההוספה) ניתן לשחזר בקריאת הסריקה הסופית מימין לשמאל (והעץ יחיד) . מה כאן לא בסדר ? בברכה , ליאור .

 

[vinney]

זה אותו דבר

אתה מתבסס על בניה של עץ, לא שיחזור. אתה צריך לדעתי לתת אלגוריתם לשחזור, בתור הוכחה. שים לב - מדובר בעץ חיפוש בינארי, משמע האיבר האחרון בסריקה הוא השורש,וכל השאר - מתחלקים ליותר ממנו ופחות ממנו, כך אתה יכול לדעת בעצם איזה חלק של הרשימה יהיה בתת עץ השמאלי ואיזה בתת עץ הימני, ולאחר מכן, לכל אחד מהחלקים - האלגוריתם יעבוד ברקורסיה באותה הצורה. אתה צריך להתבסס על הידע הזה שהסריקה נעשתה על עץ חיפוש בינארי, לא על זה שאתה בונה עץ חיפוש בינארי חדש.

 

[immortalus]

אולי אני טועה, אבל אני חושב שהטעות היא בטענה

הטענה נראית לי לא נכונה בעליל... אני וידע שאפשר לשחזר עץ אם נתון PRE-ORDER+POST-ORDER כלומר 2 סריקות... מסריקה אחת? לא נשמע לי אפשרי. נסה למשל לשחזר את העץ הבא מסריקת ה-POST-ORDER שלו. אם תצליח, תדע מיד את האלגוריתם לשחזור ומכאן הדרך להוכחה קצרה, מצד שני אני מטיל ספק שתצליח: 2,4,5,3,10,15,12,9,6

 

[immortalus]

המ.. תיקון טעות, יש אלגוריתם כזה...

תוכיח ע"י תיאור האלגוריתם, צריך להתקבל...

 

[thankful]

אכן טעית בטענתך הקודמת

שכן מדובר בעץ חיפוש בינארי (ולכן הדגשתי את "חיפוש" בשאלה המקורית ...) ליאור .