עצי B

עצי חיפוש מסדר גבוה

אם נרצה, נוכל להכליל את כל המונחים שדיברנו עליהם עד עכשיו בהקשר של עצי חיפוש בינאריים, נוכל להגדיר עץ חיפוש מדרגה $m$ כאשר $m\ge 2$ אשר כל קודקוד בעץ הזה יקיים שיש לו לכל היותר $m$ ילדים ויכול להכיל לכל היותר $m-1$ מספרים בתוכו.

עצי חיפוש בינאריים הם מקרה פרטי של ההגדרה הזאת שכן $m=2$ . כלומר הם עצי חיפוש מסדר $2$ . ולכן יש להם גם רק ילד אחד בכל קודקוד.

הגדרה סדר= דרגת קודקוד= מספר הבנים שיש לאותו קודקוד.

• אם דרגת הקודקוד היא $k$ אז לקודקוד יהיו $k-1$ ערכים פנימיים ו $k$ מצביעים.

הגדרת ההכנסה לעץ כזה תהיה הכללה להכנסה לעץ בינארי :

יהי שורש $v_{x_i:i\in [k-1]}$ שערכיו $x_i:i\in [k-1]$ ו $k\le m$

• תת העץ השמאלי יכיל את הערכים שקטנים מ $x_1$
• תת העץ ה $i$ $2\le i<k$ יכיל רק אלמנטים שגדולים מ $x_{i-1}$
• תת העץ הימני ביותר (ה $k$-י) יכיל רק את האיברים שגדולים מ $x_{k-1}$

למשל עץ חיפוש מסדר 4:
שימו לב שמותר להצביע לילד שהוא null בעץ חיפוש מסדר m כללי

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

לא נתעמק ממש על הכנסה ומחיקה בעצי חיפוש מסדר גבוה כי כמו עצי חיפוש בינאריים הם חסומים ב $\mathrm{\Omega }(n)$ .
אבל!! ראינו עצי AVL ואיך הם עוזרים לנו להקטין את החסם על הפעולות על ידי הקטנת גובה העץ. וכעת, נדבר על האלטרנטיבה לעצי חיפוש מסדר גבוה שנותנת לנו בידיוק את הכוח הזה.

הגדרה של עצי B

עץ $B$ הוא עץ מסדר $m$ כאשר $m>2$ המקיים את התנאים הבאים :

• כל קודקוד חוץ מהשורש מכיל לפחות $\lceil \frac{m}{2}\rceil -1$ ערכים . השורש מכיל לפחות ערך אחד.
• רק לקודקודים ברמה הנמוכה ביותר יכול להיות ילד ריק.

מתנאי 2 ניתן להסיר שכל העלים בעצי $B$ הם באותה הרמה.
מהתנאי הראשון ביחד עם ההגדרה של עצי חיפוש מסדר $m$ מגביל את מספר הילדים של קודקוד פנימי (ללא השורש) בעצי $B$ להיות בין

דוגמה לעץ חיפוש מסדר $5$

עומק של עץ $B$ מסדר m

באופן כללי יתקיים עבור עץ $B$ מסדר $m$ המכיל $N$ ערכים :

כאשר $t$ מייצג רמה מסויימת בעץ.
מכאן אפשר להסיק ש

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

הכנסה

השלב הראשון הוא חיפוש , שלב החיפוש זהה לשלב החיפוש בעץ חיפוש מסדר m רגיל.

כעת לשם ההכנסה נחלק למקרים בהינתן שנרצה להכניס את הערך $y$

• הגענו לקודקוד $v_{x_i:i\in [k-1]}$ המקיים $k-1<m-1$ וגם הערך $y$ יכול להכנס באינדקס $j\in [k-1]$ , במצב זה נכניס אותו פשוט לרשימה במקום המתאים .
• הקודקוד שאליו נרצה להכניס כבר בתפוסה מלאה, הכנסה של הערך $y$ תשבור את התנאים של עצי $B$ . (למשל הכנסת 55 לעץ למעלה).
  במצב זה, נעשה מספר פעולות:

1. נכניס את הערך הרצוי ל קודקוד המתאים תוך כדי התעלמות ממצב ה $overflow$ שיצרנו.

2. בשלב השני נצטרך לתקן את החוסר איזון שיצרנו, (בהכרח חוסר איזון יהיה כשבקודקוד יש $m$ ערכים, לא יהיה יותר).

נסמן את האיברים בקודקוד $S=r_i:i\in [m]$ ונפצל אותו לתתי מערכים הבאים

