ויקיספר

מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים: הבדלים בין גרסאות בדף

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Atavory (שיחה | תרומות)
7,521 עריכות
Atavory (שיחה | תרומות)
7,521 עריכות
אין תקציר עריכה
שורה 275:
 
 
===פעולת הsplice===
==פעולות למעבר על כל איברי העץ==
 
 
נניח שלצומת אין בנים, או שלצומת יש רק בן יחיד. כדי להוציא את הצומת מהעץ, פשוט מחברים את אביו (אם יש לו כזה) עם בנו (אם יש לו כזה).
לעתים רוצים לעבור על כל איברי העץ, אם כדי להדפיסם, ואם למטרה אחרת. נראה כעת שלוש שיטות (רקורסיביות) מקובלות למעבר על כל איברי העץ, ונשתמש בהדפסה כדוגמה. בשיעורי הבית תתבקש להראות שכל אחד מזמני הריצה של המעברים הוא לינארי במספר האיברים בעץ.
 
===מעבר Pre-Order===
 
{{דוגמה|תוכן =
בצורת מעבר זו, כאשר מגיעים לצומת:
התרשים הבא מראה כיצד להוציא את הצומת בעל המפתח 7:
#ראשית מדפיסים את (איבר) הצומת עצמו
#לאחר מכן עוברים על תת העץ הימני שלו
#לאחר מכן עוברים על תת-העץ השמאלי שלו
 
<source lang = "python">
Pre-Order(nd)
1 if nd == Nil▼
2 return▼
 
[[תמונה:dsa_binary_search_splice.png|מרכז|100%|splice בעץ חיפוש בינרי.]]}}
3 Print(nd.value)
 
4 Pre-Order(nd.l-child)
5 Pre-order(nd.r-child)
</source>
 
הפסוודו-קוד הבא מממש זאת. (רובו מטפל במקרי קצה מעצבנים, כגון המקרה שבו הצומת המוצא הוא השורש.)
התרשים הבא מראה את סדר המעבר בצומת:▼
 
[[תמונה:dsa_binary_search_tree_pre_order.png|מרכז|100%|מעבר pre-order.]] ▼
 
 
===מעבר Post-Order===
 
בצורת מעבר זו, כאשר מגיעים לצומת:
#ראשית עוברים על תת-העץ השמאלי שלו
#לאחר מכן עוברים על תת העץ הימני שלו
#לאחר מכן מדפיסים את (איבר) הצומת עצמו
 
 
<source lang = "python">
# Splices (removes) a node (nd) from a tree (t).
Post-Order(nd)
# The node (nd) must not have two children.
1 if nd == Nil▼
Splice(t, nd)
2 return
1 child = nd.l_child == Nil ? nd.r-child : nd.l-child
 
2 parent = nd.parent
4 Post-Order(nd.l-child)
5 Post-order(nd.r-child)
 
▲13 if ndchild =!= Nil
3 Print(nd.value)
4 child.parent = parent
</source>
 
▲15 if ndparent == Nil
התרשים הבא מראה את סדר המעבר בצומת:▼
6 t.root = child
 
▲27 return
[[תמונה:dsa_binary_search_tree_post_order.png|מרכז|100%|מעבר post-order.]] ▼
 
8 if nd.key < parent.key
 
9 parent.l-child = child
===מעבר In-Order===
10 else
 
11 parent.r-child = child
בצורת מעבר זו, כאשר מגיעים לצומת:
#ראשית עוברים על תת-העץ השמאלי שלו
#לאחר מכן מדפיסים את (איבר) הצומת עצמו
#לאחר מכן עוברים על תת העץ הימני שלו
 
 
<source lang = "python">
In-Order(nd)
1 if nd == Nil
2 return
 
3 In-Order(nd.l-child)
 
4 Print(nd.value)
 
5 In-order(nd.r-child)
</source>
 
התרשים הבא מראה את סדר המעבר בצומת:▼
 
[[תמונה:dsa_binary_search_tree_in_order.png|מרכז|100%|מעבר in-order.]] ▼
 
בשיעורי הבית תתבקש להוכיח שצורת מעבר זו תדפיס את כל איברי העץ בסדר עולה.▼
 
===האלגוריתם===
שורה 395 ⟵ 354:
{{משפט|תוכן =
סיבוכיות הפעולה היא <math dir = "ltr">\displaystyle \Theta(h)</math> במקרה הגרוע, כאשר <math dir = "ltr">\displaystyle h</math> הוא גובה העץ.}}
 
 
==פעולות למעבר על כל איברי העץ==
 
 
לעתים רוצים לעבור על כל איברי העץ, אם כדי להדפיסם, ואם למטרה אחרת. נראה כעת שלוש שיטות (רקורסיביות) מקובלות למעבר על כל איברי העץ, ונשתמש בהדפסה כדוגמה. בשיעורי הבית תתבקש להראות שכל אחד מזמני הריצה של המעברים הוא לינארי במספר האיברים בעץ.
 
===מעבר Pre-Order===
שורה 418 ⟵ 378:
5 Pre-order(nd.r-child)
</source>
 
▲התרשים הבא מראה את סדר המעבר בצומת:
 
▲[[תמונה:dsa_binary_search_tree_pre_order.png|מרכז|100%|מעבר pre-order.]]
 
 
===מעבר Post-Order===
שורה 437 ⟵ 402:
3 Print(nd.value)
</source>
 
▲התרשים הבא מראה את סדר המעבר בצומת:
 
▲[[תמונה:dsa_binary_search_tree_post_order.png|מרכז|100%|מעבר post-order.]]
 
 
===מעבר In-Order===
שורה 457 ⟵ 427:
5 In-order(nd.r-child)
</source>
 
▲התרשים הבא מראה את סדר המעבר בצומת:
 
▲[[תמונה:dsa_binary_search_tree_in_order.png|מרכז|100%|מעבר in-order.]]
 
▲בשיעורי הבית תתבקש להוכיח שצורת מעבר זו תדפיס את כל איברי העץ בסדר עולה.
 
==סיכום==
 
בפרק זה ראינו מבנה לניהול נתונים בעל צורה כשל עץ. למעטרוב הפעולות הטריביאליות ביותר, כל הפעולותהמעניינות לינאריות ב<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>, נקבל מבנה נתונים יעיל. הפרק [[מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצים אדומים-שחורים|עצים אדומים-שחורים]] עוסק בכך.
אוחזר מתוך "https://he.wikibooks.org/wiki/מבני_נתונים_ואלגוריתמים_-_מחברת_קורס/מבני_נתונים/עצי_חיפוש_בינריים"