2009 מועד א שאלה 4 סעיפים א' ב'

[orp]

מישהו יכול בבקשה להסביר את סעיף א' ואת שאלה 1 בסעיף ב'?

[Golden]

מצטרף לבקשה, 2009 מועד א', שאלה 4 סעיף א' וסעיף ב'1, תודה לכל העוזרים מראש.

[ronenhe]

לגבי 2א: מקווה שאני לא מטעה אבל זאת דעתי..
שמכניסים איבר צריך לדאוג לכל מה שלמעלה..
במידה והוספנו את 7 קודקוד האב לא בנוי להוספה כי אם במקום של 7 היו כבר 3 איברים היה צורך בפיצול של קודקוד האב..
האלגוריתם שלנו מפצל מראש את כל קודקודי האב עד למקום שהיה צריך להוסיף..
ולכן 3 לא יכול להיות אחרי פיצול (בקודקוד הרב)
לגבי 2ב
1 : דוגמא נגדית:



לגבי 2 שימו לב לזה ש:

ומאותה סיבה ש:


מקווה שעזרתי..
בהצלחה..

[eliorar]

סעיף א': לא יכול להיות.
אם הפעולה האחרונה הייתה הכנסה של 7 אז הצומת שמעליו (3,8,2) היה צריך להתפצל כי יש לו 2t-1 כלומר 3. כפי שרואים הוא לא מפוצל לכן פעולה זו לא יכלה להתקיים.

סעיף ב':
1. לא נכון:

log f(n) ≤ c • log g(n) => log f(n) ≤ log ( g(n)^c) => f(n) ≤ g(n)^c

וזה בהחלט לא גורר ש

f(n)≤c • g(n)

לדוגמא:7≤3^2 אבל 7≥2•3
2. לא נכון:

(2n)! = n! • (n+1)(n+2)...(2n)

n! • (n+1)(n+2)...(2n)≤ c• n!

נחלק ב n!:

(n+1)(n+2)...(2n) ≤ c

וזה לעולם לא יקרה כי c קבוע.

[Golden]

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

[eliorar]

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

כנס לאתר הזה: http://www.cse.ohio-state.edu/~bondhugu ... ndex.shtml
יש שם הדגמה טובה של עץ B-Tree