החדים בינינו ישימו לב ש$r_{m/2}$ לא נמצא באף אחת מהקבוצות, תיכך נדבר עליו.

כעת נעשה את הדבר הפשוט הבא : נפצל את הקודקוד שהכיל את $S$ לשני קודקודים המכילים בהתאמה את הערכים שב $SL$ ו $SR$ .
שני הקודקודים החדשים יהיו ילדים ישירים של האבא ושכנים אחד של השני(נדבר מה יכול לקרות בהמשך), כמו כן הערך שלא נכנס לרשימה ייכנס באופן ריקורסיבי לאבא שמעליו מהסיבה שכעת הוספנו עוד ילד לאבא ולכן מהגדרת העץ צריך להוסיף עוד ערך (יש הפרש של 1 בין השניים) (אם גם באבא יש $overflow$ התהליך ממשיך באופן זהה).

התוצאה על העץ הנ״ל תהיה :

בוא נראה מה קורה אם נכניס עכשיו את הערך 3 לפי השלבים הנ״ל :
שלב ראשון :

והשלב השני:

אופס! קיבלנו $overflow$ גם בשורש, ובמצב זה סוף סוף העץ גדל בגובהו , בניגוד ל $AVL$ שבהכנסה ניצור עלה חדש ואז נאזן את הכל, כלומר בנייה מלמעלה למטה, כאן הבנייה היא מלמטה למעלה ולכן לא צריך שום טיפול מיוחד כדי לדאוג שכל העלים יהיו באותה רמה (מדהים לא?)

מה שיקרה בדוגמה שלנו בשלב הזה היא שנמשיך כרגיל אבל הפעם בגלל שהגענו ל $overflow$ בשורש אין לנו למי לחבר את שני הקודקודים המפוצלים שיצרנו , לכן ניצור שורש חדש שערכו יהיה $r_{m/2}$ שנוצר מהפיצול.

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

מבחינת יעילות, כמו חיפוש הפעולה חסומה באופן הדוק בגובה העץ $\mathrm{\Theta }({\log }_m(n))$

נשים לב לנקודה נוספת, מבחינת הבנייה של המבנה עבור $n$ ערכים.
מפתה להגיד שפשוט מבצעים את פעולה ההכנסה $n$ פעמים ולכן זה חסום ב $O(n{\log }_m(n))$ אבל זה לא המצב, כיוון שהעץ ריק ואנחנו יודעים שבכל קודקוד פרט לשורש יכולים להיות לפחות מספר הסדר $m$ חלקי 2 ערכים פנימיים , לכן עבור $n$ ערכים יהיה לכל היותר בקירוב $2n/m$ קודקודים. שזה בעצם $O(n/m)$ פיצולים.

מחיקה

כמו בעצי חיפוש בינאריים הכי קל לנו יהיה למחוק ערכים מעלים, ואם נרצה למחוק מערכים שאינם כאלה נמצא לו יורש בתוך העץ שיחליף אותו (ב $AVL$ זה יהיה עלה אחר). גם בעצי $B$ המצב יהיה דומה , אלגוריתם המחיקה ייראה כך

ה״יורש״ להחלפה במקרה של מחיקת קודקוד שאינו עלה יימצא באופן הבא

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

(מאוד דומה למציאת הערך הבא בהדפסת inorder של עץ בינארי).

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

כעת, נניח שנרצה למחוק את הערך $60$ בעץ למעלה, הוא הערך בשורש ולכן מחיקתו תוביל לכך שאין ערכים בקודקוד, במצב זה ובמצב זה $underflow$ בקודקודים פנימיים, מיד נשלים על ידי ה״יורש״ שהגדרנו למעלה (במקרה הזה 100).

על פניו נשמע מצויין , עם זאת , ניתן לראות שעלול להווצר מצב שבו בעלה יש מספר מועט מדי של ערכים, מה שלא מתאים להגדרה של עצי $B$ (במקרה שלנו יש דרישה למינימום 2 ערכים).

נשמע כאילו הפתרון יהיה למזג? כמו שעשינו פיצול בהכנסה, עם זאת זה לא המצב, כי בעוד שפיצול קודקוד זה אך ורק לפי ערכי הקודקוד , מיזוג לא בהכרח יהיה אפשרי בגלל שיש תלוי בערכי האבא. למשל אם נמזג את 110 עם הקודקוד מימינו , לא רק שנצטרך להוריד ערך אחד מהאבא אלא גם שהמצביעים לא יתאימו לערכים כלומר המצביע השמאלי לקודקוד (150,700) יכיל ערכים שקטנים וגדולים מ 150 וזה לא טוב.

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

