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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

זמן הריצה של Member[עריכה]

להלן פסוודו-קוד אפשרי לMember:

# Searches a tree (t) for a key (k).
# Returns whether the tree contains the key.
Find(t, k)
1	nd = t.root

ְ2	while nd != Nil
3		if k < nd.key
4			nd = nd.l-child
5		else if k > nd.key
6			nd = nd.r-child
7		else
8			return True
		
9	return False

אם מספר הצמתים בתת עץ בגובה הוא , אז קיים קבוע , כך שמספר הצמתים בתת-העץ הוא לכל היותר . נשים לב שבכל איטרציה, אם הצומת לא נמצא (7-8), אז באיטרציה הבאה נמצאים בצומת שגובהו נמוך ב1(בגלל 3-4 או 5-6). לכן:

  1. באיטרציה הראשונה, מספר הצמתים בתת-העץ הוא לכל היותר .
  2. באיטרציה השניה, מספר הצמתים בתת-העץ הוא לכל היותר .
  3. באיטרציה השלישית, מספר הצמתים בתת-העץ הוא לכל היותר .
  4. ...

נקח . אז , ולכן ב איטרציות נגיע לתת-עץ בגודל 1 (צומת יחיד).

בפרט, אם ניקח עץ בעל איברים, אז , ולכן .



דוגמה:

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

חיפוש בעץ דחוס.


אופטימאליות[עריכה]

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