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

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

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

<gallery widths="100px" heights="100px">
קובץ:Tree234 node2.svg|איור 1 - צומת-2
קובץ:Tree234 node3.svg|איור 2 - צומת-3
קובץ:Tree234 node4.svg|איור 3 - צומת-4
</gallery>
[[קובץ:Tree234 example1.svg|שמאל|ממוזער|350px|איור 4 - דוגמה לעץ 2-3-4]]
בגרסה המתוארת כאן (ראו איור 4), גם הצמתים הפנימיים וגם העלים מכילים רשומות, כאשר כל רשומה מיוצגת על ידי מפתח, ואין חפיפה בין המפתחות שבעלים ובצמתים הפנימיים. 
המפתחות המאוכסנים בצומת פנימי מגדירים את תחום המפתחות המאוחסן בכל תת-עץ <math>c_i</math> המחובר לאותו צומת.

בצומת פנימי מסוג צומת-2,
*תת-העץ המחובר לבן <math>c_1</math> מכיל מפתחות הקטנים מ- <math>x</math>. 
*תת-העץ המחובר לבן <math>c_2</math> מכיל מפתחות הגדולים מ- <math>x</math>. 
בצומת פנימי מסוג צומת-3,
*תת-העץ המחובר לבן <math>c_1</math> מכיל מפתחות הקטנים מ- <math>x</math>. 
*תת-העץ המחובר לבן <math>c_2</math> מכיל מפתחות הגדולים מ- <math>x</math> וקטנים מ- <math>y</math>. 
*תת-העץ המחובר לבן <math>c_3</math> מכיל מפתחות הגדולים מ- <math>y</math>. 
בצומת פנימי מסוג צומת-4,
*תת-העץ המחובר לבן <math>c_1</math> מכיל מפתחות הקטנים מ- <math>x</math>. 
*תת-העץ המחובר לבן <math>c_2</math> מכיל מפתחות הגדולים מ- <math>x</math> וקטנים מ- <math>y</math>. 
*תת-העץ המחובר לבן <math>c_3</math> מכיל מפתחות הגדולים מ- <math>y</math> וקטנים מ- <math>z</math>. 
*תת-העץ המחובר לבן <math>c_4</math> מכיל מפתחות הגדולים מ- <math>z</math>.

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

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

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

== חיפוש ==
[[קובץ:Tree234 search1.svg|שמאל|ממוזער|300px|איור 5 - חיפוש מוצלח אחרי המפתח R (בירוק), חיפוש כושל אחרי המפתח G (באדום).]]
חיפוש רשומה שלה מפתח <math>k</math> מתחיל בשורש ומתקדם במורד העץ כאשר בכל צומת:
# אם <math>k</math> שווה לאחד המפתחות <math>x,y,z</math> אזי נמצאה הרשומה.
# אחרת, ממשיכים בתת-העץ אשר תחום המפתחות בו מכיל את מכיל את המפתח <math>k</math>.

לדוגמה, בצומת- 4 שבאיור 3:
* אם <math>k < x</math> ממשיכים לתת-העץ <math>c_1</math>.
* אם <math>x < k < y</math> ממשיכים לתת-העץ <math>c_2</math>.
* אם <math>y < k < z</math> ממשיכים לתת-העץ <math>c_3</math>.
* אם <math>z < k</math> ממשיכים לתת-העץ <math>c_4</math>.

בסופו של דבר, או שהמפתח נמצא בצומת פנימי, או שמגיעים לעלה. אם הרשומה נמצאת בעץ, אזי העלה יכיל את המפתח <math>k</math> ואת הרשומה השייכת לו (ראו איור 5).

