מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 27:
עץ חיפוש בינרי (או ''BST'' ) הוא עץ המורכב מ''צמתים''. כל צומת מכיל את השדות הבאים:
#מפתח
#(מצביע ל)אב
#(מצביע ל)בן השמאלי
#(מצביע ל)בן הימנילהלן הפסוודו-קוד לצומת:
שורה 41 ⟵ 36:
<source lang = "python">
Node
# The key this node holds.
1
# Parent.
2
# Left child.
3
# Right child.
4
# Makes a node with a given key (k)
Make-Node(k)
1
2
3
4
למבנה המתאר את העץ עצמו יש שני שדות: (מצביע ל)צומת השורש, ושדה המציין את גודל העץ (כלומר, את מספר הצמתים בו).
להלן הפסוודו-קוד לעץ:
שורה 72 ⟵ 66:
<source lang = "python">
Binary-Search-Tree
# The root (shoresh).
1
# Number of nodes.
2
# Makes an empty BST.
Make-Binary-Search-Tree()
1
2
3
4
{{הגדרה|תוכן =
עץ חיפוש בינרי חייב לקיים את ''תכונת הBST'' - לכל צומת {{קוד בשורה|x}}:
#אם {{קוד בשורה|y}} הוא צומת בתת העץ ה '''שמאלי''' של {{קוד בשורה|x}}, אז {{קוד בשורה|y.key \le x.key}}.
#אם {{קוד בשורה|y}} הוא צומת בתת העץ ה '''ימני''' של {{קוד בשורה|x}}, אז {{קוד בשורה|x.key \le y.key}}.}}
{{דוגמה|תוכן =
התרשים הבא מראה שני עצי חיפוש בינריים לקבוצת המפתחות <math dir = "ltr">\displaystyle \{2, 3, 5, 5, 7, 8\}</math>:
שורה 113 ⟵ 99:
{{הארה|1 =
לכל קבוצת מפתחות יש יותר מעץ חיפוש בינרי יחיד (אלא אם כן הקבוצה ריקה או מכילה איבר יחיד).}}
==חיפוש==
| |||