עץ 2-3-4

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

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

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

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

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

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

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

  • תת-העץ המחובר לבן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1} מכיל מפתחות הקטנים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} .
  • תת-העץ המחובר לבן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_2} מכיל מפתחות הגדולים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} .

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

  • תת-העץ המחובר לבן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1} מכיל מפתחות הקטנים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} .
  • תת-העץ המחובר לבן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_2} מכיל מפתחות הגדולים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} וקטנים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y} .
  • תת-העץ המחובר לבן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_3} מכיל מפתחות הגדולים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y} .

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

  • תת-העץ המחובר לבן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1} מכיל מפתחות הקטנים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} .
  • תת-העץ המחובר לבן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_2} מכיל מפתחות הגדולים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} וקטנים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y} .
  • תת-העץ המחובר לבן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_3} מכיל מפתחות הגדולים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y} וקטנים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle z} .
  • תת-העץ המחובר לבן הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_4} מכיל מפתחות הגדולים מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle z} .

בעץ 2-3-4 עם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle h} רמות, יש בין הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^{h}-1 } ל- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4^{h}-1 } מפתחות (כאשר העץ מורכב מצמתים מסוג צומת-2 בלבד, או צומת-4 בלבד, בהתאמה). במילים אחרות, על מנת ליצג הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} רשומות, יש צורך בעץ עם לפחות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \log_{4} (n + 1)} רמות, אך לא יותר מ- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \log_{2} (n + 1)} רמות. משמע, כל המסלולים בעץ הם באורך הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(\log n)} .

מבנהו של עץ 2-3-4 מבטיח חיפוש, הכנסה, והוצאת מפתח (המיצג רשומה) בסיבוכיות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(\log n)} במקרה הגרוע ביותר, כאשר הוא מספר המפתחות (רשומות) בעץ.

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

חיפוש

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

חיפוש רשומה שלה מפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} מתחיל בשורש ומתקדם במורד העץ כאשר בכל צומת:

  1. אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} שווה לאחד המפתחות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x,y,z} אזי נמצאה הרשומה.
  2. אחרת, ממשיכים בתת-העץ אשר תחום המפתחות בו מכיל את מכיל את המפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} .

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

  • אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k < x} ממשיכים לתת-העץ הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1} .
  • אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x < k < y} ממשיכים לתת-העץ הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_2} .
  • אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y < k < z} ממשיכים לתת-העץ הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_3} .
  • אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle z < k} ממשיכים לתת-העץ הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_4} .

בסופו של דבר, או שהמפתח נמצא בצומת פנימי, או שמגיעים לעלה. אם הרשומה נמצאת בעץ, אזי העלה יכיל את המפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} ואת הרשומה השייכת לו (ראו איור 5).

הכנסה

הכנסת מפתח לעץ ניתנת לביצוע באחת משתי שיטות עיקריות. בשתי השיטות, הכנסת מפתח חדש הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} לעץ 2-3-4 מתחילה כמו חיפוש, בו מתקדמים במורד העץ עד אשר מגיעים לעלה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} בו מסתיים חיפוש כושל. אם העלה הוא צומת-2 או צומת-3, מוסיפים לו מפתח נוסף במקום המתאים והופכים אותו לצומת-3 או צומת-4, בהתאמה (ראו איור 6). השיטות נבדלות ביניהן בדרך שבה הן מתמודדות עם הוספת מפתח לצומת-4. בשני המקרים, הפעולה הבסיסית הנדרשת לפני ההוספה היא פיצול צומת-4 לשלושה צמתים מסוג צומת-2, כאשר (ראו איור 7):

  • המפתח האמצעי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y} נמצא בצומת העליון
  • הבן השמאלי מכיל את המפתח הקטן ואת שני תתי העץ המחוברים ל- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1,c_2}
  • הבן הימני מכיל את המפתח הגדול ואת שני תתי העץ המחוברים ל- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_3,c_4}
