נושא: עוקב בעץ חיפוש בינארי

נשלח בתאריך: 26 April 2007 בשעה 18:31 | IP רשוּם

הי לכם!

יש לי שאלה לגבי עוקב בעץ חיפוש בינארי.

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

במילים אחרות, יש לי לולאה פשוטה שרצה k פעמים ובתוכה יש קריאה לפונק' שמוצאת את העוקב, ועוד מספר קבוע של פעולות. בכל ריצה של הלולאה, האיבר עליו מופעלת פונק' העוקב הוא האיבר אשר הוחזר ממנה בריצה הקודמת של הלולאה, כאשר בפעם הראשונה האיבר הוא האיבר המינימלי (הכי שמאלי) בעץ. כלומר: האלגוריתם מתחיל מאיבר זה ומוצא את k העוקבים לו.

מהו זמן הריצה ביחס למשתנים k ו-h (גובה העץ)? האם יש חסם עליון טוב יותר מ-h*k? מישהו אמר לי שזה k+h אבל לא נראה לי הגיוני...  אשמח לעזרתכם!