עצי AVL מינימליים

[מתכNET]

עצי AVL מינימליים

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

 

[n0b0dy]

AVL

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

 

[מתכNET]

אם כך עץ בינארי כמעט שלם הוא

AVL מינימלי?

 

[מתכNET]

נראה לי שההגדרה לא מדויקת

לפי ההגדרה שנתת עץ בינארי כמעט שלם ועץ בינארי שלם שניהם בגובה H הם מינימליים באותה מידה. נראה לי שעץ AVL מינימלי בגובה H הוא העץ בגובה H עם מספר הצמתים הקטן ביותר.

 

[n0b0dy]

תיקון

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

 

[מתכNET]

מהחוברת של הטכניון הבנתי ש:

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