כמה שאלות על AVL TREE

[מתכNET]

כמה שאלות על AVL TREE

1.יכול להיות שמשתמשים במונחים אחרים לתאר את פעולת האיזון? אני קראתי ש RR זה אומר RIGHT OF RIGHT כלומר הצומת ש הפר את האיזון הוא הצומת הימני בתת עץ ימני נראה לי שיש כאלה שאומרים RR מתכוונים ROTATE RIGHT. אבל אם הצומת שהפר את האיזון הוא הימני בתת העץ אז כיוון הסיבוב הוא שמאלה. 2.האם ישנה דרך לבדוק אם ביצעתי את אוסף הפעולות על AVL TREE באופן נכון? תודה.

 

[johnny d]

2. לכתוב תוכנה שבודקת.

 

[מתכNET]

לבדוק במבחן הכוונה

 

[danby]

אוסף הפעולות נכון אם"ם

העץ ממשיך להיות מאוזן בסוף פעולת ההכנסה / הוצאה.

 

[מתכNET]

אוקי,שאלת הבהרה.

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

 

[danby]

כמה הבהרות

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