שאלונת על עצי 2-3...

[white shadow 3]

שאלונת על עצי 2-3...

נשאלנו "למה המימוש של עץ 2-3 לא מאפשר צומת עם דרגה 1"..?

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

זאת תשובה לגיטימית? יש עוד סיבות שאני יכול לציין? כי אני לא 100% שהבנתי את כוונת המשורר בשאלה הזאת ...(זה בערך כמו לשאול למה BFS עובר על כל צומת רק פעם אחת..ככה הגדירו אותו....)

תודה

 

[Javali]

תשובה לגיטימית, אבל לא נכונה

הבעיה שאתה מתאר בביצוע מחיקה יכולה להפתר בצורה פשוטה ע״י אלגוריתם מתאים.
&nbsp
רמז לפתרון הנכון: חשוב על הייתרון של עצי 2-3 לעומת עצים בינאריים.

 

[white shadow 3]

תודה + שאלה נוספת

לגבי השאלה הקודמת - אני אחשוב בשנית על היתרונות ומקווה שאגיע למסקנות
&nbsp
שאלה נוספת -
נגדיר label tree כעץ בינארי שלכל צומת מפתח ייחודי.
הוכח/הפרך: כל label tree שמתקיים את תכונת עץ חיפוש בינארי ניתן לקבל ע"י סדרת הכנסות בלבד.
עכשיו, בהרצאה ראינו את פונקציית insert tree שלמיטב הבנתי לוקחת עץ T (שיכול להיות ריק או בעל איברים) ואיבר חדש a ו"מפעפעת" את הצומת a הזאת במורד העץ עד שמגיע למקום הנכון.
עכשיו, לא ראינו הוכחה שהפונקציה הזאת אכן שומרת על תכונת עץ החיפוש הבינארי אבל בשאלה הזאת אנחנו יכולים להניח שהפונקציה אכן נכונה ומקיימת את הדרישה
&nbsp
אז - מה אני מפספס כאן בשאלה? הרי אם אמרו לנו שהפונקציה הזאת נכונה ואני יודע שבסוף ריצתה על צומת אחת חדשה אני מקבל עץ שמקיים את תכונת עץ חיפוש בינארי, אז אני יכול להפעיל אותה n פעמים על n "מפתחות שונים" ועדיין לקבל label tree שמתקיים את תכונת עץ החיפוש הבינארי...

&nbsp

 

[Javali]

תשובה

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

 

[white shadow 3]

אוקי

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

אז אני יוצא מנקודת הנחה שנתון לי עץ, ואני צריך לבדוק האם תמיד אני יכול למצוא סדרת הכנסות
כלומר, נניח נתון לי עץ בו 1 הוא שורש ו-2 בן ימני אז הסדרה היא 1,2
אם נתון לי עץ שבו 2 שורש ו-1 בן שמאלי אז הסדרה 2,1
(תוך הנחה כי האיבר הראשון בסדרה יהיה השורש שלנו)

עכשיו נניח יש לי עץ שבו 2 שורש, 1 בן שמאלי ו-3 בן ימני
אז אני יכול לחשוב על הסדרה 2,1,3 או 2,3,1 ששתיהן יניבו לי את העץ הזה

נניח יש לי עץ שבו 2 שורש, 1 בן שמאלי, 3 בן ימני, 4 בן ימני של 3
אז אפשר לחשוב על הסדרות: 2,1,3,4 או 2,3,1,4 או 2,3,4,1

וכו'
עד לכאן הבנתי נכון?
על פניו בינתיים נראה שאין סיבה שזה לא יהיה נכון, השאלה היא איך מוכיחים את זה .
כלומר, בגלל שאני בעצם מחפש לפחו סדרה אחת (אולי יש עוד..) אז פתרון אחד טריויאלי נראה פשוט ללכת לפי רמות ולסדר את הקודקודים לפי הופעתם בכל רמה משמאל לימין והנה, מצאנו סדרה...
(נניח בדוגמא עם העץ שבו 2 שורש, 1 בן שמאלי, 3 בן ימני, 4 בן ימני של 3 אז הסדרה לדוגמא תהיה 2,1,3,4)

לא? (יש לי תחושה חזקה שלאור ה"מסקנות" שלי בשרשור הזה כנראה שהתשובה תהיה "לא"...)

אגב, תודה (שוב) על ההסברים והסבלנות..

 

[Javali]

יפה

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

> ... עד לכאן הבנתי נכון?
נכון.

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

אני לא בטוח שהסדרה שאתה בחרת תתן לך את ההוכחה הכי פשוטה, אבל כשתנסה להוכיח יכול להיות שתמצא סדרה יותר פשוטה.

 

[white shadow 3]

