הצגת המקור של הדף "עץ 2-3"

ב[[מדעי המחשב]], '''עץ 2-3''' (ב[[אנגלית]]: {{משמאל לימין|'''2-3 tree'''}}) הוא [[מבנה נתונים]] מסוג [[עץ (תורת הגרפים)|עץ]] [[עץ חיפוש|חיפוש]] מאוזן. בעץ זה:
# כל [[צומת (תורת הגרפים)|צומת]] אב (צומת פנימי) מכיל מפתח אחד ושני בנים (צומת-2, איור 1), או שני מפתחות ושלושה בנים (צומת-3, איור 2).
# כל הצמתים ללא בנים (צמתים חיצוניים או עלים), נמצאים באותו העומק (ראה איור 3).
כמו כן, עץ ריק ועץ עם עלה אחד הם עצי 2-3.

<gallery widths="100px" heights="100px">
Tree23 node2.svg|איור 1 - צומת-2
Tree23 node3.svg|איור 2 - צומת-3
</gallery>

[[קובץ:Tree23 example2.svg|שמאל|ממוזער|400px|איור 3 - דוגמה לעץ 2-3]]
לעץ 2-3 מספר גרסאות בעלות תכונות שונות מעט, אשר נבחרות על פי התאמתן לשימוש מסוים{{הערה|שם=Brown79 }}. בגרסה המתוארת כאן, הרשומות (המכילות מפתח וערך הקשור אליו) נמצאות רק בעלים, בעוד הצמתים הפנימיים מכילים מידע לארגון בלבד. בכל צומת פנימי, 
* הערך-<math>x</math> מכיל תמיד את המפתח המקסימלי המצוי בתת-העץ השמאלי המחובר ל-<math>l</math>. 
* תת-העץ המרכזי המחובר ל-<math>m</math> מכיל מפתחות הגדולים מ-<math>x</math>.
* בצומת-3, הערך <math>y</math> מכיל את המפתח המקסימלי המצוי בתת-העץ המרכזי המחובר ל-<math>m</math>. 
* בצומת-3, תת-העץ הימני המחובר ל-<math>r</math> מכיל מפתחות הגדולים מ-<math>y</math>. 

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

מבנהו של עץ 2-3 מבטיח חיפוש, הכנסה, והוצאת מפתח (המיצג רשומה) ב[[סיבוכיות]] <math>O(\log n)</math> במקרה הגרוע ביותר, כאשר <math>n</math> הוא מספר המפתחות (רשומות) בעץ.

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

== חיפוש ==
[[קובץ:Tree23 search.svg|שמאל|ממוזער|350px|איור 4 - חיפוש מוצלח אחר המפתח 5 (בירוק), חיפוש כושל אחר המפתח 12 (באדום).]]

חיפוש רשומה שלה מפתח <math>k</math> מתקדם במורד העץ כאשר בכל צומת:
# אם <math>k \leq x</math> ממשיכים לתת-העץ השמאלי.
# אם <math>k > x</math> והצומת הוא צומת-2, ממשיכים בתת-העץ הימני.
# אם <math>k > x</math> והצומת הוא צומת-3, אזי אם <math>k \leq y</math> ממשיכים בתת-העץ האמצעי, אחרת ממשיכים בתת-העץ הימני.
בסופו של דבר מגיעים לעלה. אם הרשומה נמצאת בעץ, אזי העלה יכיל את המפתח <math>k</math> ואת הרשומה השייכת לו (ראה איור 4). אם רוצים רק לוודא את הימצאות הרשומה, ולא לגשת אליה, אפשר לעצור בכל שלב בו <math>k=x</math> או <math>k=y</math>.

== הכנסה ==

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

בעץ עם צמתים פנימיים, הכנסת רשומה חדשה עם מפתח <math>k</math> מתקדמת כמו חיפוש, עד אשר מגיעים ל-<math>a</math>, הצומת הפנימי האחרון לפני העלים. 

אם צומת <math>a</math> הוא צומת-2, מוסיפים לו עוד בן (עלה) והופכים אותו לצומת-3, כאשר העלים ממוינים והערכים <math>x,y</math> מעודכנים כנדרש. אם <math>k</math> הוא הערך הגדול מבין שלושת הבנים, יש לעדכן גם את הערכים <math>x</math> או <math>y</math> של האבות של הצומת <math>a</math> (ראה איור 6).

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

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

<gallery widths="300px" heights="300px">
קובץ:Tree23 insert1.svg|איור 5 - הכנסת המפתחות 1 עד 5, החל מעץ ריק.
קובץ:Tree23 insert2.svg|איור 6 - הכנסת המפתחות 6 עד 7.
קובץ:Tree23 insert3.svg|איור 7 - הכנסת המפתח 8.
</gallery>

== הוצאה ==

הוצאת רשומה עם מפתח <math>k</math> מתקדמת כמו חיפוש, עד אשר מגיעים ל-<math>a</math>, הצומת הפנימי האחרון לפני העלים.

אם צומת <math>a</math> הוא צומת-3, מסירים את הבן עם מפתח <math>k</math>, והופכים אותו לצומת-2. אם הבן שהוסר היה הגדול משלושת הבנים, יש לעדכן גם את הערכים <math>x</math> או <math>y</math> של האבות של הצומת <math>a</math> (ראה איור 8).

