שאלה כללית סיבוכיות מקום+זמן מול קוד יפה (שפת C)

[noodle]

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

כל NODE מכיל מחרוזת, אינדקס ומצביעים לבנים .

הכנסה לעץ: יש לי מונה כמה מחרוזות קיבלתי, נניח שכרגע אני מקבל מחרוזת שהיא המחרוזת ה-53 (קיבלתי 52 מחרוזות עד כה- יש לי 52 צמתים בעץ) אני יוצר NODE בשבילו ומכניס לעץ, אבא שלו יהיה הצומת עם אינדקס 26, והוא יהיה הבן הימני של צומת עם אינדקס 26.

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

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

מקווה שהבהרתי את עצמי.

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

[B.D.B]

אם אתה מכניס ומחפש לפי הסטרינג אז למה משמש האינדקס?

והאם אתה צריך אבא ישיר או גם "אב קדמון"?

[noodle]

אם אתה מכניס ומחפש לפי הסטרינג אז למה משמש האינדקס?

והאם אתה צריך אבא ישיר או גם "אב קדמון"?

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

[B.D.B]

מה?! על הקצאה דינמית ופוינטרים לא שמעת?

[noodle]

מה?! על הקצאה דינמית ופוינטרים לא שמעת?

יש לי תחושה שאתה בכלל לא קורא מה שאני רושם או שאתה קורא רק חלקים

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

הכנסה לעץ: יש לי מונה כמה מחרוזות קיבלתי, נניח שכרגע אני מקבל מחרוזת שהיא המחרוזת ה-53 (קיבלתי 52 מחרוזות עד כה- יש לי 52 צמתים בעץ) אני יוצר NODE בשבילו ומכניס לעץ, אבא שלו יהיה הצומת עם אינדקס 26, והוא יהיה הבן הימני של צומת עם אינדקס 26.

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

[B.D.B]

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

[noodle]

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

אני לא משתמש במערך אבל נעזוב את זה.

אז איך ניתן לבנות עץ בינארי רגיל בלי אינדקס, כאשר אתה מקבל את השורש ואת הצומת שאתה רוצה להכניס?

[B.D.B]

אתה ממיין לפי הערך שאתה רוצה להכניס, עד שאתה מגיע ל-node שהבן שלו הוא null ומכניס שם.

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

[noodle]

ידעתי שאתה לא קורא את כל התגובות שלי

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

העץ ממולא משמאל לימין.

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

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

[Gil28]

אתה יכול להשתמש במערך של ביטים בתור המסלול בעץ. שמאל זה 0 וימין זה 1. ברגע שהגעת ל-11111 למשל אתה יודע שסיימת לבנות

רמה בעץ ותתחיל עם 111110.

[B.D.B]

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

[noodle]

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

התרגיל מתחיל כך: "בנו עץ...".

[B.D.B]

אז איך אתה אמור למלא את העץ, משמאל לימין?

[noodle]

ידעתי שאתה לא קורא את כל התגובות שלי

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

העץ ממולא משמאל לימין.

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

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

[B.D.B]

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

האב של node באינדקס i הוא תמיד i/2 (בערך תחתון) הבנים של node באינדקס i הם i*2 ו-i*2+1.

קח בחשבון שאינדקסים של ה-node-ים מתחילים ב-1 ושל המערך ב-0.