מבני נתונים - עצים בינאריים
מבני נתונים, אלגוריתמים וסיבוכיות
תתי-נושאים של עצים בינאריים
רמת קושי:
להלן הגדרת משפחת עצים בשם עצים רקורסיביים מסדר שני (ראו תרשים):
סעיף א' (10 נקודות)
הוכיחו באינדוקציה על המבנה כי גובה העץ הוא .
סעיף ב' (15 נקודות)
הוכיחו כי משפחת העצים הרקורסיביים מסדר שני היא משפחה מאוזנת.
תזכורת: משפחה של עצים נקראת מאוזנת אם לכל עץ במשפחה גובה העץ הוא , כאשר הוא מספר הצמתים בעץ.
סעיף א' (10 נקודות)הוכיחו באינדוקציה על המבנה כי גובה העץ הוא .
סעיף ב' (15 נקודות)
הוכיחו כי משפחת העצים הרקורסיביים מסדר שני היא משפחה מאוזנת.
תזכורת: משפחה של עצים נקראת מאוזנת אם לכל עץ במשפחה גובה העץ הוא , כאשר הוא מספר הצמתים בעץ.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד א · 2026 · סמסטר א
★★★★★
רקורסיהנוסחת נסיגההוכחת נכונותסימון אסימפטוטיBig-Oעצים בינאריים
שאלה 2:
נתונה מחרוזת מעל האלפבית נסמן ב- את שכיחות הופעתה של האות במחרוזת .
סעיף א': (5 נקודות)
נניח כי היא חזקה של 2.
הראו כי קיימת בחירה של שכיחויות לאותיות כך שהעץ המתאים לקוד התחיליות האופטימלי הוא עץ בינארי שלם, כלומר כל העלים בעץ באותו עומק.
סעיף ב': (5 נקודות)
נניח כי מספר האותיות הוא .
להלן נתון מבנה של עץ בינארי מלא:
[איור של עץ הושמט]
הציעו רשימת שכיחויות עבור האותיות כך שעץ זה יכול להיות העץ המייצג קוד תחיליות אופטימלי עבור שכיחויות אלו. נמקו בקצרה את בחירתכם.
כתבו את השכיחויות על העץ עצמו.
סעיף ג': (15 נקודות)
הוכיחו כי לכל עץ בינארי מלא עם עלים קיימת רשימת שכיחויות שעבורה הוא עץ קוד תחיליות אופטימלי.
נתונה מחרוזת מעל האלפבית נסמן ב- את שכיחות הופעתה של האות במחרוזת .
סעיף א': (5 נקודות)
נניח כי היא חזקה של 2.
הראו כי קיימת בחירה של שכיחויות לאותיות כך שהעץ המתאים לקוד התחיליות האופטימלי הוא עץ בינארי שלם, כלומר כל העלים בעץ באותו עומק.
סעיף ב': (5 נקודות)
נניח כי מספר האותיות הוא .
להלן נתון מבנה של עץ בינארי מלא:
[איור של עץ הושמט]
הציעו רשימת שכיחויות עבור האותיות כך שעץ זה יכול להיות העץ המייצג קוד תחיליות אופטימלי עבור שכיחויות אלו. נמקו בקצרה את בחירתכם.
כתבו את השכיחויות על העץ עצמו.
סעיף ג': (15 נקודות)
הוכיחו כי לכל עץ בינארי מלא עם עלים קיימת רשימת שכיחויות שעבורה הוא עץ קוד תחיליות אופטימלי.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד ב · 2026 · סמסטר א
★★★★★
אלגוריתמים חמדנייםעצים בינארייםהוכחת נכונותאינדוקציה
(בונוס - 3 נקודות) סמנו את התשובה הנכונה: בעץ בינארי בעל קודקודים פנימיים יש בהכרח עלים.
נכון / לא נכון
נכון / לא נכון
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד ב · 2024 · סמסטר ב
★★★★★
עצים בינארייםהוכחת נכונות
יהי עץ בינארי. נאמר כי סימטרי, אם העץ סימטרי ביחס לשורש העץ.
הצע אלגוריתם לינארי המקבל כקלט עץ בינארי ומחזיר אמת אם העץ סימטרי, אחרת יחזיר שקר.
הנח שלכל צומת בעץ יש רק 3 שדות מידע: מפתח (אין חשיבות למידע לפתרון הבעיה), מצביע לבן הימני ומצביע לבן השמאלי.
לדוגמא, עבור העץ הבא האלגוריתם יחזיר אמת.
הצע אלגוריתם לינארי המקבל כקלט עץ בינארי ומחזיר אמת אם העץ סימטרי, אחרת יחזיר שקר.
הנח שלכל צומת בעץ יש רק 3 שדות מידע: מפתח (אין חשיבות למידע לפתרון הבעיה), מצביע לבן הימני ומצביע לבן השמאלי.
לדוגמא, עבור העץ הבא האלגוריתם יחזיר אמת.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד ב · 2021 · סמסטר ב
★★★★★
עצים בינארייםרקורסיהסיבוכיותסיבוכיות זמן
כתוב אלגוריתם המקבל כקלט מצביע לשורש עץ בינארי כמעט שלם , ומחזיר כפלט את מספר הצמתים שיש להוסיף ברמה התחתונה של העץ על מנת שיהיה עץ שלם. שימו לב, אם עץ הקלט שלם יוחזר הערך 0.
ניקוד מלא ינתן לאלגוריתם נכון שזמן הריצה שלו: כאשר גובה העץ .
ניקוד חלקי ינתן לאלגוריתם נכון שזמן ריצתו .
גם פתרון נכון שזמן ריצתו יזכה בנקודות, כאשר את מספר הצמתים בעץ (אבל פחות מהמקרים הקודמים שפורטו).
הנח שלכל צומת בעץ יש רק 3 שדות מידע: מפתח (אין חשיבות למידע לפתרון הבעיה), מצביע לבן הימני ומצביע לבן השמאלי.
לדוגמא, עבור העץ הבא האלגוריתם יחזיר 1.
ניקוד מלא ינתן לאלגוריתם נכון שזמן הריצה שלו: כאשר גובה העץ .
ניקוד חלקי ינתן לאלגוריתם נכון שזמן ריצתו .
גם פתרון נכון שזמן ריצתו יזכה בנקודות, כאשר את מספר הצמתים בעץ (אבל פחות מהמקרים הקודמים שפורטו).
הנח שלכל צומת בעץ יש רק 3 שדות מידע: מפתח (אין חשיבות למידע לפתרון הבעיה), מצביע לבן הימני ומצביע לבן השמאלי.
לדוגמא, עבור העץ הבא האלגוריתם יחזיר 1.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד א · 2020 · סמסטר ב
★★★★★
עצים בינארייםרקורסיהסיבוכיות זמןנוסחת נסיגה
ענה/י נכון/לא נכון לכל אחד מהסעיפים הבאים. מותר אך לא חובה לכתוב הסבר עד אורך של שורה לכל סעיף.
א) לכל קיים עץ חיפוש בינארי של איברים שגובהו
ב) ברשימה מקושרת באורך כדאי לשמור גם מצביע לאיבר האמצעי, כי בהשקעה של שטח, קיבלנו אפשרות לבצע חיפוש בינארי.
ג) באלגוריתם של Boyer & Moore בהגדרה של , נחפש לכל סיפא מופע מוקדם יותר, אך נדרוש שהאות הקודמת לסיפא תהיה שונה. אם נוריד דרישה זאת, האלגוריתם יכול לשגות.
ד) בטבלת Hash בגודל 2500 הוכנסו 1000 איברים ע"י שימוש ב־Hashing Uniform. הזמן הממוצע לחיפוש מוצלח, כאשר לכל איבר שהוכנס הסתברות שווה להופיע בחיפוש, הוא .
ה) נתון B-tree מדרגה שמכיל איברים. אם נכניס איבר נוסף לעץ ובשלב הבא נבטל אותו, העץ שמתקבל אחרי ביצוע שתי הפעולות יהיה תמיד זהה לעץ ממנו יצאנו.
ו) החסם התחתון למיזוג 2 סדרות ממוינות, אחת באורך ואחת באורך 3 הוא .
ז) לכל קיים עץ AVL המכיל קודקודים שסריקת ה־post-order שלו היא סדרה ממוינת.
ח) בכל רשימה מקושרת, קיים איבר אליו ניתן לגשת ב־ זמן.
ט) לכל קיים עץ בינארי המכיל בדיוק עלים ו־ קודקודים פנימיים.
י) זמן חיפוש איבר ברשימת דילוגים (skip-list) הוא במקרה הגרוע.
א) לכל קיים עץ חיפוש בינארי של איברים שגובהו
ב) ברשימה מקושרת באורך כדאי לשמור גם מצביע לאיבר האמצעי, כי בהשקעה של שטח, קיבלנו אפשרות לבצע חיפוש בינארי.
ג) באלגוריתם של Boyer & Moore בהגדרה של , נחפש לכל סיפא מופע מוקדם יותר, אך נדרוש שהאות הקודמת לסיפא תהיה שונה. אם נוריד דרישה זאת, האלגוריתם יכול לשגות.
ד) בטבלת Hash בגודל 2500 הוכנסו 1000 איברים ע"י שימוש ב־Hashing Uniform. הזמן הממוצע לחיפוש מוצלח, כאשר לכל איבר שהוכנס הסתברות שווה להופיע בחיפוש, הוא .
ה) נתון B-tree מדרגה שמכיל איברים. אם נכניס איבר נוסף לעץ ובשלב הבא נבטל אותו, העץ שמתקבל אחרי ביצוע שתי הפעולות יהיה תמיד זהה לעץ ממנו יצאנו.
ו) החסם התחתון למיזוג 2 סדרות ממוינות, אחת באורך ואחת באורך 3 הוא .
ז) לכל קיים עץ AVL המכיל קודקודים שסריקת ה־post-order שלו היא סדרה ממוינת.
ח) בכל רשימה מקושרת, קיים איבר אליו ניתן לגשת ב־ זמן.
ט) לכל קיים עץ בינארי המכיל בדיוק עלים ו־ קודקודים פנימיים.
י) זמן חיפוש איבר ברשימת דילוגים (skip-list) הוא במקרה הגרוע.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד א · 2018 · סמסטר ב
★★★★★
עץ חיפוש בינארירשימות מקושרותחיפוש בינאריאלגוריתמיםטבלאות גיבובעצי Bמיוןחסם תחתון למיוןעצי AVLעצים בינארייםסיבוכיות זמן
הוכח/י או הפרך/י את הטענות הבאות לגבי קביעת צורת העץ ע"י הסדרה שמתקבלת ממעבר postorder, והדגם/י את תשובתך לכל אחד מהסעיפים, אם אפשר, עבור הסדרה
א) לכל סדרה של ערכים שונים, קיים בדיוק עץ בינרי אחד שבמעבר postorder על קדקודי העץ מתקבלת הסדרה .
ב) לכל סדרה של ערכים שונים, קיים בדיוק עץ חיפוש בינרי אחד שבמעבר postorder על קדקודי העץ מתקבלת הסדרה .
ג) לכל סדרה של ערכים שונים, קיים בדיוק עץ AVL אחד שבמעבר postorder על קדקודי העץ מתקבלת הסדרה .
א) לכל סדרה של ערכים שונים, קיים בדיוק עץ בינרי אחד שבמעבר postorder על קדקודי העץ מתקבלת הסדרה .
ב) לכל סדרה של ערכים שונים, קיים בדיוק עץ חיפוש בינרי אחד שבמעבר postorder על קדקודי העץ מתקבלת הסדרה .
ג) לכל סדרה של ערכים שונים, קיים בדיוק עץ AVL אחד שבמעבר postorder על קדקודי העץ מתקבלת הסדרה .
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד ב · 2018 · סמסטר ב
★★★★★
עצים בינארייםעץ חיפוש בינאריעצי AVL
(20 נקודות) צייר את עץ ה AVL עבור סדרת הנתונים הבאים (מימין לשמאל):
5, 20, 7, 6, 1. תאר את התהליך.
5, 20, 7, 6, 1. תאר את התהליך.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד א · 2017 · סמסטר ב
★★★★★
עצי AVLעץ חיפוש בינאריעצים בינארייםמעקב אחר אלגוריתם
יהי עץ בינארי עם צמתים. נסמן ב־ את תת העץ ששורשו הבן השמאלי של ונסמן ב־ את העץ ששורשו הבן הימני של . קודקוד יקרא 'מאוזן' אם מתקיים התנאי הבא: כאשר מסמן את מספר הקודקודים בעץ .
כתוב/י אלגוריתם יעיל למציאת כל הקודקודים בעץ שהם עצמם אינם מאוזנים, אבל כך שכל צאצאיהם כן מאוזנים. מה הסיבוכיות של האלגוריתם?
כתוב/י אלגוריתם יעיל למציאת כל הקודקודים בעץ שהם עצמם אינם מאוזנים, אבל כך שכל צאצאיהם כן מאוזנים. מה הסיבוכיות של האלגוריתם?
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד ב · 2016 · סמסטר ב
★★★★★
עצים בינארייםרקורסיהסיבוכיות זמןסיבוכיות מקוםDFS
א) צייר/י עץ שעבור ב inorder וב postorder יתנו את הסדרות ו- בהתאמה. ב) מה הסדרה שתתקבל ממעבר preorder על עץ זה? ג) האם ניתן לקבוע את העץ על סמך מעברי preorder ו- postorder? הראה/י איך לעשות זאת או תן/י דוגמא נגדית.
העתק שאלה
שתף שאלה
סמן כחשוב
סמן כבוצע
אוניברסיטת בר-אילןמועד א · 2016 · סמסטר ב
★★★★★
עצים בינארייםעץ חיפוש בינארי
שאלות עצים בינאריים במבני נתונים עם פתרונות
שאלות תרגול במבני נתונים בנושא עצים בינאריים ממבחנים של אוניברסיטת בר-אילן. השאלות ממוינות לפי רמת קושי, עם פתרונות לבדיקה עצמית - כך שניתן ללמוד מטעויות ולהבין את דרך הפתרון לפני הבחינה. ניתן לאתר שאלות חוזרות ולהריץ מבחני סימולציה ממוקדים בנושא עצים בינאריים.