מימוש עץ AVL ב++C.

[pain_killer12]

חברים, כבר יצאה לי הנשמה.

קיבלנו תרגיל לממש עץ AVL ב++C. כל העניין הזה של לשמור על איזון העץ עם כל הסיבובים והעניינים

כבר אין לי מושג מה לעשות.

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

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

בכל הקודקודים במסלול מהשורש אני צריך לקדם את איזון (אם הלכתי ימינה בקודקוד אז אני מעלה אותו ב1

אם הלכתי שמאלה אני מוריד ב1)?

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

מישהו אולי מימש פעם?

[Zelig]

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

הנה ציטוט של Steve Yegge שיעזור לך להרגיש יותר טוב:

In my Data Structures course in college, when we got to AVL trees, my prof turned and wrote on the board, in huge, clear letters:

AVL Trees are EVIL

...and that's all we had to learn about them. He had us implement red/black trees and splay trees instead. To this day, I have no idea how threaded AVL trees work. But if that's OK with Dan Weld, it's OK with me.

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

עצי AVL גורמים כאב ראש לכולם. רוב מימושי STL שראיתי משתמשים ב-red black.

[pain_killer12]

חחח טוב נחמד לדעת שאני לא היחיד שסובל.

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

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

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

תודה רבה לך זליג על הטרחה =]

[מסבחה]

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

זה כתוב ב-C ולא ב-C++ אבל המימוש נכון, הקוד ברור (לדעתי) ויש קובץ הסבר בעברית.

מקווה שזה יעזור...

[Zelig]

אני אנסה לחפור בדיסקים ישנים עם גיבויים מהעבר. היה לי AVL כתוב ב-C++, עם templates.

אם יש, אני אשים אותו פה.

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

[pain_killer12]

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

העדפתי לא להסתכן ולעשות לבד + לקחת קצת רעיונות, אבל נתקלתי במבוי סתום =\

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

קבלו ח"ח.

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

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

[Zelig]

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

[pain_killer12]

תודה זליג ומסבחה.

אבל אני תקוע בפונקציית ההסרה מהעץ.

אם מישהו יכול לעזור לי עם הפונקציה של ההסרה

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

אם למישהו יש קוד, אשמח אם תעלו.

תודה מראש.

[attachment deleted by admin]

[pain_killer12]

אבל אני תקוע בפונקציית ההסרה מהעץ.

אם מישהו יכול לעזור לי עם הפונקציה של ההסרה

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

אם למישהו יש קוד, אשמח אם תעלו.

תודה מראש.