מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 113:
בעזרת [[#הגדרות|תכונת הBST]], קל לחפש צומת עם מפתח נתון בעץ. מתחילים בשורש, ויורדים (אם יש צורך) שמאלה או ימינה בהתאם לייחס בין המפתח בצומת לערך המבוקש.
להלן הפסוודו-קוד לפונקציה המקבלת עץ ומפתח, ומחזירה (מצביע ל)צומת המתאים למפתח (או {{קוד בשורה|Nil}} אם אין כזה).
<source lang = "python">
# Searches a tree (t) for a key (k).
שורה 128:
7 return Nil</source>
שורה 133 ⟵ 134:
{{משפט|תוכן =
סיבוכיות הפעולה היא <math dir = "ltr">\displaystyle \Theta(h)</math> במקרה הגרוע, כאשר <math dir = "ltr">\displaystyle h</math> הוא גובה העץ.}}
נוכל לכתוב פונקציה {{קוד בשורה|Member}}, המקבלת עץ ומפתח, ומחזירה האם המפתח נמצא בקבוצת האיברים של העץ.
<source lang = "python">
# Searches a tree (t) for a key (k).
# Returns whether the tree contains the key.
Member(t, k)
1 return Find(t, k) != Nil
</source>
==הכנסה==
|