מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 92:
{{הארה|1=
זו אינה ההגדרה היחידה האפשרית לתכונת הBST.
להלן שתי הגדרות אחרות אפשריות.
{{הגדרה|תוכן =
עץ חיפוש בינרי חייב לקיים את ''תכונת הBST'' - לכל צומת {{קוד בשורה|x}}:
#אם {{קוד בשורה|y}} הוא צומת בתת העץ ה '''שמאלי''' של {{קוד בשורה|x}}, אז <span dir = "ltr">{{קוד בשורה|y.key}} <math>\le</math> {{קוד בשורה|x.key}}</span>.
#אם {{קוד בשורה|y}} הוא צומת בתת העץ ה '''ימני''' של <span dir = "ltr">{{קוד בשורה|x.key}} <math><</math> {{קוד בשורה|y.key}}</span>.
}}
{{הגדרה|תוכן =
עץ חיפוש בינרי חייב לקיים את ''תכונת הBST'' - לכל צומת {{קוד בשורה|x}}:
#אם {{קוד בשורה|y}} הוא צומת בתת העץ ה '''שמאלי''' של {{קוד בשורה|x}}, אז <span dir = "ltr">{{קוד בשורה|y.key}} <math><</math> {{קוד בשורה|x.key}}</span>.
#אם {{קוד בשורה|y}} הוא צומת בתת העץ ה '''ימני''' של <span dir = "ltr">{{קוד בשורה|x.key}} <math>\le</math> {{קוד בשורה|y.key}}</span>.
}}
ההבדלים הנגזרים משלוש ההגדרות קטנים למדי.
}}
{{דוגמה|תוכן =
|