נושאים פעיליםנושאים פעילים  הצגת רשימה של חברי הפורוםרשימת משתמשים  חיפוש בפורוםחיפוש  עזרהעזרה
  הרשמההרשמה  התחברותהתחברות RSS עדכונים
מדעי המחשב
RSS UnderWarrior Forums : RSS מדעי המחשב
נושא

נושא: עצים בינארים

 שליחת תגובהשליחת נושא חדש
כותב
הודעה << נושא קודם | נושא הבא >>
משה
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 30 April 2005 בשעה 20:20 | IP רשוּם
ציטוט משה

נתון עץ חיפוש בינארי בעל n צמתים
מדוע k קריאות עוקבות לשגרה הנל tree-successor

 הסיבוכיות היא( o(k+h
תזכורת זה:
{
פסודו דוק לשגרה הנל

קוד:
TreeSuccessor(x)
if right[x]!=NIL
then return TreeMinimum(right[x])
y=p[x]
while y!=NIL and x=right[y]
do x=y
y=p[y]
return y


קוד:
Time Complexitiy o(h)

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

הצטרף / הצטרפה: 12 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 3296
נשלח בתאריך: 30 April 2005 בשעה 21:49 | IP רשוּם
ציטוט ניר
נתחיל בטענה: ניתן לקבל סדרה ממויינת של כל המפתחות בעץ בינארי בזמן ליניארי On. נעשה זאת על ידי סריקת העץ ב-inorder. במהלך הסריקה, כאשר סורקים את ערך הצומת, מדפיסים אותו (מסמנים שזה הערך הבא בסדרה הממויינת).
הטענה נכונה מכיוון שאנו סורקים כל תא 3 פעמים לכל היותר במהלך הסיור, ומכיוון שיש n צמתים, אז זמן הסריקה קטן שווה מ-3n.

כאשר אנחנו מדברים על פעולת ה"עוקב" כל מה שאנחנו צריכים לעשות זה למצוא את האיבר שנמצא אחרי הצומת ב-inorder.
לכן כבר אם k=n אתה יכול לראות כי הטענה נכונה.

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


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 01 May 2005 בשעה 17:44 | IP רשוּם
ציטוט אבי

מנהל האתר,

הבנתי שאת הכוחה של השאלה הזו אמורים לפתור ע"י אינדוקציה.

כלומר להראות עבור k=1 שזה o()h וזה קטן מ o()h+1

להניח נכונות עבור k=n

ולהוכיח עבור n+h+1

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

הצטרף / הצטרפה: 12 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 3296
נשלח בתאריך: 04 May 2005 בשעה 13:41 | IP רשוּם
ציטוט ניר
עבור k=1 : אנחנו צריכים למצוא בן ימני שאינו NULL. לכל היותר עלינו מהצומת הנוכחי עד שורש העץ, כלומר לכל היותר עלינו h צמתים, ולכן עבור k=1 התנאי מתקיים.

עבור k=n+h+1 אני עדיין חושב
חזרה לתחילת העמוד הצג את כרטיס החבר של ניר חפש הודעות אחרות של ניר בקר בדף הבית של ניר
 
elilip
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 27 May 2010 בשעה 22:37 | IP רשוּם
ציטוט elilip

שלום

אפשר להסביר את סריקת ה-in order -למה מבקרים בכל צומת רק 3 פעמים מקסימום?

תודה.

 
חזרה לתחילת העמוד הצג את כרטיס החבר של elilip חפש הודעות אחרות של elilip בקר בדף הבית של elilip
 

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

  שליחת תגובהשליחת נושא חדש
גרסת הדפסה גרסת הדפסה

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