עץ 2-3

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

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

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

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

קובץ:Tree23 example2.svg
איור 3 - דוגמה לעץ 2-3

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

  • הערך- מכיל תמיד את המפתח המקסימלי המצוי בתת-העץ השמאלי המחובר ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle l} .
  • תת-העץ המרכזי המחובר ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} מכיל מפתחות הגדולים מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} .
  • בצומת-3, הערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} מכיל את המפתח המקסימלי המצוי בתת-העץ המרכזי המחובר ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} .
  • בצומת-3, תת-העץ הימני המחובר ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} מכיל מפתחות הגדולים מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} .

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

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

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

חיפוש

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

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

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

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

הכנסה

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

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

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

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

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

הוצאה

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

לקריאה נוספת

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

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

הערות שוליים

  1. ^ 1.0 1.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. ^ 2.0 2.1 Knuth, Donald. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. מסת"ב 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


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

עץ 2-335192367Q169338

אוחזר מתוך "https://www.hamichlol.org.il/w/index.php?title=עץ_2-3&oldid=3058051"