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

מיקום הצומת הk-קטן ביותר

משפט: הצומת ה$\displaystyle h$ בגובה במסלול השמאלי ביותר בעץ, הוא ראשו של תת-עץ המכיל את $\displaystyle \Theta (2^{h})$ האיברים הקטנים ביותר בעץ.

תת עץ של הצומת בגובה h במסלול השמאלי.

הוכחה: היות שהעץ הוא דחוס, אז צומת בגובה $\displaystyle h$ (בפרט אחד במסלול השמאלי ביותר בעץ), מכיל $\displaystyle \Theta (2^{h})$ איברים.

כעת נוכיח שהאיברים בתת-עץ הם האיברים הקטנים ביותר בעץ.

אם הצומת הוא ראש העץ, אז ברור שאין איברים גדולים מהם (כי אין איברים אחרים מהם).

אם הצומת אינו ראש העץ, אז יש לו אב, $\displaystyle a$.

מיקום צמתים בעלי מפתחות קטנים מצומת נתון - לא צאצא ימני.

נשים לב ש$\displaystyle a$ אינו צאצא ימני של אף צומת (מדוע?), ולכן כל האיברים הקטנים ממנו נמצאים בתת עץ השמאלי שלו.

מהמשפט הקודם נובע שהאיבר ה$\displaystyle k$ הקטן ביותר נמצא בתת עץ שראשו הוא צומת בגובה $\displaystyle \Theta (\log(k))$ במסלול השמאלי ביותר.

שינויים בעץ

נוסיף לעץ עוד (מצביע ל)צומת הקטן ביותר, min:

Binary-Search-Tree
	# The root (shoresh).
1	root	
	# Number of nodes.
2	size
	# The smallest node.
3	min

נדאג לעדכן איבר זה בפעולות Insert וDelete (הדבר אינו מסובך במיוחד, ולא נציג את הפסוודו-קוד כאן).

שינויים בMember

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

Member(t, x)
	# Loop upward starting from the leftmost node.

1	nd = t.min

2	while nd.parent != Nil and nd.parent.key < x
3		nd = nd.parent

	# Now loop down again.

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

11	return False