== הכנסה ==
הכנסת מפתח לעץ ניתנת לביצוע באחת משתי שיטות עיקריות. 
בשתי השיטות, הכנסת מפתח חדש <math>k</math> לעץ 2-3-4 מתחילה כמו חיפוש, בו מתקדמים במורד העץ עד אשר מגיעים לעלה <math>a</math> בו מסתיים חיפוש כושל. 
אם העלה הוא צומת-2 או צומת-3, מוסיפים לו מפתח נוסף במקום המתאים והופכים אותו לצומת-3 או צומת-4, בהתאמה (ראו איור 6). 
השיטות נבדלות ביניהן בדרך שבה הן מתמודדות עם הוספת מפתח לצומת-4. 
בשני המקרים, הפעולה הבסיסית הנדרשת לפני ההוספה היא פיצול צומת-4 לשלושה צמתים מסוג צומת-2, כאשר (ראו איור 7):
* המפתח האמצעי <math>y</math> נמצא בצומת העליון
* הבן השמאלי מכיל את המפתח הקטן ואת שני תתי העץ המחוברים ל- <math>c_1,c_2</math>
* הבן הימני מכיל את המפתח הגדול ואת שני תתי העץ המחוברים ל- <math>c_3,c_4</math>

{|
| [[קובץ:Tree234 insert1.svg|שמאל|ממוזער|340px|איור 6 - הכנסת המפתח O לעץ מאיור 4, המסתיימת בהוספה לעלה מסוג צומת-3, בירוק.]] 
| [[קובץ:Tree234 split1.svg|שמאל|ממוזער|250px|איור 7 - פיצול צומת-4 לשלושה צמתים מסוג צומת-2.]] 
|}

=== שיטה 1 - פיצול מלמטה למעלה ===

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

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

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

{|
| [[קובץ:Tree234 insert2a.svg|שמאל|ממוזער|300px|איור 8 - הוספת המפתח V לעץ מאיור 6, פיצול מלמטה למעלה, צעד 1]]
| [[קובץ:Tree234 insert2b.svg|שמאל|ממוזער|300px|איור 9 - הוספת המפתח V לעץ מאיור 6, פיצול מלמטה למעלה, צעד 2]]
| [[קובץ:Tree234 insert2c.svg|שמאל|ממוזער|300px|איור 10 - הוספת המפתח V לעץ מאיור 6, פיצול מלמטה למעלה, צעד 3]]
|}

=== שיטה 2 - פיצול מלמעלה למטה ===

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

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

{| 
| [[קובץ:Tree234 insert3a.svg|ימין|ממוזער|300px|איור 11 - הוספת המפתח V לעץ מאיור 6, פיצול מלמעלה למטה, צעד 1]]
| [[קובץ:Tree234 insert3b.svg|ימין|ממוזער|300px|איור 12 - הוספת המפתח V לעץ מאיור 6, פיצול מלמעלה למטה, צעד 2]]
| [[קובץ:Tree234 insert3c.svg|ימין|ממוזער|300px|איור 13 - הוספת המפתח V לעץ מאיור 6, פיצול מלמעלה למטה, צעד 3]]
|}

== הוצאה ==

[[קובץ:Tree234 delete1.svg|שמאל|ממוזער|250px|איור 14 - הוצאת המפתח Z מהעץ באיור 4]]
[[קובץ:Tree234 delete2.svg|שמאל|ממוזער|250px|איור 15 - הוצאת המפתח F מהעץ באיור 14]]

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

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

=== הוצאת מפתח מצומת פנימי ===

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

הוצאת מפתח <math>k</math> מצומת פנימי מתבצעת באופן הבא (איור 15):
# מצא מחליף למפתח <math>k</math>, הצב אותו במקום <math>k</math>, והסר אותו מהעלה שבו היה מוצב.
# פעולה זו הסירה מפתח מעלה, ולכן שקולה למקרה הקודם.

=== שימור מבנה העץ לאחר הוצאה ===

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

