עץ בינארי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
לא קצרמר |
מ בוט החלפות: {{כ}}, \1 |
||
שורה 26:
* אם לכל העלים רמה n או n-1, ולא קיים עלה בעל רמה n שמשמאלו נמצא עלה בעל רמה n-1, אז העץ '''כמעט מלא'''.
* '''עץ בינארי מאוזן''' מוגדר על פי רוב כעץ שבו ההפרש בין הגובה של שני תתי-עצים של אותו הצומת לעולם אינו גדול מאחד. עם זאת באופן כללי מגדירים אותו כעץ בו כל הרמה של כל עלה אינה הרבה יותר גבוהה מהרמה של כל עלה אחר, כאשר בכל שיטת איזון מגדירים באופן שונה את המשמעות של "הרבה יותר גבוהה". לעצים מאוזנים לפי ההגדרה הראשונה יש גובה חסום, השווה לערך השלם של <math>\log_2(n)</math> כאשר n הוא מספר הצמתים בעץ.
* '''עץ בינארי מנוון''' הוא עץ בו לכל צומת שאינו עלה יש בן אחד בלבד.
== תכונות עצים בינאריים ==
שורה 33:
* מספר העלים <math>L</math> בעץ בינארי מושלם ניתן בנוסחה <math>L=2^h</math> כאשר <math>h</math> הוא גובה העץ.
* בעץ בינארי כמעט מלא, אם מספר הצמתים הוא <math>n</math> אז מספר הצמתים הפנימיים הוא <math>\left\lceil n/2\right\rceil</math>.
* בכל עץ לא ריק עם <math>n_0</math> עלים ו-<math>n_2</math> צמתים עם מדרגה 2 מתקיים <math>n_0 = n_2 + 1</math>.
and Hall. ISBN 1584884355.</ref>
| |||