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


חסם תחתון על אורך המסלול הארוך ביותר

עריכה

שאלה

עריכה

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



 

כדאי לדעת:

שים לב להשלכה - סיבוכיות חיפוש בעץ במקרה הגרוע היא  .

תשובה

עריכה

הוכחה א'

עריכה

נגדיר את אורך המסלול הארוך ביותר כ , ונשאל את השאלה הבאה: בעץ שגובהו (אורך המסלול הארוך ביותר משורש לעלה)  , כמה צמתים אפשר לשים לכל היותר?

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

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

הוכחה ב' (מבוססת על מגבלות דחיסה)

עריכה
 

שקלו לדלג על נושא זה

תוכל ללמוד את חומר הקורס גם בלי הוכחות מסוג זה.



נגדיר את אורך המסלול הארוך ביותר כ 

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



משפט:

בכל שיטת קידוד, יש הודעה אחת לפחות שארכה  .


(הטענה נובעת משיקולים קומבינטוריים דומים מאד לאלה של החסם התחתון על מיון מבוסס-השוואות שראינו.)

מצד שני, כל עץ חיפוש בינרי יכול לשמש לקידוד צומת. השולח מחפש את הצומת בעץ, מהצומת למטה (כפי שראינו בחיפוש בעץ בינרי). בכל צומת, אם הוא פונה שמאלה הוא מסמן 0, ואם פונה ימינה, הוא מסמן 1. השולח משדר את רצף הביטים למקבל. ברור שהמקבל יכול מתוך רצף הביטים (והעץ) למצא את הצומת המתאים.

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

זמני הריצה של צורות המעבר

עריכה

שאלה

עריכה

נתון עץ חיפוש בינרי בעל   צמתים. אנא הוכח שכ"א מאלגוריתמי המעבר על כל צמתי העץ (לדוגמה Pre-Order) פועל בזמן  .


הנחיות

ההוכחות לאלגוריתמי המעבר השונים כמעט זהות. בחר אלגוריתם מעבר אחד, והוכח את הטענה לגביו.

תשובה

עריכה

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

תכונת מעבר In-order

עריכה

שאלה

עריכה

אנא הוכח שמעבר In-Order מדפיס את מפתחות העץ בסדר עולה.

תשובה

עריכה

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

עץ דחוס

עריכה

שאלה

עריכה

הגדרה:

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

אנא הוכח שזמן חיפוש איבר בעץ דחוס הוא אופטימאלי (מבחינת סדר גדילה) במקרה הגרוע ביותר.

תשובה

עריכה

זמן הריצה של 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 צריך   איטרציות בעץ דחוס, ולכן זהו חסם מלעיל על זמן ריצת חיפוש בעץ דחוס. מצד שני, בחסם תחתון על אורך המסלול הארוך ביותר ראינו בכל עץ חיפוש בינרי בעל   איברים, יש מסלול אחד לפחות בעל   איברים, וזהו חסם תחתון כללי על חיפוש בעץ במקרה הגרוע. החסמים, לכן, מתלכדים כאן.


יחס צאצא-הורה

עריכה

שאלה

עריכה

נתון עץ חיפוש בינרי שבו יש צומת שהמפתח בו   וכן צומת שהמפתח בו  . נניח  .

  1. האם בהכרח הצומת של   הוא צאצא של הצומת של  ?
  2. רוצים לפתח שיטה לקבוע חד-חד משמעית האם   הוא צאצא של הצומת של   בזמן  . נניח בנוסף שממשק הצומת הורחב, וכולל גם את In-Order-Num(nd) המחזיר את סדרו של nd במעבר in-order,‏ Post-Order-Num(nd) המחזיר את סדרו של nd במעבר post-order, וDescendants(nd), המחזיר את מספר הצאצאים הכולל בתת העץ של nd (כולל nd עצמו; לדוגמה אם לnd אין ילדים, אז מספר הצאצאים הוא 1).
    1. אנא הראה שאף פונקציה בנפרד איננה מספיקה לקבוע חד-משמעית יחס זה.
    2. אנא מצא שילוב פונקציות שיספיק לקביעה חד משמעית.

תשובה

עריכה

משפט כללי

עריכה

כדי לפתור את התשובה, נוכיח ראשית את המשפט הפשוט הבא:



משפט:

בעץ חיפוש בינרי בעל מפתחות שונים זה מזה, נניח שצומת   מחזיק מפתח כלשהו. אז:

  1. הצאצאים השמאליים של   מכילים כולם מפתחות קטנים ל .
  2. יש עוד צמתים עם מפתחות קטנים מ  מעבר לכך אם ורק אם   הוא צאצא ימני (לאו דווקא ישיר) של צומת כלשהו.


להלן דוגמה למה שהמשפט אומר.