איור 6 - הכנסת המפתח O לעץ מאיור 4, המסתיימת בהוספה לעלה מסוג צומת-3, בירוק.
איור 7 - פיצול צומת-4 לשלושה צמתים מסוג צומת-2.

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

כאשר העלה שנמצא הוא צומת-4, מפצלים אותו לפני הוספה לשלושה צמתים מסוג צומת-2, על ידי העלאת המפתח המרכזי (הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y} ) לצומת העליון הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} (איור 7). לאחר מכן מוסיפים את המפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} לאחד מבניו של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} , העלים החדשים אשר מכילים את המפתחות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x,z} בהתאמה (איור 8).

על מנת לשמור על מבנה העץ אשר דורש עומק זהה לכל העלים, יש להוסיף את הצומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} לאב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} של הצומת המקורי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} . אם האב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} הוא צומת-2 או צומת-3, התהליך הסתיים, והאב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} הופך לצומת-3 או צומת-4, בהתאמה. אולם אם הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} הוא צומת-4, נדרש לפצל גם אותו לפני ההוספה, ולהוסיף את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} לאחד מבניו (איור 9). תהליך זה של פיצול והוספה עשוי להמשיך להתרחש בדרך למעלה מן העלה לכיוון השורש (ומכאן השם: פיצול מלמטה למעלה), עד אשר מגיעים לצומת שאינו צומת-4, או שמפצלים את השורש (איור 10).

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

איור 8 - הוספת המפתח V לעץ מאיור 6, פיצול מלמטה למעלה, צעד 1
איור 9 - הוספת המפתח V לעץ מאיור 6, פיצול מלמטה למעלה, צעד 2
איור 10 - הוספת המפתח V לעץ מאיור 6, פיצול מלמטה למעלה, צעד 3

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

גם בשיטה זו, הכנסת מפתח חדש הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} מתחילה כמו חיפוש, בו מתקדמים במורד העץ עד אשר מגיעים לעלה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} בו מסתיים חיפוש כושל. אולם בניגוד לשיטה המתוארת לעיל, מוודאים שכאשר מגיעים לעלה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} מסוג צומת-4, ניתן יהיה לפצל אותו לשלושה צמתים כמתואר לעיל, ולמזג את הצומת העליון אל תוך האב , מבלי שיהיה צורך לפצל את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} .

את זאת משיגים על ידי כך שמפצלים כל צומת-4 בו נתקלים במהלך החיפוש במורד העץ, החל מהשורש (ומכאן השם: פיצול מלמעלה למטה, איורים 11-13). כאשר מפצלים צומת פנימי באופן זה, אין צורך לדאוג לאביו, כיוון שמובטח לנו שאינו צומת-4. מכיוון שכך, תמיד נוכל למזג את הצומת העליון מבין שלושת הצמתים אל האב. פיצול צומת אם כך, היא פעולה מקומית אשר אינה מתפשטת במעלה העץ. באופן זה, הכנסת מפתח נעשית במעבר אחד החל מהשורש ועד העלה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} . אם העלה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} הוא צומת-2 או צומת-3, מוסיפים לו את המפתח והתהליך הסתיים. אם העלה הוא צומת-4, מפצלים אותו. מכיוון שהאב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} אינו מסוג צומת-4 (אחרת היה מפוצל קודם לכן), הרי ניתן להוסיף לו את הצומת העליון מבין שלושת הצמתים שאליהם פוצל העלה, והתהליך הסתיים.

שגיאה ביצירת תמונה ממוזערת:
איור 11 - הוספת המפתח V לעץ מאיור 6, פיצול מלמעלה למטה, צעד 1
איור 12 - הוספת המפתח V לעץ מאיור 6, פיצול מלמעלה למטה, צעד 2
קובץ:Tree234 insert3c.svg
איור 13 - הוספת המפתח V לעץ מאיור 6, פיצול מלמעלה למטה, צעד 3

הוצאה

איור 14 - הוצאת המפתח Z מהעץ באיור 4
איור 15 - הוצאת המפתח F מהעץ באיור 14

