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

זמן הריצה של 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

אם מספר הצמתים בתת עץ בגובה $\displaystyle h$ הוא $\displaystyle \Theta (2^{h})$, אז קיים קבוע $\displaystyle c>0$, כך שמספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h}$. נשים לב שבכל איטרציה, אם הצומת לא נמצא (7-8), אז באיטרציה הבאה נמצאים בצומת שגובהו נמוך ב1(בגלל 3-4 או 5-6). לכן:

1. באיטרציה הראשונה, מספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h}$.
2. באיטרציה השניה, מספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h-1}={\frac {c}{2}}\cdot 2^{h}$.
3. באיטרציה השלישית, מספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h-2}={\frac {c}{4}}\cdot 2^{h}$.
4. ...

נקח $\displaystyle i=\left\lceil h+\log(c)\right\rceil$. אז $\displaystyle c\cdot 2^{h-i}=2^{h+\log(c)-\left\lceil h+\log(c)\right\rceil }\leq 1$, ולכן ב$\displaystyle \Theta (h)$ איטרציות נגיע לתת-עץ בגודל 1 (צומת יחיד).

בפרט, אם ניקח עץ בעל $\displaystyle n$ איברים, אז $\displaystyle n=\Theta (2^{h})$, ולכן $\displaystyle h=\Theta (\log(n))$.

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

אופטימאליות

כבר ראינו שMember צריך $\displaystyle O(\log(n))$ איטרציות בעץ דחוס, ולכן זהו חסם מלעיל על זמן ריצת חיפוש בעץ דחוס. מצד שני, בחסם תחתון על אורך המסלול הארוך ביותר ראינו בכל עץ חיפוש בינרי בעל $\displaystyle n$ איברים, יש מסלול אחד לפחות בעל $\displaystyle \Omega (\log(n))$ איברים, וזהו חסם תחתון כללי על חיפוש בעץ במקרה הגרוע. החסמים, לכן, מתלכדים כאן.