דוגמה:

בתרשים הבא,   אינו צאצא ימני של אף צומת. צמתי המפתחות הקטנים ממנו (הצבועים באפור), כולם בתת העץ הימני שלו.

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

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

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


 

עכשיו תורכם:

השתמש בתכונת הBST כדי להוכיח את המשפט.

הקשר ללא מידע נוסף

עריכה

מהמשפט הכללי ברור שאי אפשר לקבוע האם הצומת של   הוא צאצא של הצומת של  . ייתכן שהצומת של   הוא צאצא שמאלי של הצומת של  , אך אם הצומת של   הוא צאצא ימני של צומת כלשהו, ייתכן שהצומת של   הוא צאצא שמאלי של אותו הצומת.

הקשר עם מידע נוסף

עריכה

ראשית, ברור שכל אחד בנפרד מסדרו של צומת במעבר in-order,‏ post-order,‏ או מספר צאצאיו, אינו מספיק כדי לקבוע יחס צאצא-אב.

נתבונן שוב במקרה בו צומת   הוא צאצא ימני של צומת  .

 
מיקום צמתים בעלי מפתחות קטנים מצומת נתון - צאצא ימני.
  1. אם  , אז   יודפס לפני   במעבר in-order בכל מקרה. אבל אם  , אז   יכול להיות צאצא שמאלי של  , או צאצא שמאלי של הורה של   (לדוגמה  ).
  2. באופן דומה, אם  , אז   יודפס לפני   במעבר post-order בכל מקרה. אבל שוב, אם  , אז   יכול להיות צאצא שמאלי של  , או צאצא שמאלי של הורה של   (לדוגמה  ).
  3. כפי שהתרשים מראה, אם  , אין בהכרח שום קשר בין מספר האיברים בתת-העץ של   לבין זה של  .

לעומת זאת, השילוב של סדר post-order וdescendants מספיק.



משפט:

נגדיר:

  1.   הוא מספר הpost-order של ילדו השמאלי של  .
  2.   הוא מספר הdescendants של ילדו השמאלי של  .

אז כל צומת בתת העץ השמאלי הוא בעל מספר post-order ב .


הוכחה: מספרי הpost-order של ילדו השמאלי של   הם   מספרים עוקבים, שהאחרון שבהם הוא  .

 