אם צומת <math>a</math> הוא צומת-2, מסירים את הבן עם מפתח <math>k</math>, והופכים אותו זמנית לצומת-1, האסור בעץ 2-3. על מנת לשמר את מבנה העץ מבצעים את אחת מפעולות המיזוג הבאות:

# אם לצומת <math>a</math> יש אח <math>b</math> מימין או משמאל שלו 3 בנים, מעבירים את אחד הבנים של <math>b</math> לצומת <math>a</math>, ומעדכנים את הערכים <math>x</math> או <math>y</math> של האבות של הצומת <math>a</math> במידת הצורך.
# אם לצומת <math>a</math> יש רק אחים מסוג צומת-2, אזי מסירים את הבן היחיד של <math>a</math>, מעבירים אותו לאחד מהאחים של <math>a</math>, ומוחקים את צומת <math>a</math> מהאב שלו <math>p</math>. 
# אם האב <math>p</math> נותר צומת-2, התהליך הסתיים. אם האב <math>p</math> נותר צומת-1 (האסור בעץ 2-3), חוזרים על תהליך המיזוג כפי שתואר לעיל (ראה איור 9). 

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

<gallery widths="300px" heights="200px">
קובץ:Tree23 delete1.svg|איור 8 - הסרת המפתחות 6 ו-5. 
קובץ:Tree23 delete2.svg|איור 9 - הסרת המפתחות 4, 3, 2, ו-1.
</gallery>

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

[[קובץ:Tree23 binary1.svg|שמאל|ממוזער|250px|איור 10 - המרת צומת-3 בזוג צמתים בינאריים כאשר הקשת האופקית מסומנת באדום]] 
[[קובץ:Tree23 example2binary.svg|שמאל|ממוזער|400px|איור 11 - יצוג בינארי של העץ באיור 3]]

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

ה[[עץ בינארי|עץ הבינארי]] המתקבל מהמרת עץ 2-3 באופן זה (ראה איור 11), הוא [[עץ מאוזן]], במובן הבא: 
* העץ הוא "מאוזן שחור", כלומר כל המסלולים בין השורש לעלים עוברים דרך אותו מספר קשתות שחורות. תכונה זו מתקיימת מכיוון שהקשתות השחורות הן הקשתות המקוריות של עץ 2-3, שהוא מאוזן באופן מושלם.
* המסלול הארוך ביותר מהשורש לעלה כלשהו, ארוך לכל היותר פי שניים מהמסלול הקצר ביותר מהשורש לעלה כלשהו. מצב זה עשוי להתקבל כאשר בעץ 2-3 עם שורש מסוג צומת-3, תת-העץ הימני מורכב רק מצמתים מסוג צומת-3, בעוד תת-העץ השמאלי מורכב מצמתים מסוג צומת-2. מסלול אחד לפחות בתת-העץ הימני יהיה מורכב מקשת אדומה ושחורה לסירוגין, בעוד בתת-העץ השמאלי כל המסלולים שחורים.

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

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

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

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

כאמור לעץ 2-3 מספר אפשרויות ליחוס הרשומות לצמתים, הנבחרות לפי התאמתן לשימוש מסוים{{הערה|שם=Brown79 }}. לדוגמה, בגרסה אחת של עץ 2-3 הרשומות נשמרות גם בצמתים פנימיים וגם בעלים{{הערה|שם=Sedgewick11 }}, ללא שכפול. באופן זה מספר הצמתים בעץ זהה למספר הרשומות, בניגוד לגרסה המתוארת לעיל, בה נשמרות הרשומות רק בעלים. למרות הבדלים אלה, פעולות האיזון בהכנסת מפתח (הרחבה ופיצול) והוצאת מפתח (מחיקה ומיזוג) זהות למעשה בכל הגרסאות.

[[עץ B|עץ-B]] הוא הרחבה של עץ 2-3{{הערה|שם=Comer }} - עץ 2-3 ידוע גם בשם "עץ-B מדרגה 3".

== לקריאה נוספת ==

<div style="direction: ltr;">
* Robert Sedgewick, Kevin Wayne, ''Algorithms'', 4th ed., Addison-Wesley (2011). Chapter 3.3 ([http://algs4.cs.princeton.edu book-site: http://algs4.cs.princeton.edu]).
</div>

== קישורים חיצוניים ==
{{ויקישיתוף בשורה}}
* [http://www.cs.technion.ac.il/~dang/courseDS/L05-B-Trees+Rank-Trees/L05-B-Trees+Rank-Trees.pdf עץ 2-3, מצגת מקורס מבנה נתונים, מדעי המחשב, הטכניון. ]
* [http://pages.cs.wisc.edu/~vernon/cs367/notes/10.23TREE.html עץ 2-3 ], באתר הקורס [http://pages.cs.wisc.edu/~vernon/cs367/cs367.html CS367 ] באוניברסיטת ויסקונסין. 2005.

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל|הערות=

{{הערה|שם=Aho74|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).}}

{{הערה|שם=Knuth97v3|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.}}

{{הערה|שם=Sedgewick11|Robert Sedgewick, Kevin Wayne, ''Algorithms'', 4th ed., Addison-Wesley (2011). Chapter 3.3.}}

{{הערה|שם=Comer|Douglas Comer, ''The Ubiquitous B-Tree'', Computing Surveys, Vol ll, No 2, June 1979. [http://people.cs.aau.dk/~simas/aalg06/UbiquitBtree.pdf pdf]}}

{{הערה|שם=Brown79|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-3]]