מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 101:
{{הארה|1 =
לכל קבוצת מפתחות יש יותר מעץ חיפוש בינרי יחיד (אלא אם כן הקבוצה ריקה או מכילה איבר יחיד).}}
נגדיר את ''גובה העץ'' כמרחק המקסימום מהשורש לעלה כלשהו.
{{דוגמה|תוכן =
בתרשים הקודם, A הוא בעל גובה 3, וB הוא בעל גובה 4.}}
==חיפוש==
שורה 125 ⟵ 130:
{{משפט|תוכן =
סיבוכיות הפעולה היא <math dir = "ltr">\displaystyle \Theta(h)</math> במקרה הגרוע, כאשר <math dir = "ltr">\displaystyle h</math> הוא גובה העץ
==הכנסה==
שורה 158 ⟵ 163:
{{משפט|תוכן =
סיבוכיות הפעולה היא <math dir = "ltr">\displaystyle \Theta(h)</math> במקרה הגרוע, כאשר <math dir = "ltr">\displaystyle h</math> הוא גובה העץ
==מינימום ומקסימום==
שורה 186 ⟵ 191:
{{משפט|תוכן =
סיבוכיות הפעולה היא <math dir = "ltr">\displaystyle \Theta(h)</math> במקרה הגרוע, כאשר <math dir = "ltr">\displaystyle h</math> הוא גובה העץ
שורה 230 ⟵ 235:
{{משפט|תוכן =
סיבוכיות הפעולה היא <math dir = "ltr">\displaystyle \Theta(h)</math> במקרה הגרוע, כאשר <math dir = "ltr">\displaystyle h</math> הוא גובה העץ
==מחיקה==
שורה 317 ⟵ 322:
{{משפט|תוכן =
סיבוכיות הפעולה היא <math dir = "ltr">\displaystyle \Theta(h)</math> במקרה הגרוע, כאשר <math dir = "ltr">\displaystyle h</math> הוא גובה העץ
==סיכום==
בפרק זה ראינו מבנה לניהול נתונים בעל צורה כשל עץ. למעט הפעולות הטריביאליות ביותר, כל הפעולות לינאריות ב<math dir = "ltr">\displaystyle h</math>, גובה העץ. נגדיר את מספר האיברים כ<math dir = "ltr">\displaystyle n</math>.
*אם <math dir = "ltr">\displaystyle h</math> ו<math dir = "ltr">\displaystyle n</math> באותו סדר גודל, הרי שקיבלנו מבנה נתונים שאינו יעיל משמעותית מ[[מבני נתונים ואלגוריתמים - מחברת קורס/רשימות מקושרות|רשימה מקושרת]].
*אם נוכל לנהל את המבנה כך ש<math dir = "ltr">\displaystyle h</math> יהיה קטן יחסית ל<math dir = "ltr">\displaystyle n</math>, נקבל מבנה נתונים יעיל. הפרק [[מבני נתונים ואלגוריתמים - מחברת קורס/עצים אדומים-שחורים]] עוסק בכך.
| |||