מהמשפט האחרון ברור כיצד יש למצוא האם צומת כלשהו nd-y הוא צאצא של צומת כלשהו nd-x, בהנחה שתוכן הראשון הוא  , תוכן השני הוא  , ו :

  1. אם לnd-x אין ילד שמאלי - התשובה שלילית.
  2. אחרת:
    1. קובעים כ  את Postorder-Num(nd.l-child).
    2. קובעים כ  את Descendants(nd.l-child).
    3. בודקים האם {Postorder-Num(nd-y) גדול או שווה ל .


 

עכשיו תורכם:

חשוב האם שילובי פונקציות שונים יפתרו את הבעיה גם כן.


מציאת איברי קצה בעץ דחוס

עריכה

שאלה

עריכה

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

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

שים לב שתשובתך אמורה להיות נכונה לכל  .

תשובה

עריכה

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

עריכה

משפט:

הצומת ה  בגובה במסלול השמאלי ביותר בעץ, הוא ראשו של תת-עץ המכיל את   האיברים הקטנים ביותר בעץ.


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


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

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

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

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

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

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


 

מהמשפט הקודם נובע שהאיבר ה  הקטן ביותר נמצא בתת עץ שראשו הוא צומת בגובה   במסלול השמאלי ביותר.

שינויים בעץ

עריכה

נוסיף לעץ עוד (מצביע ל)צומת הקטן ביותר, 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


עץ Foo-Bar

עריכה

שאלה

עריכה

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

  1. כל צומת הוא אחד משני סוגים: צומת Foo או צומת Bar.
    1. צומת Bar מחזיק מפתח אחד ו(עד ל)2 ילדים (כמו הצמתים הרגילים שראינו).
    2. צומת Foo מחזיק 2 מפתחות ו(עד ל3 ילדים.
  2. העץ מקיים את את תכונת הFoo-Bar - לכל צומת x:
    1. כל מפתח בתת-עץ שמאלי של מפתח כלשהו, קטן או שווה לו.
    2. כל מפתח בתת-עץ ימני של מפתח כלשהו, גדול או שווה לו.
  3. כל המסלולים משורש העץ לעלה ריק (Nil) בעל אותו אורך בדיוק.



דוגמה: צומת Bar

 
צומת Bar.



דוגמה: צומת Foo

 
צומת Foo.



דוגמה: עץ Foo-Bar

להלן דוגמה לעץ Foo-Bar תקין. בעץ זה 3 צמתים (2 מסוג Bar, ו1 מסוג Foo). יש לו 4 מפתחות, וגבהו 2.

 
עץ Foo-Bar.


אנא הוכח שעץ Foo-Bar הוא לוגריתמי: אם יש בו   מפתחות וגבהו הוא  , אז  .


 

שימו לב:

אל תתייחס לשאלה כיצד ליצור עץ כזה, או כיצד להכניס ולהוציא מפתחות ממנו - זה לא רלוונטי.

תשובה

עריכה

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

 
 
 
 

זמן הריצה של הפונקציות למעבר על כל הצמתים

עריכה

שאלה

עריכה

אנא הוכח שכל אחת מהפעולות למעבר על כל איברי העץ שראינו Post-Order In-Order, וIn-Order), פועלת בזמן לינארי במספר האיברים בעץ.

תשובה

עריכה

עלינו להראות שיש שני קבועים,   ו  המקיימים   עבור ערכי   גדולים מספיק.

הטענה שקיים     (כלומר  ) ברורה, מפני שאנו יודעים שהפונקציה עוברת על כל אחד מהצמתים, ויש   צמתים עפ"י ההגדרה. נוכיח לכן רק את הטענה לגבי קיומו של  .


הוכחה: (בסיס האינדוקציה) נבחר את בסיס האינדוקציה כ .

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


(מעבר האינדוקציה) נניח שהטענה מתקיימת לכל  .

נזכר שראינו כבר את נוסחת הנסיגה המתאימה לבעיה   (קל לראות זאת גם מהתרשים הבא).

 
מעבר האינדוקציה.

הנוסחה אומרת שקיים   כך שמתקיים  .

נשתמש בנוסחת הנסיגה ובהנחת האינדוקציה, ונקבל

 
 
 


אם נבחר   אז   שלילי, ולכן בהכרח  .


נשים לב שבסיס האינדוקציה הגביל אותנו לבחור  , ומעבר האינדוקציה הגביל אותנו לבחור  .

מכאן יוצא שאכן יש   המתאים לבעיה (למעשה יש אינסוף כאלה) - עלינו פשוט לבחור   המקיים


 .

 

נוסחת נסיגה למספר עצי החיפוש הבינריים השונים

עריכה

שאלה

עריכה

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



דוגמה:

נניח שעץ החיפוש מכיל את המפתחות  . יש 2 עצים מתאימים:

 
עצי חיפוש בינריים בעלי המפתחות 1 ו2.

נניח שעץ החיפוש מכיל את המפתחות  . יש 5 עצים מתאימים:

 
עצי חיפוש בינריים בעלי המפתחות 1, 2, ו3.



מהדוגמה נוכל להסיק כי

 ,  ,  .


אנא הוכח את המשפט הבא.



משפט:

אם  , אז  .


תשובה

עריכה

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

נותר רק לחבר את כל האפשרויות עבור כל ערכי   השונים, ו  יכול לקבל את הערכים  .

 

חסם תחתון למספר עצי החיפוש הבינריים השונים

עריכה

שאלה

עריכה

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



דוגמה:

נניח שעץ החיפוש מכיל את המפתחות  . יש 2 עצים מתאימים:

 
עצי חיפוש בינריים בעלי המפתחות 1 ו2.

נניח שעץ החיפוש מכיל את המפתחות  . יש 5 עצים מתאימים:

 
עצי חיפוש בינריים בעלי המפתחות 1, 2, ו3.



מהדוגמה נוכל להסיק כי

 ,  ,  .


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

תשובה

עריכה

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


הוכחה: (מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל)  , ונראה שהיא נכונה גם ל .

 
 
 
 

נפתור  , ונקבל  . עבור  , נקבל שמספיק שיתקיים  .

מבדיקת מספר העצים השונים, עולה שקיים   מתאים גם לבסיס האינדוקציה (המקרים  ).

 

ניתוח שגוי של זמן הריצה של הפונקציות למעבר על כל הצמתים

עריכה

שאלה

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



להלן הוכחה שגויה לכך שכל אחת מהפעולות למעבר על כל איברי העץ שראינו Post-Order In-Order, וIn-Order), פועלת בזמן ריבועי במספר האיברים בעץ.


הוכחה: ההוכחה באינדוקציה על מספר הצמתים,  .

(בסיס האינדוקציה) עבור  ,  .

(מעבר האינדוקציה) כבר ראינו שזמן הריצה נתון ע"י נוסחת הנסיגה  . נשמתש בהנחת האינדוקציה, ונקבל

T(n) = \Theta(i^2) + \Theta((n - i)^2)

 

מה בעייתי בהוכחה הבאה לכך שזמן הריצה הוא לינארי?

תשובה

עריכה

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