עצים בינארים

[david245]

עצים בינארים

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

 

[עדין ר]

רמז

נניח ש-n הוא גודל תת-העץ השמאלי. מה קורה אם i<n? מה קורה אם i==n? ומה קורה אם i>n? עוד רמז: רקורסיה.

 

[אופסשםמשתמש]

אני מרגיש טמבל

אבל ב ו ג' פתירים בסיבוכיות LOG ?

 

[vinney]

לא נראה לי

כי צריך להשתמש בפונקציה מא' אבל מצד שני, אם העץ לא משתנה, אתה לא צריך להריץ את הפונקציה כל פעם, אלא רק כשאתה בונה את העץ, ואז זה יהיה בlog n באמת.

 

[אופסשםמשתמש]

נניח אני יודע את הגודל של העץ

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

 

[עדין ר]

ענית לעצמך ../images/Emo13.gif

 

[Desslok of Gamilon]

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

 

[vinney]

נכון../images/Emo13.gif

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

 

[InForN]

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

אלא עם לולאה פשוטה. לא ניסיתי אבל אני חושב שזה אפשרי ואפילו עדיף מרקורסיה.

 

[InForN]

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

כל עוד i<>n בצע { n=גודל(שורש.שמאל) אם (i<n) אזי { שורש=שורש.שמאל } אם (i>n) אזי { i=i-n-1 שורש=שורש.ימין } } החזר שורש.ערך