תוֹכֶן

• טבלת השוואה
• הגדרת עץ B
• מאפייני עץ B מסדר M
• הגדרת עץ בינארי
• טכניקות מעבר
• סיכום

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

הבדל נוסף בין עץ B לעץ הבינארי הוא שעץ B חייב לכלול את צמתי הילד שלו באותה רמה ואילו לעץ הבינארי אין אילוץ כזה. עץ בינארי יכול להכיל 2 תת-עצים או צמתים לכל היותר ואילו בעץ B יכול להיות M לא של תת-עצים או צמתים שבהם M הוא סדר העץ.

1. טבלת השוואה
2. הגדרה
3. הבדלים עיקריים
4. סיכום

טבלת השוואה

בסיס להשוואה	עץ B	עץ בינארי
אילוץ חיוני	בצומת יכול להיות מספר M מקסימום של צמתי ילדים (כאשר M הוא סדר העץ).	צומת יכול להכיל מספר מקסימלי של 2 תת-עצים.
משומש	הוא משמש כאשר נתונים מאוחסנים בדיסק.	הוא משמש כאשר רשומות ונתונים מאוחסנים ב- RAM.
גובה העץ	יומןM N (כאשר m הוא סדר עץ M-way)	יומן2 נ
יישום	מבנה נתונים לאינדקס קוד ב- DBMS רבים.	מיטוב קוד, קידוד הופמן וכו '.

הגדרת עץ B

עץ B הוא עץ ה- M-way המאוזן הידוע גם כעץ המיון המאוזן. זה דומה לעץ חיפוש בינארי בו הצמתים מאורגנים על בסיס מעבר פנימי. מורכבות החלל של עץ B היא O (n). מורכבות זמן ההכנסה והמחיקה היא O (log n).

ישנם תנאים מסוימים שחייבים להיות נכונים עבור עץ B:

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

מאפייני עץ B מסדר M

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

הגדרת עץ בינארי

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

ישנן גרסאות מסוימות של עץ בינארי כמו עץ ​​בינארי בהחלט, עץ בינארי שלם, עץ בינארי מורחב וכו '.

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

טכניקות מעבר

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

• Inorder - במעברי עץ זה מבקרים את תת-המשנה השמאלי רקורסיבי ואז ביקרו בצומת השורש ובמשתמש הימני האחרון מבקרים.
• Preorer- במעבר עץ זה צובר השורש בתחילה ואז תת-המשנה השמאלי ובסוף התת-מימין הימני.
• Postorder- טכניקה זו מבקרת את התת-שמאל ואז את התת-מימין הימני ובצומת השורש האחרון.

1. בעץ B, המספר המרבי של צמתי ילדים שיכולים להיות לצומת לא סופני הוא M כאשר M הוא סדר העץ. מצד שני, עץ בינארי יכול לכלול לכל היותר שני תת-משנה או צמתי ילדים.
2. עץ B משמש כאשר נתונים מאוחסנים בדיסק ואילו עץ בינארי משמש כאשר נתונים מאוחסנים בזיכרון מהיר כמו זיכרון RAM.
3. תחום נוסף ליישום B-tree הוא מבנה הנתונים של אינדקס קוד ב- DBMS, לעומת זאת, עץ בינארי משמש לאופטימיזציית קוד, קידוד האפמן וכו '.
4. הגובה המרבי של עץ B הוא יומן_MN (M הוא סדר העץ). לעומת זאת, הגובה המרבי של העץ הבינארי הוא יומן₂N (N הוא מספר הצמתים והבסיס הוא 2 מכיוון שהוא בינארי).

סיכום

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