איך לתרגל שאלות עץ אדום-שחור במבני נתונים ומבוא לאלגוריתמים?

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

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

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

מה חשוב לדעת על עץ אדום-שחור לקראת מבחן במבני נתונים ומבוא לאלגוריתמים?

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

מבני נתונים ומבוא לאלגוריתמים - עץ אדום-שחור

סיבוכיות, מבני נתונים בסיסיים ואלגוריתמי מיון וחיפוש

סטטיסטיקות מבחנים

תתי-נושאים של עצי חיפוש

רמת קושי:

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

A

של

2 n

מספרים שלמים ושונים זה מזה בתחום

[0.. n lo g n]

.
בנוסף נתון עץ חיפוש בינארי

T

(לא עץ אדום שחור), ובו

n

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

O (n)

האם כל האיברים בעץ

T

מופיעים במערך

A

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2026 · סמסטר א

★★★★★

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

תכננו מבנה נתונים

D

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

Init(D) - אתחול מבנה ריק. זמן: $O (1)$
Insert(D, x) - הכנסת איבר $x$ למבנה. זמן: $O (lo g n)$
Delete(D, x) - מחיקת איבר $x$ מהמבנה (נתון מצביע לצומת למחיקה). זמן: $O (lo g n)$
Min-Gap(D) - החזרת ההפרש המינימלי בין שני מספרים סמוכים בגודלם הקיימים כרגע במבנה. לדוגמה: אם המבנה מכיל ${1, 5, 9, 20}$ , ההפרש המינימלי הוא 4 (בין 1 ל-5 או בין 5 ל-9). זמן ריצה נדרש: $O (1)$ במקרה הגרוע.

הנחיות:

פרטו באילו מבני נתונים אתם משתמשים (ייתכן שצריך יותר מאחד).
הסבירו כיצד ממומשת כל פעולה, ובפרט כיצד נשמר המידע המאפשר לענות על Min-Gap בזמן קבוע.
שימו לב: ההכנסות והמחיקות צריכות לעדכן את ה-Min-Gap בהתאם.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2026 · סמסטר א

★★★★★

תכנון מבנה נתוניםעץ אדום-שחורמבני נתונים מורחביםעצי חיפושסיבוכיות

תכננו מבנה נתונים

D

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

Init(D) - אתחול מבנה ריק. זמן: $O (1)$
Insert(D, x) - הכנסת איבר $x$ למבנה. זמן: $O (lo g n)$
Delete(D, x) - מחיקת איבר $x$ מהמבנה (נתון מצביע לצומת למחיקה). זמן: $O (lo g n)$
Max-Gap(D) - החזרת ההפרש המקסימלי בין שני מספרים סמוכים בגודלם הקיימים כרגע במבנה. לדוגמה: אם המבנה מכיל ${1, 5, 9, 20}$ , ההפרש המקסימלי הוא 11 (בין 9 ל-20). זמן ריצה נדרש: $O (1)$ במקרה הגרוע.

הנחיות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2026 · סמסטר א

★★★★★

תכנון מבנה נתוניםמבני נתונים מורחביםעץ אדום-שחורסטטיסטיקות סדרסיבוכיות

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

S

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

הצבעה לאירוויזיון מיוצגת ע"י רשומה המכילה שני שדות:
זמן הצבעה Time - סדרה ייחודית של 6 ספרות המבטאת את שעת ההצבעה,
לדוגמא הסדרה 221015 מבטאת את שעת ההצבעה 22:10:15.
שדה בוליאני Vote - שערכו הוא TRUE אם ההצבעה הייתה עבור ישראל.

א) (9 נקודות) תארו את מבנה הנתונים: באיזה מבנה/מבנים תשתמשו? מהו גודלו/גודלם? מהם השדות והמפתחות בהם מהי משמעותם? מומלץ לשרטט.
אם אתם משתמשים בשדות הרחבה לעץ א"ש הראו את העמידה בתנאי 14.1 ע"י נוסחא.

ב) (8 נקודות) כתבו את שגרת BUILD(S, A).
אם אתם משתמשים בשיטת החציונים יש לפרט.

