קריאות רצופות ל-succesor

[גודבאר]

קריאות רצופות ל-succesor

איך ניתן להוכיח ש-k קריאות רצופות ל-succesor מבוצעות בזמן O(h+k) = t מדובר על עץ בינארי

 

[HaifaMan]

שאלת הכוון

איך אתה מטייל על העץ בביצוע קריאת successor ?

 

[גודבאר]

תודה. אבל זה לא כל-כך עוזר

אולי יש למישהו רעיון יותר. קריאה אחת ל-successor מבוצעת ב- O h צריך חסם ל-k קריאות רצופות.

 

[HaifaMan]

שים לב שב-K קריאות

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