עץ 2-3-4

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

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

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

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

בגרסה המתוארת כאן (ראו איור 4), גם הצמתים הפנימיים וגם העלים מכילים רשומות, כאשר כל רשומה מיוצגת על ידי מפתח, ואין חפיפה בין המפתחות שבעלים ובצמתים הפנימיים. המפתחות המאוכסנים בצומת פנימי מגדירים את תחום המפתחות המאוחסן בכל תת-עץ $c_{i}$ המחובר לאותו צומת.

בצומת פנימי מסוג צומת-2,

תת-העץ המחובר לבן $c_{1}$ מכיל מפתחות הקטנים מ- $x$ .
תת-העץ המחובר לבן $c_{2}$ מכיל מפתחות הגדולים מ- $x$ .

בצומת פנימי מסוג צומת-3,

תת-העץ המחובר לבן $c_{1}$ מכיל מפתחות הקטנים מ- $x$ .
תת-העץ המחובר לבן $c_{2}$ מכיל מפתחות הגדולים מ- $x$ וקטנים מ- $y$ .
תת-העץ המחובר לבן $c_{3}$ מכיל מפתחות הגדולים מ- $y$ .

בצומת פנימי מסוג צומת-4,

תת-העץ המחובר לבן $c_{1}$ מכיל מפתחות הקטנים מ- $x$ .
תת-העץ המחובר לבן $c_{2}$ מכיל מפתחות הגדולים מ- $x$ וקטנים מ- $y$ .
תת-העץ המחובר לבן $c_{3}$ מכיל מפתחות הגדולים מ- $y$ וקטנים מ- $z$ .
תת-העץ המחובר לבן $c_{4}$ מכיל מפתחות הגדולים מ- $z$ .

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

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

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

חיפוש

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

אם $k$ שווה לאחד המפתחות $x,y,z$ אזי נמצאה הרשומה.
אחרת, ממשיכים בתת-העץ אשר תחום המפתחות בו מכיל את מכיל את המפתח $k$ .

לדוגמה, בצומת- 4 שבאיור 3:

אם $k<x$ ממשיכים לתת-העץ $c_{1}$ .
אם $x<k<y$ ממשיכים לתת-העץ $c_{2}$ .
אם $y<k<z$ ממשיכים לתת-העץ $c_{3}$ .
אם $z<k$ ממשיכים לתת-העץ $c_{4}$ .

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

הכנסה

הכנסת מפתח לעץ ניתנת לביצוע באחת משתי שיטות עיקריות. בשתי השיטות, הכנסת מפתח חדש $k$ לעץ 2-3-4 מתחילה כמו חיפוש, בו מתקדמים במורד העץ עד אשר מגיעים לעלה $a$ בו מסתיים חיפוש כושל. אם העלה הוא צומת-2 או צומת-3, מוסיפים לו מפתח נוסף במקום המתאים והופכים אותו לצומת-3 או צומת-4, בהתאמה (ראו איור 6). השיטות נבדלות ביניהן בדרך שבה הן מתמודדות עם הוספת מפתח לצומת-4. בשני המקרים, הפעולה הבסיסית הנדרשת לפני ההוספה היא פיצול צומת-4 לשלושה צמתים מסוג צומת-2, כאשר (ראו איור 7):

המפתח האמצעי $y$ נמצא בצומת העליון
הבן השמאלי מכיל את המפתח הקטן ואת שני תתי העץ המחוברים ל- $c_{1},c_{2}$
הבן הימני מכיל את המפתח הגדול ואת שני תתי העץ המחוברים ל- $c_{3},c_{4}$

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

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

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

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

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

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

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

הוצאה

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

הוצאת מפתח מעלה

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

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

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

הערך הגדול ביותר בתת-העץ השמאלי, אותו אפשר למצוא על ידי ירידה בבן הימני ביותר של כל צומת עד הגעה לעלה הימני ביותר בתת-העץ, או
הערך הקטן ביותר בתת-העץ הימני, אותו אפשר למצוא על ידי ירידה בבן השמאלי ביותר של כל צומת עד הגעה לעלה השמאלי ביותר בתת-העץ.

הוצאת מפתח $k$ מצומת פנימי מתבצעת באופן הבא (איור 15):

מצא מחליף למפתח $k$ , הצב אותו במקום $k$ , והסר אותו מהעלה שבו היה מוצב.
פעולה זו הסירה מפתח מעלה, ולכן שקולה למקרה הקודם.

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

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

אם לצומת $a$ $a$ יש מימין אח $b$ $b$ מסוג צומת-3 או צומת-4 (איור 16)
1. מוסיפים את המפתח $k'$ המפריד בין $a$ ל- $b$ באב $p$ אל הצומת $a$
2. מסירים את $x$ , המפתח הקטן ביותר של צומת $b$ ומכניסים אותו במקום המפתח $k'$ של האב $p$
3. מעבירים את הבן הראשון $c_{1}$ של צומת $b$ להיות הבן האחרון של צומת $a$
אחרת, אם לצומת $a$ $a$ יש משמאל אח $b$ $b$ מסוג צומת-3 או צומת-4 (איור 17)
1. מוסיפים את המפתח $k'$ המפריד בין $a$ ל- $b$ באב $p$ אל הצומת $a$
2. מסירים את $z$ , המפתח הגדול ביותר של צומת $b$ ומכניסים אותו במקום המפתח $k'$ של האב $p$
3. מעבירים את הבן האחרון ( $c_{3}$ או $c_{4}$ ) של צומת $b$ להיות הבן הראשון $c_{1}$ של צומת $a$
אם לצומת $a$ $a$ אין אחים, מימין או משמאל, מסוג צומת-3 או צומת-4 (איור 18)
1. צור צומת חדש המכיל את המפתחות של צומת $a$ , המפתחות של $b$ אחד מאחיו מימין או משמאל, והמפתח $k'$ המפריד בין $a$ לבין האח $b$ בצומת האב $p$
2. הסר את המפתח $k'$ מן האב $p$ , וחבר אל האב את הצומת החדש במקום שני $a,b$ הצמתים שיצרו אותו
3. אם הסרת המפתח $k'$ מן האב גורמת לו להפוך לצומת ללא מפתחות, חזור על תהליך האיזון מחדש עם צומת זה.

מקרה מיוחד הוא כאשר השורש נותר צומת ריק עם בן אחד. במקרה זה מסירים את השורש והופכים את בנו לשורש החדש (איור 19). באופן זה קטן עומקו של עץ 2-3-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 פעולות החיפוש, ההכנסה, וההוצאה של מפתח מתבצעות בסיבוכיות $O(\log n)$ במקרה הגרוע ביותר.

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

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

ראו גם

עץ 2-3

לקריאה נוספת

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.

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

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

הערות שוליים

^ Douglas Comer, 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.

[1] Douglas Comer, The Ubiquitous B-Tree, Computing Surveys, Vol ll, No 2, June 1979

[2] 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.

[3] 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.

[1]

[2]

[3]

מבני נתונים
מבנים מופשטים	רשימה • מחסנית • קבוצה • מולטי קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות
מימושים ליניאריים	מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ
גרפים ועצים	ערימה (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R‏ • Trie • X-fast trie • טריי y מהיר• עץ WAVL
הסתברותיים	מסנן בלום