מבנה נתונים -חילופיות מחיקת איברים מעץ
שלום רב אשמח אם למישהו יש רעיון איך להוכיח כי מחיקת איברים מעץ בינארי הוא חילופי. משמע במידהואני מוחק קודם איבר X ואחריו איבר Y העץ שיתקבל בסוף למחיקה יהיה זהה לחלוטין לעץ בו קודם הייתי מוחק איבר Y ולאחר מכן את איבר X. הטענה נכונה ונבדקה, הבעיה היא עם ניסוח ההוכחה.
שלום רב אשמח אם למישהו יש רעיון איך להוכיח כי מחיקת איברים מעץ בינארי הוא חילופי. משמע במידהואני מוחק קודם איבר X ואחריו איבר Y העץ שיתקבל בסוף למחיקה יהיה זהה לחלוטין לעץ בו קודם הייתי מוחק איבר Y ולאחר מכן את איבר X. הטענה נכונה ונבדקה, הבעיה היא עם ניסוח ההוכחה.
: זה מה שכתבתי עד עכשיו - ג) נפתח בהגדרה של עץ חיפוש בינארי- זהו עץ בינארי בו בכל צמת הבן הימני גדול-שווה לאב ,והבן השמאלי קטן-שווה לאב. ולכן כל האיברים בתת-עץ הימני תמיד קטנים-שווים לערך האב וכן כל האיברים בתת-עץ הימני תמיד קטנים-שווים לערך האב. מההגדרה ניתן להסיק כי מחיקת איבר מעץ חיפוש בינארי חייבת לשמור על חוקיות מיקום שאר האיברים בעץ החיפוש: במידה ונמחק איבר שקטן מהשורש – האיבר המחליף חייב להיות יותר גדול מבניו השמליים של האיבר הנמחק, קטן יותר מבניו הימניים ולהיות קטן מהשורש. במידה ונמחק איבר שגדול או שווה לשורש עצמו – האיבר המחליף חייב להיות יותר גדול מבניו השמליים של האיבר הנמחק, קטן יותר מבניו הימניים ולהיות גדול מהשורש. מסקנה : האיבר המתאים ביותר לרוטציה עם האיבר הנמחק הינו האיבר השמאלי ביותר של הבן הימני של האיבר הנמחק. לכן מחיקת איברים משני תתי עץ שונים או מחיקת צומת/שורש ואיבר מתת עץ שמאלי לא ישפיעו על תצורתו הסופית של העץ. X – שורש/צומת Y- איבר בתת-עץ שמאלי של X X>Y כל איבריו של Y מקיימים את האי-שוויון לכן הרוטציה תתבבצע עם איברים הגדולים מY שאינם מתת-עץ X. בהוצאת 2 איברים סמוכים מאותו תת עץ או הוצאת איבר מתת עץ ימני והשורש, עקב החוקיות לא משנה מי ימחק קודם היחס בין האיברים המחליפים אותם נשמר. X – שורש/צומת Y - איבר בתת-עץ ימני של X Y>X כל איבריו של X מקיימים את האי-שוויון לכן הרוטציה תתבבצע עם איברים הגדולים מY הנמצאים בהמשכו של תת-עץ כלפי מטה ולא ישנו את היחס של האיבר החדש עם השורש הקטן מהם. אבל זה נראה לי עמוס ולא ברור