הוצאת מפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} מעץ 2-3-4 מתקדמת במורד העץ כמו חיפוש, עד אשר נמצא הצומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} בו נמצא המפתח אותו רוצים להוציא.

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

אם המפתח נמצא בעלה, מוחקים אותו (איור 14). אם העלה הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} הוא מסוג צומת-3 או צומת-4, בכך הסתיים התהליך. אולם אם העלה הוא מסוג צומת-2, הוא הופך לעלה ריק אשר מפר את תכונות העץ. לשם שימור תכונות העץ מבצעים את פעולות השימור המתוארות בהמשך.

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

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

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

הוצאת מפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} מצומת פנימי מתבצעת באופן הבא (איור 15):

  1. מצא מחליף למפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} , הצב אותו במקום הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k} , והסר אותו מהעלה שבו היה מוצב.
  2. פעולה זו הסירה מפתח מעלה, ולכן שקולה למקרה הקודם.

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

לאחר הוצאת מפתח מעלה או מצומת פנימי הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} , ייתכן וצומת זה ישאר ללא מפתחות כלל, וללא בנים (במקרה של עלה) או עם בן אחד (במקרה של צומת פנימי). על מנת לשמר את מבנה העץ, מבצעים את סדרת הפעולות הבאות, החל מהעלה שהתרוקן.

  1. אם לצומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} יש מימין אח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} מסוג צומת-3 או צומת-4 (איור 16)
    1. מוסיפים את המפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k'} המפריד בין הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} ל- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} באב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} אל הצומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a}
    2. מסירים את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} , המפתח הקטן ביותר של צומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} ומכניסים אותו במקום המפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k'} של האב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p}
    3. מעבירים את הבן הראשון הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1} של צומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} להיות הבן האחרון של צומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a}
  2. אחרת, אם לצומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} יש משמאל אח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} מסוג צומת-3 או צומת-4 (איור 17)
    1. מוסיפים את המפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k'} המפריד בין הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} ל- הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} באב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} אל הצומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a}
    2. מסירים את הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle z} , המפתח הגדול ביותר של צומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} ומכניסים אותו במקום המפתח של האב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p}
    3. מעבירים את הבן האחרון (הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_3} או הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_4} ) של צומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} להיות הבן הראשון הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c_1} של צומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a}
  3. אם לצומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} אין אחים, מימין או משמאל, מסוג צומת-3 או צומת-4 (איור 18)
    1. צור צומת חדש המכיל את המפתחות של צומת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} , המפתחות של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} אחד מאחיו מימין או משמאל, והמפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k'} המפריד בין הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} לבין האח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} בצומת האב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p}
    2. הסר את המפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k'} מן האב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} , וחבר אל האב את הצומת החדש במקום שני הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,b} הצמתים שיצרו אותו
    3. אם הסרת המפתח הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k'} מן האב גורמת לו להפוך לצומת ללא מפתחות, חזור על תהליך האיזון מחדש עם צומת זה.
איור 16 - שימור מבנה העץ לאחר הוצאה, מקרה 1
איור 17 - שימור מבנה העץ לאחר הוצאה, מקרה 2
איור 18 - שימור מבנה העץ לאחר הוצאה, מקרה 3

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

שגיאה ביצירת תמונה ממוזערת:
איור 19 - שימור מבנה העץ לאחר הוצאה, הסרת השורש

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

איור 20 - יצוג בינארי של צומת-3 וצומת-4, באמצעות צמתים מסוג צומת-2
איור 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 פעולות החיפוש, ההכנסה, וההוצאה של מפתח מתבצעות בסיבוכיות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(\log n)} במקרה הגרוע ביותר.

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

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

ראו גם

לקריאה נוספת

  • 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.

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

ויקישיתוף ראו מדיה וקבצים בנושא זה בוויקישיתוף.

הערות שוליים

  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.