ג) (8 נקודות) כתבו את שגרת COUNT(S, Time1, Time2).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2025 · סמסטר ב

★★★★★

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

בשאלה זו נתייחס לקטע על הישר הממשי באמצעות ההגדרות הבאות:
קטע על הישר הממשי נתון ע"י זוג נקודות-

(a, b)

a \leq b

, שהם נקודת ההתחלה והסיום שלו.
אורך של קטע:

L = b - a

הציעו מבנה

S

אשר מייצג קטעים על הישר הממשי, ושבאמצעותו ניתן לבצע את הפעולות הבאות עם זמני הריצה המצויים ליד כל שגרה.
INSERT(S, (a,b)): מכניס את הקטע

(a, b)

למבנה

S

, רק אם נקודת ההתחלה שלו

a

היא ייחודית, כלומר שונה מכל נקודת התחלה אחרת במבנה, בזמן

O (lo g n)

.
LONGEST(S, a): מחזיר את אורך הקטע (או קטעים) הארוך ביותר במבנה

S

, מבין כל הקטעים שנקודות ההתחלה שלהם גדולות או שוות ל-

a

, בזמן

O (lo g n)

.
הערה: לא ידוע אם קיים קטע עם נקודת ההתחלה המסוימת

a

.
RANGE(S, L_1, L_2): בהינתן שני מספרים שלמים

L_{1}, L_{2}

, מחזיר את מספר הקטעים באורך

L

, כך ש

L_{1} \leq L \leq L_{2}

, בזמן

O (lo g n)

.
הערה: לא ידוע אם קיימים קטעים באורך

L_{1}, L_{2}

במבנה.

א) (9 נקודות) תארו את מבנה הנתונים: באיזה מבנה/מבנים תשתמשו? מהו גודלו/גודלם? מהם השדות והמפתחות בהם ומהי משמעותם? מומלץ לשרטט.
אם אתם משתמשים בשדות הרחבה לעץ א"ש הראו את העמידה בתנאי 14.1 ע"י נוסחא.

ב) (8 נקודות) כתבו את שגרת LONGEST(S, a).

ג) (8 נקודות) כתבו את שגרת RANGE(S, L_1, L_2).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר ב

★★★★★

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

בשאלה זו נתייחס לקטע על הישר הממשי באמצעות ההגדרות הבאות:
קטע על הישר הממשי נתון ע"י זוג נקודות-

(a, b)

a \leq b

, שהם נקודת ההתחלה והסיום שלו.
אורך של קטע:

L = b - a

הציעו מבנה

S

(a, b)

למבנה

S

, רק אם נקודת ההתחלה שלו

a

היא ייחודית, כלומר שונה מכל נקודת התחלה אחרת במבנה, בזמן

O (lo g n)

.
LONGEST(S, a): מחזיר את אורך הקטע (או קטעים) הארוך ביותר במבנה

S

, מבין כל הקטעים שנקודות ההתחלה שלהם גדולות או שוות ל-

a

, בזמן

O (k + lo g n)

, כאשר

k

הוא מספר הקטעים שנקודות ההתחלה שלהם גדולות או שוות ל-

a

.
הערה: לא ידוע אם קיים קטע עם נקודת ההתחלה המסוימת

a

.
RANGE(S, L_1, L_2): בהינתן שני מספרים שלמים

L_{1}, L_{2}

, מחזיר את מספר הקטעים באורך

L

, כך ש

L_{1} \leq L \leq L_{2}

, בזמן

O (lo g n)

.
הערה: לא ידוע אם קיימים קטעים באורך

L_{1}, L_{2}

במבנה.

א. (9 נקודות) תארו את מבנה הנתונים: באיזה מבנה/מבנים תשתמשו? מהו גודלו/גודלם? מהם השדות והמפתחות בהם מהי משמעותם? מומלץ לשרטט.

ב. (8 נקודות) כתבו את שגרת LONGEST(S, a).

ג. (8 נקודות) כתבו את שגרת RANGE(S, L_1, L_2).

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2025 · סמסטר ב

