מחיקה מ-B-tree

מנהל: TA_Isana

שלח תגובה
tagels
הודעות: 4
הצטרף: 21:14 30/10/2009

מחיקה מ-B-tree

שליחה על ידי tagels » 18:59 24/06/2010

רק לוודא, באלגוריתם של מחיקת מפתח (k) מ-b-tree,
כשיורדים ובודקים האם לכל צומת יש t-1 מפתחות, האם זה כולל את השורש או שעליו מדלגים?

danny
הודעות: 64
הצטרף: 12:32 23/10/2009

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

שליחה על ידי danny » 17:49 25/06/2010

אפשר לראות מהאלגוריתם במצגת 7 עמוד 11, שבעצם מדלגים על ה-root

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

מקווה שזה עזר.
Error is Created. Truth is Eternal. Error, or Creation, will be Burned up, & then, & not till Then, Truth or Eternity will appear

שלח תגובה

חזור אל “- מבני נתונים 2010”