# אם לצומת <math>a</math> יש מימין אח <math>b</math> מסוג צומת-3 או צומת-4 (איור 16)
## מוסיפים את המפתח <math>k'</math> המפריד בין <math>a</math> ל- <math>b</math> באב <math>p</math> אל הצומת <math>a</math>
## מסירים את <math>x</math>, המפתח הקטן ביותר של צומת <math>b</math> ומכניסים אותו במקום המפתח <math>k'</math> של האב <math>p</math>
## מעבירים את הבן הראשון <math>c_1</math> של צומת <math>b</math> להיות הבן האחרון של צומת <math>a</math>
# אחרת, אם לצומת <math>a</math> יש משמאל אח <math>b</math> מסוג צומת-3 או צומת-4 (איור 17)
## מוסיפים את המפתח <math>k'</math> המפריד בין <math>a</math> ל- <math>b</math> באב <math>p</math> אל הצומת <math>a</math>
## מסירים את <math>z</math>, המפתח הגדול ביותר של צומת <math>b</math> ומכניסים אותו במקום המפתח <math>k'</math> של האב <math>p</math>
## מעבירים את הבן האחרון (<math>c_3</math> או <math>c_4</math>) של צומת <math>b</math> להיות הבן הראשון <math>c_1</math> של צומת <math>a</math>
# אם לצומת <math>a</math> אין אחים, מימין או משמאל, מסוג צומת-3 או צומת-4 (איור 18)
## צור צומת חדש המכיל את המפתחות של צומת <math>a</math>, המפתחות של <math>b</math> אחד מאחיו מימין או משמאל, והמפתח <math>k'</math> המפריד בין <math>a</math> לבין האח <math>b</math> בצומת האב <math>p</math> 
## הסר את המפתח <math>k'</math> מן האב <math>p</math>, וחבר אל האב את הצומת החדש במקום שני <math>a,b</math> הצמתים שיצרו אותו
## אם הסרת המפתח <math>k'</math> מן האב גורמת לו להפוך לצומת ללא מפתחות, חזור על תהליך האיזון מחדש עם צומת זה. 

{|
||[[קובץ:Tree234 delete3b.svg|שמאל|ממוזער|280px|איור 16 - שימור מבנה העץ לאחר הוצאה, מקרה 1]] 
||[[קובץ:Tree234 delete3a.svg|שמאל|ממוזער|280px|איור 17 - שימור מבנה העץ לאחר הוצאה, מקרה 2]] 
|[[קובץ:Tree234 delete4.svg|שמאל|ממוזער|250px|איור 18 - שימור מבנה העץ לאחר הוצאה, מקרה 3]]
|}

מקרה מיוחד הוא כאשר השורש נותר צומת ריק עם בן אחד. במקרה זה מסירים את השורש והופכים את בנו לשורש החדש (איור 19). באופן זה קטן עומקו של עץ 2-3-4.
{|
|[[קובץ:Tree234 delete5.svg|שמאל|ממוזער|250px|איור 19 - שימור מבנה העץ לאחר הוצאה, הסרת השורש]]
|}

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

[[קובץ:Tree234 binary1.svg|שמאל|ממוזער|350px| איור 20 - יצוג בינארי של צומת-3 וצומת-4, באמצעות צמתים מסוג צומת-2]]
[[קובץ:Tree234 binary2.svg|שמאל|ממוזער|450px| איור 21 - יצוג בינארי של העץ המופיע באיור 4]]

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

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

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

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

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

[[עץ B|עץ-B]] הוא הרחבה של עץ 2-3-4{{הערה|Douglas Comer, ''[http://people.cs.aau.dk/~simas/aalg06/UbiquitBtree.pdf The Ubiquitous B-Tree]'', Computing Surveys, Vol ll, No 2, June 1979}}{{הערה|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). Section 11.4.}}{{הערה|Knuth, Donald. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1998. {{ISBN|0-201-89685-0}}. Page 482 of section 6.2.4.}} - עץ 2-3-4 ידוע גם בשם "עץ-B מדרגה 4".

==ראו גם==
* [[עץ 2-3]]

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

<div style="direction: ltr;">
* Robert Sedgewick, ''Algorithms in Java: Parts 1-4'', 3rd Edition, Addison-Wesley (2002). Chapter 13.3.
* Robert Sedgewick, Kevin Wayne, ''Algorithms'', 4th Edition., Addison-Wesley (2011). Chapter 6, pp. 866.
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, ''Introduction to Algorithms'', 3rd Edition., The MIT Press (2009). Chapter 18: B-Trees.
</div>

==קישורים חיצוניים==
{{ויקישיתוף בשורה|Category:2-3-4-Trees}}

==הערות שוליים==
{{הערות שוליים}}

{{מבני נתונים}}
[[קטגוריה:עצי חיפוש|2-3-4]]