ושוב אני כאן

[Yurismaster]

ושוב אני כאן

בגישה אובדנית, קיבלנו תרגיל עם 7 תרגילים, חלקם קשים ואלו שנחשבו לקשים ביותר פתרתי בלי בעיות מיוחדות . אבל את 2 השאלות הללו ...2 השאלות הללו גררררררררר האחת אני חושב שפתרתי אני פשוט לא בטוח: בהנחה והחיפוש אחר מפתח K בעץ חיפוש בינארי הסתיים בעלה(צומת). יהיו A קבוצת המפתחות משמאל למסלול החיפוש, B קבוצת המפתחות במסלול החיפוש ו-C קבוצת המפתחות מימין למסלול החיפוש. הוכח או הפרך: a<=b<=c עבור a שייך ל A b שייך ל B c שייך ל C אז עשיתי עץ דוג' נגדית: 100 150 50 160 125 130 B=100,150,125 ואז 130 שייך ל C והוא יותר קטן מ 150 ששייך ל B אני מקווה שזה נכון...אבל מה שמטריד אותי יותר זה שאלה שהולכת ככה:הוכח או הפרך: פעולת מחיקה מעץ בינארי היא פעולה קומוטטיבית. כלומר:מחיקת צומת X ואחרי Y תוביל לאותו עץ כמו מחיקת צומת Y ואחריו מחיקת צומת X. אין לי מושג!!! זה יותר הגיוני שזה הפרכה כי אין מושג איך להוכיח את זה, אבל אני לא מוצא שום הפרכה...חייבים להוכיח את זה?

 

[DNile]

לגבי השאלה השניה -

זה תלוי בהגדרה של מחיקה. האם אפשר למחוק איבר מעץ אם האיבר הזה איננו קיים? בהנחה שX נמצא איפה שהוא בעץ מתחת לY, אז מחיקת Y תוביל אוטומטית למחיקת X, ואז אי אפשר למחוק את X שכבר איננו נמצא בעץ.

 

[Yurismaster]

שאנחנו הגדרנו פונ'

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

 

[אינגולמו]

מחיקה של קודקוד

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

 

[אינגולמו]

אינטואיציה

1. נניח ובעץ מלא יש N קודקודים. בשביל להגיע לעלה אתה עובר LOGN קודקודים. אם חיפשת את העלה עם הערך המקסימלי, אזי A זה כמעט כל העץ, B זה תמיד LOGN, ו-C היא קבוצה ריקה. אם חיפשת את הערך המינימלי בעץ, אז הגדלים של A ו-C מתהפכים. לכן אי-השוויון שכתבת לא נכון בהכרח. 2. אני היית מחלק למקרים איכשהו... אולי: א. אם Y הוא לא בן שמאלי של X, ואז אני חושב שזה נכון, כי פעולת ה-DELETE לא מתעסקת בכלל עם Y בזמן מחיקת X, וההיפך. ב. אם Y הוא בן שמאלי של X: תבדוק את המקרים ש-Y הוא האיבר המקסימלי/לא המקסימלי בתת עץ השמאלי של X... נראה לי שזה הכיוון.

 

[Yurismaster]

בשאלה הראשונה

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

 

[אלדד28]

יש פה קצת בלבול

אינגו, נדמה לי שבדקת את גודל הקבוצות, הכוונה היא לאיברים שבתוך הקבוצות - כלומר, כל האיברים ב-A יהיו קטנים מכל האיברים ב-B שיהיו קטנים יותר מכל האיברים ב-C. yurismaster, ההפרכה שנתת נכונה.

 

[אינגולמו]

נכון, אופס ../images/Emo45.gif

 

[tami120]

אם אתה צריך מימושים של אלגורתימים..

של אלגוריתמים של עצים ועוד תכתוב את האימייל אני אשלח לך

 

[אלדד28]

ולגבי השאלה השניה...

לא, הפעולה הזו לא קומוטטיבית. ראה הדוגמה המצורפת, כאשר X=5 ו-Y=1. אם מוחקים את X ואח"כ את Y מקבלים 6 מוביל ימינה ל-7 מוביל ימינה ל-8. אם מוחקים את Y ואח"כ את X מקבלים 7 מוביל ימינה ל-8 ושמאלה ל-6.

 

[Yurismaster]

תודה!

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

 

[אלדד28]

RB Trees זה כיף לא נורמלי,

בהצלחה עם המימוש של REMOVE

 

[אינגולמו]

רגע, משהו לא ברור לי

אם מחקתי את 5, אז 1 נהפך להיות השורש. אח"כ מחקתי את 1, ואז שורש העץ הוא 7. אם מחקתי את 1, אז 5 נשאר השורש, ואח"כ, כאשר אני מוחק את 5, שוב 7 נהפך להיות השורש, עם אותם בנים כמו מקודם. זה יוצא אותו העץ... מה פיספסתי פה?

 

[אלדד28]

אם מחקת את 5,

6 הופך להיות השורש. כשמוחקים NODE שיש לו שני בנים, ה-SUCCESSOR של ה-NODE מחליף את ה-NODE.

 

[אינגולמו]

זה לא משנה ../images/Emo13.gif

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

 

[tami120]

לגבי השאלה הראשונה

לגבי השאלה הראשונה -זה לא נכון הדוגמא שהבאת לא נכונה כי זאת לא הגדרה של עץ חיפוש בינארי זה בטוח נכון בגלל שההגדרה של עץ חיפוש בינארי היא שעבור כל צומת (k) מתקיים : כל איבר בתת עץ שמאל קטן מהערך של צומת k וכל איבר בתת עץ ימין גדול מצומת k בגלל שזאת ההגדרה של עץ חיפוש בינארי זה חייב להתקיים

 

[Yurismaster]

זה הcatch בשאלה,

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

 

[ChipsMan]

תסמוך עלי...

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

יש איזה אלגוריתם מוזר שהראו לנו במבני נתונים שבהנתן עץ, עושים עליו איזהשהו חישוב בזמן לינארי, ואז כל פעם שרוצים לדעת מיהו האב המשותף הנמוך ביותר לשני צמתים עושים את זה ב-O(1) a. וזה היה מפחיד במיוחד

 

[tami120]

מוזר, עדיין נראה לי שזה נכון...

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