מדריך לעצי AVL בג'אווה

1. הקדמה

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

2. מהו עץ AVL?

עץ ה- AVL, על שם ממציאיו אדלסון-ולסקי ולנדיס, הוא עץ חיפוש בינארי בעל איזון עצמי.

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

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

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

בואו נגדיר א צוֹמֶת חפץ לעץ שלנו:

צמת מעמד ציבורי {מפתח מפתח int; גובה int; צומת שמאל; צומת מימין; ...}

לאחר מכן, בואו נגדיר את AVLTree:

מחלקה ציבורית AVLTree {שורש הצומת הפרטי; חלל updateHeight (צומת n) {n.height = 1 + Math.max (גובה (n. שמאל), גובה (n.right)); } int גובה (צומת n) {return n == null? -1: n. גובה; } int getBalance (Node n) {return (n == null)? 0: גובה (n.right) - גובה (n. שמאל); } ...}

3. כיצד לאזן עץ AVL?

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

ישנן שתי פעולות לאיזון עץ מחדש:

  • סיבוב נכון ו
  • סיבוב שמאלי.

3.1. סיבוב נכון

נתחיל בסיבוב נכון.

נניח שיש לנו BST הנקרא T1, עם Y כצומת השורש, X כילד שמאל של Y ו- Z כילד הימני של X. בהתחשב במאפיינים של BST, אנו יודעים ש- X <Z <Y.

לאחר סיבוב ימני של Y, יש לנו עץ הנקרא T2 עם X כשורש ו- Y כילד הימני של X ו- Z כילד שמאל של Y. T2 הוא עדיין BST מכיוון שהוא שומר על הסדר X <Z <Y .

בואו נסתכל על פעולת הסיבוב הנכונה עבורנו AVLTree:

צומת rotateRight (צומת y) {צומת x = y. שמאל; צומת z = x.right; x.right = y; y. שמאל = z; updateHeight (y); updateHeight (x); החזר x; }

3.2. מבצע סיבוב שמאלי

יש לנו גם פעולת סיבוב שמאלי.

נניח ש- BST הנקרא T1, עם Y כצומת השורש, X כילדו הימני של Y ו- Z כילדו השמאלי של X. בהתחשב בכך אנו יודעים כי Y <Z <X.

לאחר סיבוב שמאלי של Y, יש לנו עץ שנקרא T2 עם X כשורש ו- Y כילד שמאל של X ו- Z כילד הימני של Y. T2 הוא עדיין BST מכיוון שהוא שומר על הסדר Y <Z <X .

בואו נסתכל על פעולת הסיבוב השמאלית עבור שלנו AVLTree:

צומת rotateLeft (צומת y) {צומת x = y.right; צומת z = x. שמאל; x. שמאל = y; y.right = z; updateHeight (y); updateHeight (x); החזר x; }

3.3. טכניקות איזון מחדש

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

כאשר גורם האיזון של צומת Z הוא 2, עץ המשנה עם Z כשורש נמצא באחד משני המצבים הללו, בהתחשב ב- Y כילדו הנכון של Z.

במקרה הראשון, הגובה בילד הימני של Y (X) גדול יותר מגובה הילד השמאלי (T2). אנו יכולים לאזן מחדש את העץ בקלות על ידי סיבוב שמאלי של Z.

במקרה השני, גובה הילד הימני של Y (T4) קטן מגובה הילד השמאלי (X). מצב זה זקוק לשילוב של פעולות סיבוב.

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

כמו כן, כאשר גורם האיזון של צומת Z הוא -2, עץ המשנה שלו נמצא באחד משני המצבים הללו, ולכן אנו רואים ב- Z את השורש ו- Y כילדו השמאלי.

הגובה בילד השמאלי של Y גדול מזה של הילד הימני שלו, לכן אנו מאזנים את העץ עם הסיבוב הימני של Z.

או במקרה השני, לילדו הימני של Y יש גובה גדול יותר מאשר לילדו השמאלי.

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

בואו נסתכל על פעולת האיזון מחדש עבורנו AVLTree:

איזון מחדש של הצומת (צומת z) {updateHeight (z); איזון int = getBalance (z); אם (איזון> 1) {אם (גובה (z.right.right)> גובה (z.right.left)) {z = rotateLeft (z); } אחר {z.right = rotateRight (z.right); z = rotateLeft (z); }} אחר אם (איזון גובה (z.left.right)) z = rotateRight (z); אחרת {z.left = rotateLeft (z.left); z = rotateRight (z); }} להחזיר z; }

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

4. הכנס צומת

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

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

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

בואו נסתכל על פעולת ההכנסה:

הוספת צומת (צומת צומת, מפתח int) {if (node ​​== null) {להחזיר צומת חדש (מפתח); } אחר אם (node.key> key) {node.left = insert (node.left, key); } אחר אם (node.key <key) {node.right = insert (node.right, key); } אחר {זרוק RuntimeException חדש ("מפתח כפול!"); } להחזיר איזון מחדש (צומת); }

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

מורכבות הזמן של אלגוריתם ההוספה היא פונקציה של הגובה. מכיוון שהעץ שלנו מאוזן, אנו יכולים להניח שמורכבות הזמן במקרה הגרוע ביותר היא O (log (N)).

5. מחק צומת

כדי למחוק מפתח מהעץ, ראשית עלינו למצוא אותו ב- BST.

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

נניח את הילד הימני של Z שנקרא Y. ראשית, אנו מוצאים את הצומת השמאלי ביותר של ה- Y וקוראים לו X. לאחר מכן, אנו מגדירים את הערך החדש של Z השווה לערך X 'ונמשיך למחוק את X מ- Y

לבסוף, אנו מכנים את שיטת האיזון מחדש כדי לשמור על ה- BST עץ AVL.

הנה שיטת המחיקה שלנו:

מחיקת צומת (צומת צומת, מפתח int) {if (node ​​== null) {node return; } אחר אם (node.key> key) {node.left = delete (node.left, key); } אחר אם (node.key <key) {node.right = delete (node.right, key); } אחר {if (node.left == null || node.right == null) {node = (node.left == null)? node.right: node.left; } אחר {Node mostLeftChild = mostLeftChild (node.right); node.key = mostLeftChild.key; node.right = מחק (node.right, node.key); }} אם (צומת! = null) {node = איזון מחדש (צומת); } הצומת החזרה; }

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

6. חפש צומת

חיפוש אחר צומת בעץ AVL הוא ה- אותו דבר כמו בכל BST.

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

מורכבות הזמן של החיפוש היא פונקציה של הגובה. אנו יכולים להניח שמורכבות הזמן במקרה הגרוע ביותר היא O (log (N)).

בואו נראה את קוד הדוגמה:

מציאת צומת (מפתח int) {Node current = root; בעוד (הנוכחי! = null) {אם (הנוכחי. מקש == מפתח) {הפסקה; } הנוכחי = הנוכחי. מקש <מקש? current.right: current.left; } להחזיר זרם; }

7. מסקנה

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

כמו תמיד, תוכל למצוא את הקוד ב- Github.