נניח אני מוצא סדרה כלשהיא ורוצה להוכיח באינדוקציה שהיא אכן

מביאה אותי חזרה לאותו העץ,
אני יכול / צריך להשתמש בכיוון השני (פונקציית ה-INSERT שנתנו לנו אותה בכיתה ואמרו לנו שהיא נכונה) או שצריך בדרך אחרת (כי נשמע לי קצת כמו לולאה עצמית להוכיח צד אחד של משהו ע"י שימוש בצד השני שלו אבל אם כבר אני יודע שהפונקציה הזאת נכונה ובהינתן סדרה מסויימת של איברים, לדעתי, אמורים לקבל בדיוק עץ חיפוש בינארי אחד (לא בטוח 100% אבל ממה שניסיתי לצייר לי בראש זה היה נראה שאמור לעבוד..) )
&nbsp
אגב, עוד משהו שניסיתי לחשוב עליו - אולי שימוש בסריקה, נגיד, PREORDER של העץ הנתון יכולה לעזור לי? אז אני יודע שהשורש יהיה ראשון, לאחר מכן יופיעו בסדרה כל המספרים הקטנים ממנו ולאחר מכן כל המספרים הגדולים ממנו ע"פ סדר הקריאות
גם כאן אני יכול כביכול להשתמש בפונקציה INSERT על הסדרה שהתקבלה וע"פ הנחת הנכונות שלה לקבל את העץ T המקורי..
&nbsp
(אני פשוט כבר קצת מיואש

)

 

[Javali]

לא להתייאש

1. לא להתייאש. אתה קרוב מאוד להוכחה.
&nbsp
2. אתה יכול להשתמש בתכונות של insert.
&nbsp
3. אם אתה מפעיל את insert על סדרה אתה מקבל בדיוק עץ בינארי אחד. מה שאתה צריך להוכיח זה שאתה מקבל את העץ הבינארי שאתה רוצה.
&nbsp
4. הרעיון של שימוש בסריקת preorder הוא נכון מאוד. זו בדיוק הסדרה שתתן לך הוכחה פשוטה.
&nbsp
5. האם אתה יכול להוכיח שבאמצעות שימוש ב-insert על סדרת ה-preorder של העץ אתה מקבל חזרה את העץ? יכול להיות שכבר הוכחת את זה, ואם כן, מה טוב. אבל אני עדיין לא ראיתי הוכחה. בפרט, המשפט שכתבת (להשתמש בפונקציה INSERT על הסדרה שהתקבלה וע"פ הנחת הנכונות שלה לקבל את העץ T המקורי) זה נפנופי ידיים.
&nbsp
6. יש סיכוי לא רע שאם תכתוב שאתה משתמש ב preorder ותתן איזה נפנוף ידיים על למה זה בונה את T תקבל את רוב הנקודות על התרגיל. אבל בלי ההוכחה לא סביר שתקבל את כולן.
&nbsp

 

[white shadow 3]

מעולה,

מרגיש קצת יותר טוב על ההתקדמות

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

 

[white shadow 3]

בעצם, אני לא מראה כאן שקיבלתי את T ע"י שימוש ב-*INSERT*...

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

?

 

[Javali]

זו הוכחה באינדוקציה

רק חסר לך הניסוח הפורמלי. הנה פחות או יותר:
&nbsp
אנחנו מוכיחים שעץ שבונים ע״י insert על הסדרה שמקבלים מסריקת preorder של עץ חיפוש בינארי נותן את העץ המקורי. ההוכחה באינדוקציה על מבנה העץ.
&nbsp
עבור עץ ריק הטענה נכונה.
&nbsp
נניח שהוכחנו את הטענה עבור עצים בגודל קטן מ-n. עץ חיפוש בינארי מורכב משורש, ושני תתי-עצים שכל אחד מהם הוא עץ חיפוש בינארי בגודל קטן מ-n. סריקת preorder של עץ כזה תיתן לנו ראשית את השורש, אחריו את סריקת ה-preorder של תת-העץ השמאלי ואח״כ את זו של הימני.
השורש ישאר זהה לעץ המקורי כי...
מהתכונות של insert אנחנו מקבלים שכל איברי תת-העץ השמאלי של העץ המקורי ילכו לתת השמאלי של העץ החדש. (הסבר...) ומהנחת האינדוקציה תת העץ השמאלי של העץ החדש זהה לזה של העץ המקורי. כנ״ל לתת העץ הימני.
מ.ש.ל.

 

[white shadow 3]

תודה רבה!

(שוב, על העזרה ועל הסבלנות הרבה

)

 

[white shadow 3]

כפול

 

[white shadow 3]

כפול

 

[white shadow 3]

כפול