דף 1 מתוך 1

מחיקה מ-B-tree

נשלח: 18:59 24/06/2010
על ידי tagels
רק לוודא, באלגוריתם של מחיקת מפתח (k) מ-b-tree,
כשיורדים ובודקים האם לכל צומת יש t-1 מפתחות, האם זה כולל את השורש או שעליו מדלגים?

Re: מחיקה מ-B-tree

נשלח: 17:49 25/06/2010
על ידי danny
אפשר לראות מהאלגוריתם במצגת 7 עמוד 11, שבעצם מדלגים על ה-root

אם אתה בצומת x ולא מצאת את המפתח, אז לפי 3a ו-3b (בעמוד 11), אתה מסתכל על r שהוא הבן שאליו אתה מתכוון לפנות כדי להמשיך לחפש את המפתח.
r הוא זה שאתה בודק לגביו האם הוא עם t-1 מפתחות, ולכן אף פעם לא בודקים את root, כי הוא לא בן של אף אחד.

מקווה שזה עזר.