★★★★★

תכנון מבנה נתוניםמבני נתוניםסיבוכיותעץ אדום-שחורעץ סדר סטטיסטימבני נתונים מורחביםחיפוש

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

n

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

הציעו מבנה נתונים

S

התומך בפעולות הבאות בזמני הריצה המצוינים:

I N S E R T (s a l a r y, am o u n t)

: הכנסת סטודנט חדש שהכנסתו החודשית היא

s a l a r y

, ושערך המלגה הנוכחית שהאוניברסיטה מעניקה לו היא

am o u n t

, בזמן

O (lo g n)

I N C R E A S E - A M O U N T (s a l a r y, in cr e a se)

: הוספת הסכום החיובי

in cr e a se

למלגת כל סטודנט שהכנסתו החודשית קטנה או שווה ל-

s a l a r y

ונמצא במבנה, בזמן

O (lo g n)

. תוכלו להניח שקיים במבנה סטודנט שהכנסתו החודשית היא

s a l a r y

A S S E S S - A M O U N T (s a l a r y)

: החזרת המלגה הכוללת לסטודנט שהכנסתו החודשית היא

s a l a r y

, בזמן

O (lo g n)

. תוכלו להניח שקיים במבנה סטודנט שהכנסתו היא

s a l a r y

.

כדי לפתור את הבעיה נחזיק עץ אדום-שחור

T

עם

n

איברים. כל צומת

V

מייצג סטודנט, ומכיל:

V . s a l a r y

: הכנסתו החודשית של הסטודנט, שהיא ייחודית וגם מפתח העץ.

V . am o u n t

: המלגה הראשונית שהסטודנט מקבל.

V . in cr e a se

: תוספת מלגה לכל האיברים בתת העץ השמאלי של

V

. לא כולל

V

עצמו.

א) (5 נקודות) קבעו האם השדה

V . in cr e a se

עומד בתנאי 14.1. אם כן כתבו נוסחא.
ב) (10 נקודות) הראו שהשדה

V . in cr e a se

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

I N C R E A S E - A M O U N T (s a l a r y, in cr e a se)

.

דוגמא: שחר נמצא בתוכנית המלגות, עם הכנסה חודשית 52 ₪, ומלגה ראשונית 600 ₪.
נבצע

I N C R E A S E - A M O U N T (60, 1000)

ואז

I N C R E A S E - A M O U N T (75, 100)

.
כעת

A S S E S S - A M O U N T (52)

יחזיר 1700 ₪ (כי הכנסתו של שחר קטנה מ-60 ₪, ומ-75 ₪).
כעת נכניס את דניאל לתוכנית. הכנסתה החודשית של דניאל היא 59 ש"ח, והמלגה הראשונית שהיא מקבלת היא 1200 ₪. כעת

A S S E S S - A M O U N T (59)

יחזיר 1200 ₪.

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר ב

★★★★★

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

שאלה מותאמת לסמסטר הלימוד
שאלה 6 (25 נקודות) – השאלה מיועדת רק לסטודנטים שלמדו בשנת 2024

תכננו מבנה

S

, שהוא עץ א"ש, שמפתחותיו הם מספרים טבעיים, ושניתן לבצע עליו את הפעולות הבאות:

B U I L D (S, A)

: בניית

S

ממערך ממוין

A

בגודל

n

, בזמן ריצה

O (n)

I N S E R T (S, k)

: מכניס את המפתח

k

למבנה. זמן הריצה

O (lo g n)

H E A V I E S T - P A T H (S)

: החזרת סכום מפתחותיו של המסלול הפשוט הכבד ביותר שמתחיל בשורש, בזמן ריצה

O (n)

T [ni l l]

.

ב) (9 נקודות) כתבו את שגרת

H E A V I E S T - P A T H (S)

.

ג) (8 נקודות) כתבו את שגרת

B U I L D (S, A)

.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר א

★★★★★

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

השאלה מיועדת רק לסטודנטים שלמדו בסמסטר 2025א

הציעו מבנה נתונים

S

