עץ 2-3

במדעי המחשב, עץ 2-3 (באנגלית: 2-3 tree) הוא מבנה נתונים מסוג עץ חיפוש מאוזן. בעץ זה:

1. כל צומת אב (צומת פנימי) מכיל מפתח אחד ושני בנים (צומת-2, איור 1), או שני מפתחות ושלושה בנים (צומת-3, איור 2).
2. כל הצמתים ללא בנים (צמתים חיצוניים או עלים), נמצאים באותו העומק (ראה איור 3).

כמו כן, עץ ריק ועץ עם עלה אחד הם עצי 2-3.

• 
  איור 1 - צומת-2
• 
  איור 2 - צומת-3

איור 3 - דוגמה לעץ 2-3

לעץ 2-3 מספר גרסאות בעלות תכונות שונות מעט, אשר נבחרות על פי התאמתן לשימוש מסוים^[1]. בגרסה המתוארת כאן, הרשומות (המכילות מפתח וערך הקשור אליו) נמצאות רק בעלים, בעוד הצמתים הפנימיים מכילים מידע לארגון בלבד. בכל צומת פנימי,

• הערך-${\displaystyle x}$ מכיל תמיד את המפתח המקסימלי המצוי בתת-העץ השמאלי המחובר ל-${\displaystyle l}$.
• תת-העץ המרכזי המחובר ל-${\displaystyle m}$ מכיל מפתחות הגדולים מ-${\displaystyle x}$.
• בצומת-3, הערך ${\displaystyle y}$ מכיל את המפתח המקסימלי המצוי בתת-העץ המרכזי המחובר ל-${\displaystyle m}$.
• בצומת-3, תת-העץ הימני המחובר ל-${\displaystyle r}$ מכיל מפתחות הגדולים מ-${\displaystyle y}$.

בעץ 2-3 עם ${\displaystyle h}$ רמות, יש בין ${\displaystyle 2^{h-1}}$ ל- ${\displaystyle 3^{h-1}}$ עלים (כאשר העץ מורכב מצמתים מסוג צומת-2 בלבד, או צומת-3 בלבד, בהתאמה). במילים אחרות, על מנת ליצג ${\displaystyle n}$ רשומות, יש צורך בעץ עם לפחות ${\displaystyle 1+\log _{3}n}$ רמות, אך לא יותר מ- ${\displaystyle 1+\log _{2}n}$ רמות. משמע, כל המסלולים בעץ הם באורך ${\displaystyle O(\log n)}$.

מבנהו של עץ 2-3 מבטיח חיפוש, הכנסה, והוצאת מפתח (המיצג רשומה) בסיבוכיות ${\displaystyle O(\log n)}$ במקרה הגרוע ביותר, כאשר ${\displaystyle n}$ הוא מספר המפתחות (רשומות) בעץ.

עץ 2-3 פותח על ידי ג'ון הופקרופט בשנת 1970^[2][3], ושייך למשפחה של עצי חיפוש המאזנים את עצמם (Self-balancing search tree). בעצים מסוג זה פעולות הכנסת מפתח והוצאת מפתח עשויות לגרום שינויים במבנה העץ, לשם שימור איזונו. דוגמאות נוספות לעצי חיפוש המאזנים את עצמם הן: עץ AVL, עץ אדום שחור, עץ 2-3-4, ועץ B.

חיפוש

איור 4 - חיפוש מוצלח אחר המפתח 5 (בירוק), חיפוש כושל אחר המפתח 12 (באדום).

חיפוש רשומה שלה מפתח ${\displaystyle k}$ מתקדם במורד העץ כאשר בכל צומת:

1. אם ${\displaystyle k\leq x}$ ממשיכים לתת-העץ השמאלי.
2. אם ${\displaystyle k>x}$ והצומת הוא צומת-2, ממשיכים בתת-העץ הימני.
3. אם ${\displaystyle k>x}$ והצומת הוא צומת-3, אזי אם ${\displaystyle k\leq y}$ ממשיכים בתת-העץ האמצעי, אחרת ממשיכים בתת-העץ הימני.