המהלך הזה יתבצע בצורה הבאה :

• אם השכן המידי של קודקוד $v$ שהוא במצב $underflow$ מכיל מספר שיותר גבוה ממספר המינימום המותר של ערכים (כלומר שהסרת ערך אחד לא תפגע) . ניקח את הערך שהכי קרוב לקודקוד שממנו מוחקים בשכן המיידי (נסמן $x_l$) , ואת הערך שמפריד בין שני הילדים באבא נסמן $t$. נשים את $t$ בקודקוד שמצב $underflow$ במקום המתאים, ואת $x_l$ נשים במיקום של $t$ למשל עבור העץ הנ״ל ניקח את 150 , נשים אותו בקודקוד 110 מצד ימין, ואת 200 נשים במקום 150, באופן הבא :

נשים לב, שכן מידי = שכן ימני אם קיים ואם לא אז שכן שמאלי

• המצב השני יתרחש כאשר הורדת ערך מהשכן המידי לא מתאפשרת בגלל שגם לו יהיה $underflow$ , (למשל אם נרצה למחוק את 600) לא נוכל להשאיל את 704 . במצב זה נצטרך להשלים את הערך המתאים מהאבא ואם יש יותר מדי ילדים לאבא, יתקיים מיזוג של הקודקוד עם שכנו הימני. בגלל המצב של underflow אנחנו יודעים שניתן לעשות מיזוג כזה אחרי שהוספנו ערך מהאבא .

המיזוג ייראה כך (על מחיקת הערך 600)

גם כאן יש בעיה מחיקת הערך 700 מהאבא יצרה $underflow$ אצלו. לכן המחיקה במצב זה המחיקה תהיה ריקורסיבית כלומר שאם יש $underflow$ ,נצטרך גם פה לעשות $balancing$ . האיזון יהיה זהה למה שעשינו במחיקה מהעלה, אם אפשר להשלים מהשכן המידי , נשלים, רק שהפעם בגלל שאנחנו לא משלימים על עלה נסדר את הילדים בהתאם. למשל בדוגמה שלנו :

המקרה השני , הוא מצב לא גם באבא לא ניתן לאזן מהשכן המיידי ולכן נמזג ונשלים מהאבא שמעליו (ופה נכנסת הריקורסיה המדוברת) למשל, אם נמחק את 55 זה ייראה כך :


וככה נמשיך באופן ריקורסיבי עד הגעה לשורש.

גם פעולת המחיקה חסומה בגובה העץ כמו פעולה ההכנסה.

וריאנטים לעצי $B$

ישנם וריאנטים מכל מיני סוגים שמיועדים לייעל טיפה את המימוש הנ״ל או לתאר מקרים ספציפיים למשל עצי $B+$ שמכילים בתוכם עוד כמה אפשרויות לרוטציות או עצי $B\ast$ שמכילים את כל המידע בילדים וכך ניתן לבצע סריקה על כל הילדים לפי הסדר. אני רוצה לפרט בקצרה על מקרה פרטי ,

עץ 2-3

זה עץ $B$ המקיים ש $m=3$ באופן כללי כל קודקוד יכיל ערך אחד או שני ערכים , קודקוד עם ערך אחד יכיל 2 ילדים וקודקוד עם שני ערכים יכיל 3 ילדים.

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

האלגוריתם יעבוד בצורה הבאה:

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

דוגמה:

עצי +B

מוריד את כל ערכי העץ לילדים ומחבר מצביע בינהם וככה מקבלים את היכולת לסרוק את כל הערכים בצורה ליניארית במקום לסרוק את העץ בצורה אחרת.

נשים לב שברמות מעל העלים יש עותקים של הערכים המקומיים שנועדו לאפשר חיפוש מהיר יותר

הכנסה -
ההבדל כעת הוא שעל מנת שלא נשבור את הסדר של העלים למטה, נעלה כל פעם עותק של המידע במצב של overflow בהכנסה ופשוט מפצלים את העלים לפי הערך שהעלנו.

מחיקה-
מוצאים את הערך ברמת העלים ומוחקים אותו (בוודאות הוא נמצא כעלה). נשים לב שאין צורך למחוק את העותקים כי הם עדיין משמשים עבורו כ seperators תקינים בין העלים.

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