אשר מייצג פריטי לבוש בחנות בגדי-מנמ"א, ושבאמצעותו ניתן לבצע את הפעולות הבאות עם זמני הריצה המצויים ליד כל שגרה.
פריט לבוש מיוצג ע"י רשומה המכילה שני שדות:
ברקוד (Barcode) - סדרה ייחודית של 8 ספרות בבסיס 10, ומחיר (Price) - מספר ממשי.
BUILD(S, A) : בניית

S

מתוך מערך לא ממוין בגודל

n

, בזמן

O (n)

.
INSERT(S, z) : הכנסת פריט הלבוש

z

למבנה

S

, בזמן

O (lo g n)

.
SEARCH(S, Barcode) : חיפוש איבר עם הברקוד Barcode במבנה

S

בזמן

O (lo g n)

.
DELETE(S, z) : מחיקת הפריט שאליו מצביע

z

מהמבנה

S

, בזמן

O (lo g n)

.
MAX(S, Barcode1, Barcode2) : החזרת המחיר היקר ביותר לפריט מבין כל הפריטים שהברקוד שלהם הוא בטווח

[B a r co d e 1 \dots B a r co d e 2]

, בזמן

O (lo g n)

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

B a r co d e 1, B a r co d e 2

קיימים ב-

S

.
SALE(S, NewSale, ItemPrice) : ביטול כל מבצע קודם, ועדכון מבצע חדש של הורדת NewSale ₪ מכל פריט שמחירו יקר יותר מ-ItemPrice ₪, בזמן

O (1)

.

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

ב) (8 נקודות) הראו באמצעות נוסחא שהשדה המרחיב עומד בתנאי 14.1.

ג) (8 נקודות) כתבו את שגרת BUILD(S, A). ניתן להשתמש במערך עזר בגודל

O (n)

. יש לפרט איך מאתחלים שדות מרחיבים.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2025 · סמסטר א

★★★★★

תכנון מבנה נתוניםעץ אדום-שחורמבני נתונים מורחביםאסימפטוטיקהסיבוכיותמיון ספרות

שאלה מותאמת לסמסטר הלימוד
שאלה 5 (25 נקודות) – שאלה על החומר המלא ללא מיקוד.

תכננו מבנה

S

, שהוא עץ א"ש מורחב, שמפתחותיו הם מספרים טבעיים, ושניתן לבצע עליו את הפעולות הבאות:

B U I L D (S, A)

: בניית

S

ממערך ממוין

A

בגודל

n

, בזמן ריצה

O (n)

I N S E R T (S, k)

: מכניס את המפתח

k

למבנה. זמן הריצה

O (lo g n)

H E A V I E S T - P A T H (S)

: החזרת סכום מפתחותיו של המסלול הפשוט הכבד ביותר שמתחיל בשורש ומסתיים בעלה, בזמן ריצה

O (1)

.
(מסלול פשוט = מסלול שאינו עובר באף צומת יותר מפעם אחת).

דוגמא: בעץ זה, המסלול הכבד ביותר המתחיל בשורש הוא המסלול 5-2-4-3, וסכום מפתחותיו הוא 14.
(הצמתים השחורים בעץ שחורים באיור והצמתים האדומים בעץ אפורים באיור)

א) (9 נקודות) כאמור נרצה להשתמש בעץ אדום שחור מורחב על מנת לפתור את הבעיה.
באיזה שדה הרחבה תשתמשו בכל צומת ומהי משמעותו.
אם יש מבנים ומשתני עזר נוספים - מהי משמעותם ואיך הם מאותחלים?

ב) (3 נקודות) הראו שהשדה המרחיב עומד בתנאי 14.1.

ג) (4 נקודות) כתבו את שגרת

H E A V I E S T - P A T H (S)

.

ד) (9 נקודות) כתבו את שגרת

B U I L D (S, A)

. יש לפרט כיצד מאותחלים שדות מרחיבים.

הערות:

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד ב · 2025 · סמסטר א

★★★★★

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

שאלות עץ אדום-שחור במבני נתונים ומבוא לאלגוריתמים עם פתרונות

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