בסופו של דבר מגיעים לעלה. אם הרשומה נמצאת בעץ, אזי העלה יכיל את המפתח ${\displaystyle k}$ ואת הרשומה השייכת לו (ראה איור 4). אם רוצים רק לוודא את הימצאות הרשומה, ולא לגשת אליה, אפשר לעצור בכל שלב בו ${\displaystyle k=x}$ או ${\displaystyle k=y}$.

הכנסה

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

בעץ עם צמתים פנימיים, הכנסת רשומה חדשה עם מפתח ${\displaystyle k}$ מתקדמת כמו חיפוש, עד אשר מגיעים ל-${\displaystyle a}$, הצומת הפנימי האחרון לפני העלים.

אם צומת ${\displaystyle a}$ הוא צומת-2, מוסיפים לו עוד בן (עלה) והופכים אותו לצומת-3, כאשר העלים ממוינים והערכים ${\displaystyle x,y}$ מעודכנים כנדרש. אם ${\displaystyle k}$ הוא הערך הגדול מבין שלושת הבנים, יש לעדכן גם את הערכים ${\displaystyle x}$ או ${\displaystyle y}$ של האבות של הצומת ${\displaystyle a}$ (ראה איור 6).

אם צומת ${\displaystyle a}$ הוא צומת-3, מרחיבים אותו זמנית לצומת-4 (האסור בעץ 2-3), ומוסיפים לו עלה במקום המתאים. על מנת לשמור על מבנה העץ, מפצלים את צומת-4 שנוצר לשני צמתים-2, ${\displaystyle a}$ ו-${\displaystyle b}$. את זוג המפתחות הנמוכים מציבים בצומת השמאלי ${\displaystyle a}$, ואת זוג המפתחות הגבוהים מציבים בצומת הימני ${\displaystyle b}$. כעת מוסיפים את הצומת החדש שנוסף (${\displaystyle b}$) לאב ${\displaystyle p}$ של צומת ${\displaystyle a}$ המקורי. תהליך זה זהה להוספת עלה לצומת פנימי - אם צומת ${\displaystyle p}$ הוא צומת-2 הוא יהפוך לצומת-3, ואם הוא צומת-3 הוא יעבור הרחבה לצומת-4 ופיצול. כך ממשיכים בסדרה של הרחבות ופיצולים עד אשר מגיעים לצומת-2 או מפצלים את השורש (ראה איור 7).

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

• 
  איור 5 - הכנסת המפתחות 1 עד 5, החל מעץ ריק.
• 
  איור 6 - הכנסת המפתחות 6 עד 7.
• 
  איור 7 - הכנסת המפתח 8.

הוצאה

הוצאת רשומה עם מפתח ${\displaystyle k}$ מתקדמת כמו חיפוש, עד אשר מגיעים ל-${\displaystyle a}$, הצומת הפנימי האחרון לפני העלים.

אם צומת ${\displaystyle a}$ הוא צומת-3, מסירים את הבן עם מפתח ${\displaystyle k}$, והופכים אותו לצומת-2. אם הבן שהוסר היה הגדול משלושת הבנים, יש לעדכן גם את הערכים ${\displaystyle x}$ או ${\displaystyle y}$ של האבות של הצומת ${\displaystyle a}$ (ראה איור 8).

אם צומת ${\displaystyle a}$ הוא צומת-2, מסירים את הבן עם מפתח ${\displaystyle k}$, והופכים אותו זמנית לצומת-1, האסור בעץ 2-3. על מנת לשמר את מבנה העץ מבצעים את אחת מפעולות המיזוג הבאות:

1. אם לצומת ${\displaystyle a}$ יש אח ${\displaystyle b}$ מימין או משמאל שלו 3 בנים, מעבירים את אחד הבנים של ${\displaystyle b}$ לצומת ${\displaystyle a}$, ומעדכנים את הערכים ${\displaystyle x}$ או ${\displaystyle y}$ של האבות של הצומת ${\displaystyle a}$ במידת הצורך.
2. אם לצומת ${\displaystyle a}$ יש רק אחים מסוג צומת-2, אזי מסירים את הבן היחיד של ${\displaystyle a}$, מעבירים אותו לאחד מהאחים של ${\displaystyle a}$, ומוחקים את צומת ${\displaystyle a}$ מהאב שלו ${\displaystyle p}$.
3. אם האב ${\displaystyle p}$ נותר צומת-2, התהליך הסתיים. אם האב ${\displaystyle p}$ נותר צומת-1 (האסור בעץ 2-3), חוזרים על תהליך המיזוג כפי שתואר לעיל (ראה איור 9).

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

• 
  איור 8 - הסרת המפתחות 6 ו-5.
• 
  איור 9 - הסרת המפתחות 4, 3, 2, ו-1.

יצוג כעץ בינארי

איור 10 - המרת צומת-3 בזוג צמתים בינאריים כאשר הקשת האופקית מסומנת באדום

איור 11 - יצוג בינארי של העץ באיור 3

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

העץ הבינארי המתקבל מהמרת עץ 2-3 באופן זה (ראה איור 11), הוא עץ מאוזן, במובן הבא:

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

מתברר^[2] שפעולות האיזון המתבצעות בעץ 2-3 בעת הכנסה והוצאה של מפתח (הרחבה ופיצול, מחיקה ומיזוג), מתבטאות ביצוג כעץ בינארי המתקבל לאחר המרה, כפעולות דומות לפעולות האיזון בעץ AVL (סיבוב העץ).

מכיוון שכך, גם ביצוג כעץ בינארי של עץ 2-3 פעולות החיפוש, ההכנסה, וההוצאה של מפתח מתבצעות בסיבוכיות ${\displaystyle O(\log n)}$ במקרה הגרוע ביותר.

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

הרחבות וגרסאות נוספות

כאמור לעץ 2-3 מספר אפשרויות ליחוס הרשומות לצמתים, הנבחרות לפי התאמתן לשימוש מסוים^[1]. לדוגמה, בגרסה אחת של עץ 2-3 הרשומות נשמרות גם בצמתים פנימיים וגם בעלים^[4], ללא שכפול. באופן זה מספר הצמתים בעץ זהה למספר הרשומות, בניגוד לגרסה המתוארת לעיל, בה נשמרות הרשומות רק בעלים. למרות הבדלים אלה, פעולות האיזון בהכנסת מפתח (הרחבה ופיצול) והוצאת מפתח (מחיקה ומיזוג) זהות למעשה בכל הגרסאות.

עץ-B הוא הרחבה של עץ 2-3^[5] - עץ 2-3 ידוע גם בשם "עץ-B מדרגה 3".

לקריאה נוספת

• Robert Sedgewick, Kevin Wayne, Algorithms, 4th ed., Addison-Wesley (2011). Chapter 3.3 (book-site: http://algs4.cs.princeton.edu).

קישורים חיצוניים

מדיה וקבצים בנושא עץ 2-3 בוויקישיתוף

• עץ 2-3, מצגת מקורס מבנה נתונים, מדעי המחשב, הטכניון.
• עץ 2-3 , באתר הקורס CS367 באוניברסיטת ויסקונסין. 2005.

הערות שוליים

1. Mark R. Brown and Robert E. Tarjan, Design and Analysis of a Data Structure for Representing Sorted Lists, SIAM J. Comput., 9(3), pp. 594–614, 1979.
2. Knuth, Donald. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Page 476 of section 6.2.3.
3. Alfred V. Aho, J.E. Hopcroft, Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley Series in Computer Science and Information Processing (1974).
4. Robert Sedgewick, Kevin Wayne, Algorithms, 4th ed., Addison-Wesley (2011). Chapter 3.3.
5. Douglas Comer, The Ubiquitous B-Tree, Computing Surveys, Vol ll, No 2, June 1979. pdf