שיחזור עץ בינארי משתי סריקות

[amirxbox]

שיחזור עץ בינארי משתי סריקות

שאחת מהן INORDER. מישהו יכול להגיד לי מה הזמן ריצה של שחזור כזה?

 

[johnny d]

ליניארי

 

[amirxbox]

אתה בטוח?

למשל אם יש לי את הסריקות בשני מערכים אני לא מוצא דרך יותר יעילה מ N^2 או משהו שכנראה יהיה NLOGN.

 

[johnny d]

בטוח

אם לדוגמה מדובר על DFS אתה צריך להחזיק מערך נוסף בו אתה מסמן איזה צמתים עברת כבר ב- DFS ולפי הקדקוד הבא במערך ה-In-Order אתה יכול להסיק אם ללכת לבן ימני או מעלה. כמובן ללכת לבן שמאלי זה כאשר המיקום הנוכחי בin-order שווה למיקום נוכחי ב-dfs. ישנם טריקים דומים לכל מיני סוגי סריקות.

 

[amirxbox]

תודה.

 

[amirxbox]

בבקשה רמז או /וכיוון בשאלה הבאה

Given a set of unsorted numbers , suggest an ADT that supports the max_in_range(i,j) operation in O(logn) time units, and uses O memory cells. The max_in_range(i,j) operation returns the largest element in the subset . You may use a preprocessing phase, activated once when the ADT is constructed, which takes O time units. Afterwards, successive calls to max_in_range should take O(logn) time units each. Note: after the initialization of the ADT the numbers cannot be modified, no new numbers will be introduced and no deletions are permitted.

 

[amirxbox]

אני לא מבין איך זה אפשרי

חשבתי על לבנות עץ שיהיה בדומה לטבלת תחרות טניס או "גביע" אבל בניית עץ כזה זה NLOGN.

 

[דודהלי]

אי אפשר לשחזר לפי INORDER

כי כל עץ שמכיל את אותם ערכים, לא משנה מה המבנה שלו יהיה- תמיד נקבל את ה INORDER באותו סדר- ממויין! אפשר לשחזר עץ לפי ה- PREORDER וה- POSTORDER שלו.

 

[amirxbox]

מה הקשר לשאלה??

ולפי מה שאני יודע שתי סירקות שאחת מהן INORDER יביאו לשחזור מוצלח.

 

[דודהלי]

אתה טועה

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

 

[amirxbox]

מה הקשר אבל עצים למה ששאלתי

ואני חושב שאתה טועה. אי אפשר לשחזר עץ בינארי לצורה חד משמעית מPREORDER.

 

[johnny d]

לא הוא לא

in order is a one-way destructive traverse function זה קצת מעצבן שמתעקשים על משהו שאינו נכון. נניח שזו סדרה ליניארית שנקראה על פונקצית הטיול: 508 33 48 405 12 just try to rebuild a single tree and prove it's unique

 

[דודהלי]

INORDER זה סדר ממויין של הערכים

 

[amirxbox]

אבל לא אמרתי שאפשר מ INORDER

אמרתי שאפשר מ INORDER+ PREORDER. והוא טען שאפשר מ PREORDER לבד וזה לא נכון..

 

[Gunslinger]

עץ הוא עץ בינארי ממויין או כללי?

 

[johnny d]

עץ = גרף מכוון ללא מעגלים

 

[דודהלי]

הוא אמר עץ בינארי, לא סתם עץ