8.3 עצים n-אריים כלליים

מבנה נתונים ואלגוריתמים

 

 

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

 

עץ חיפוש n'-ארי (עץ m-way) הוא:

1.      עץ ריק, או..

2.      עץ שבו שורש המכיל i מפתחות (1<= i<m) -  k_j, וסדרה של תתי-עצים - T_j, (j = 0...i) באופן הבא:

·            אם k הוא מפתח ב- T₀, אזי k <= k₁.

·            אם k הוא מפתח ב-  T_j (0<j<i), אזי k_j <= k <= k_{j +1}.

·            אם k הוא מפתח ב- T_i, אזי k > k_i, ו..

·            כל T_j הם עצי m-way שאינם ריקים או שכל T_j הם ריקים.

 

 

או בעברית פשוטה:

2. לצומת יש בדרך כלל m-1 מפתחות ו-m בנים. לכל צומת יש מצביעים לתת-עץ ומפתחות לסירוגין

     בצורה הבאה: תת-עץ | מפתח | תת-עץ | מפתח | .... | מפתח | תת-עץ.

§         כל המפתחות בתת-עץ שמשמאל למפתח הם קטנים ממנו.

§         כל המפתחות בצומת שבין שני מפתחות הם בטווח שבין שני מפתחות אלה.

§         כל המפתחות בתת-עץ שמימין למפתח הם גדולים ממנו.

§         זהו החלק הרקורסיבי ה"סטנדרטי" של ההגדרה.

 

 

גובהו של עץ m'-ארי מלא בעל n צמתים הוא ceiling(log_mn).

 

 

עץ B מסדר m הוא עץ m-way אשר בו:

 

1.      כל העלים נמצאים באותה רמה, ובנוסף...

2.      כל הצמתים מלבד השורש והעלים הם בעלי לפחות m/2 בנים ולכל היותר m בנים. השורש הוא בעל 2 בנים לפחות, והוא לכל היותר בעל m בנים.

 

גרסה של עץ B הידועה בשם עץ B+, מתייחסת לכל המפתחות בצמתים, מלבד אלה שבעלים, כ"גלמים". כל המפתחות משוכפלים בעלים. לשיטה זו יש יתרון מאיר שכל העלים מקושרים ביחד ברצף, והעץ כולו יכול להיסרק ללא ביקור בצמתים הגבוהים יותר.

 

 

מושגים

 

עצים n-אריים (או עצי n-way)

            עצים שכל צומת שלהם יתכנו עד כ- n בנים.

עץ B

גרסה מאוזנת של עץ n-way.

עץ B+

עץ שבו כל העלים מקושרים ומאפשרים מעבר in-order מהיר.

 

 

המשך ל: טבלאות גיבוב                 חזור ל: תוכן עניינים