הבדלים בין גרסאות בדף "עץ חיפוש"

נוספו 692 בתים ,  לפני 7 שנים
אין תקציר עריכה
מ (שוחזר מעריכות של 62.0.200.129 (שיחה) לעריכה האחרונה של Shwartz)
 
כדי להוסיף קודקוד חדש לעץ יעבור ה[[אלגוריתם]] על כל קודקוד וקודקוד החל מהשורש, וינוע ימינה כאשר מפתח הקודקוד הנוכחי במסלול קטן מהמפתח של הקודקוד המוכנס, ושמאלה במקרה ההפוך. האלגוריתם ייעצר ויבצע את ההוספה במקום שבו המסלול ייגמר.
 
 
כדי למחוק קודקוד יש תחילה למצוא אותו, ולאחר מכן אם הוא עלה פשוט למחוק אותו, אם יש לו בן אחד בלבד למחוק ולהפוך את הבן הזה לבן של האבא של מה שמחקנו, ואם יש לו שני בנים, למצוא את העוקב (הקודקוד הקטן ביותר שגדול ממנו) שבהכרח אין לו בן שמאלי, למחוק את העוקב ולהחליף את הקודקוד שלנו בעוקב. לשם ביצוע פעולות אלו ביעילות יש לשמור גם [[מצביע]] להורה.
 
מאחר שלעץ בינארי יש שני בנים, הרי שבמקרה של עץ מלא במידה שווה, גובהו יהיה Log n, עבור n נתונים (log בסיס 2). במצב כזה חיפוש בעץ יימשך פרק זמן קצר יחסית הנמצא ב[[סיבוכיות]] לוגריתמית למספר הנתונים. אומנם, ייתכנו מקרים גרועים, למשל הכנסה בסדר ממוין מראש, שבהם גובה העץ יהיה n, ועלות החיפוש גבוהה.
if node.right != null then visit(node.right)
</div>
עץ הוא עץ חיפוש [[אם ורק אם]] הסדר התוכי שלו ממוין.
 
===סדר סופי (postorder traversal)===
קריאת תת-העץ השמאלי, לאחר מכן תת-העץ הימני ולאחר מכן קריאת השורש. בהינתן הדפסת עץ המתבססות על סדר סופי, ניתן אף לשחזר את העץ בצורה חד-חד ערכית, אם אכן הוא עומד במאפייניו של עץ חיפוש.
8,258

עריכות