TechCodeview

עצי ספליי הם עצי החיפוש הבינאריים המאזנים את עצמם או בהתאמה עצמית. במילים אחרות, אנו יכולים לומר שעצי ה-splay הם הווריאציות של עצי החיפוש הבינאריים. התנאי המקדים לעצי הספליי שעלינו לדעת על עצי החיפוש הבינאריים.

כפי שאנו כבר יודעים, מורכבות הזמן של עץ חיפוש בינארי בכל מקרה. מורכבות הזמן של עץ חיפוש בינארי במקרה הממוצע היא O(לוגן) ומורכבות הזמן במקרה הגרוע היא O(n). בעץ חיפוש בינארי, הערך של תת-העץ השמאלי קטן מצומת השורש, והערך של תת-העץ הימני גדול יותר מצומת השורש; במקרה כזה, מורכבות הזמן תהיה O(לוגן) . אם העץ הבינארי מוטה שמאלה או ימינה, אז מורכבות הזמן תהיה O(n). כדי להגביל את העיוות, ה AVL ועץ אדום-שחור נכנס לתמונה, לאחר O(כניסה ) מורכבות זמן לכל הפעולות בכל המקרים. אנחנו יכולים גם לשפר את מורכבות הזמן על ידי ביצוע יישומים מעשיים יותר, אז העץ החדש מה זה עץ ספליי?

עץ ספליי הוא עץ המאזן את עצמו, אבל עצי AVL ואדום-שחור הם גם עצים מאזנים עצמיים. מה מייחד את עץ הספליי שני עצים. יש לו מאפיין אחד נוסף שהופך אותו לייחודי הוא התפשטות.

עץ ספליי מכיל את אותן פעולות כמו א עץ חיפוש בינארי , כלומר, הכנסה, מחיקה וחיפוש, אבל הוא מכיל גם פעולה אחת נוספת, כלומר, splaying. כך. כל הפעולות בעץ ה-splay מלווה ב-splaying.

עצי ספליי הם לא עצים מאוזנים למהדרין, אבל הם עצים מאוזנים בערך. בואו נבין את פעולת החיפוש ב-splay-tree.

נניח שאנו רוצים לחפש אלמנט 7 בעץ, שמוצג להלן:

כדי לחפש אלמנט כלשהו בעץ הספליי, ראשית, נבצע את פעולת עץ החיפוש הבינארי הרגילה. מכיוון ש-7 הוא פחות מ-10 כך נגיע משמאל לצומת השורש. לאחר ביצוע פעולת החיפוש, עלינו לבצע splaying. כאן חלוקה פירושה שהפעולה שאנו מבצעים על כל אלמנט צריכה להפוך לצומת השורש לאחר ביצוע כמה סידורים מחדש. הסידור מחדש של העץ יתבצע באמצעות הסיבובים.

הערה: ניתן להגדיר את עץ ה-splay כעץ המותאם את עצמו בו כל פעולה שתבוצע על האלמנט תסדר מחדש את העץ כך שהאלמנט עליו בוצעה הפעולה יהפוך לצומת השורש של העץ.

סיבובים

ישנם שישה סוגים של סיבובים המשמשים לפיזור:

1. סיבוב זיג (סיבוב ימינה)
2. סיבוב זג (סיבוב שמאלה)
3. זיג זג (זיג ואחריו זג)
4. זג זיג (זג ואחריו זיג)
5. זיג זיג (שני סיבובים ימינה)
6. זג זג (שני סיבובים שמאלה)

גורמים הנדרשים לבחירת סוג סיבוב

להלן הגורמים המשמשים לבחירת סוג סיבוב:

• האם לצומת שאנו מנסים לסובב יש סבא וסבתא?
• האם הצומת משמאל או ימין של ההורה?
• האם הצומת משמאל או ימין הוא בן של הסבא והסבתא?

תיקים לרוטציות

תיק 1: אם לצומת אין סבא-הורה, ואם זה הילד הימני של ההורה, אז אנחנו מבצעים את הסיבוב שמאלה; אחרת, הסיבוב הימני מתבצע.

מקרה 2: אם לצומת יש סבא וסבתא, אז בהתבסס על התרחישים הבאים; הסיבוב יבוצע:

תרחיש 1: אם הצומת הוא זכותו של ההורה וההורה הוא גם זכותו של ההורה שלו, אז זיג זיג סיבוב ימינה ימינה מבוצע.

תרחיש 2: אם הצומת שמאל של הורה, אבל ההורה הוא ימין של ההורה שלו, אז זיגזג סיבוב ימינה שמאלה מבוצע.

תרחיש 3: אם הצומת הוא ימין של ההורה וההורה הוא ימין של ההורה שלו, אז זיג זיג סיבוב שמאלה שמאלה מבוצע.

תרחיש 4: אם הצומת הוא מימין להורה, אבל ההורה שמאלי מההורה שלו, אז זיגזג סיבוב ימינה-שמאלה מבוצע.

כעת, בואו נבין את הסיבובים לעיל עם דוגמאות.

כדי לסדר מחדש את העץ, אנחנו צריכים לבצע כמה סיבובים. להלן סוגי הסיבובים בעץ הספליי:

סיבובי זיג

סיבובי הזיג משמשים כאשר הפריט שיש לחפש הוא צומת שורש או צאצא של צומת שורש (כלומר, שמאל או צאצא ימני).

להלן המקרים שיכולים להתקיים בעץ הספליי בזמן החיפוש:

תיק 1: אם פריט החיפוש הוא צומת שורש של העץ.

מקרה 2: אם פריט החיפוש הוא צאצא של צומת השורש, אז שני התרחישים יהיו שם:

1. אם הילד הוא ילד שמאלי, יתבצע הסיבוב הימני, המכונה סיבוב זיג ימינה.
2. אם הילד הוא ילד ימני, הסיבוב השמאלי יבוצע, המכונה סיבוב זיג שמאלה.

הבה נסתכל על שני התרחישים לעיל באמצעות דוגמה.

שקול את הדוגמה הבאה:

בדוגמה שלמעלה, עלינו לחפש אלמנט 7 בעץ. נבצע את השלבים הבאים:

שלב 1: ראשית, אנו משווים 7 עם צומת שורש. מכיוון ש-7 הוא פחות מ-10, כך הוא ילד שמאלי של צומת השורש.

שלב 2: לאחר שהאלמנט נמצא, נבצע splaying. הסיבוב הימני מתבצע כך ש-7 הופך לצומת השורש של העץ, כפי שמוצג להלן:

הבה נבחן דוגמה נוספת.

בדוגמה שלמעלה, עלינו לחפש אלמנט 20 בעץ. נבצע את השלבים הבאים:

שלב 1: ראשית, אנו משווים 20 עם צומת שורש. כפי ש-20 גדול מצומת השורש, כך הוא ילד ימני של צומת השורש.

שלב 2: לאחר שהאלמנט נמצא, נבצע splaying. הסיבוב השמאלי מתבצע כך שאלמנט 20 הופך לצומת השורש של העץ.

סיבובי זיג זיג

לפעמים המצב נוצר כאשר הפריט לחיפוש הוא בעל הורה וגם סבא וסבתא. במקרה זה, עלינו לבצע ארבע סיבובים לפיזור.

בואו נבין את המקרה הזה באמצעות דוגמה.

נניח שעלינו לחפש אלמנט אחד בעץ, שמוצג להלן:

שלב 1: ראשית, עלינו לבצע פעולת חיפוש BST רגילה על מנת לחפש באלמנט 1. כפי ש-1 הוא פחות מ-10 ו-7, כך הוא יהיה בצד שמאל של הצומת 7. לכן, לרכיב 1 יש הורה, כלומר 7 וגם סבא וסבתא, כלומר 10.

שלב 2: בשלב זה, עלינו לבצע splaying. אנחנו צריכים להפוך את צומת 1 כצומת שורש בעזרת כמה סיבובים. במקרה זה, איננו יכולים פשוט לבצע סיבוב זיג או זג; עלינו ליישם סיבוב זיג זיג.

על מנת להפוך את צומת 1 כצומת שורש, עלינו לבצע שני סיבובים ימניים המכונה סיבובי זיג זיג. כאשר אנו מבצעים את הסיבוב הימני אז 10 יזוז כלפי מטה, וצומת 7 יגיע כלפי מעלה כפי שמוצג באיור שלהלן:

שוב, נבצע סיבוב זיג ימינה, צומת 7 יזוז כלפי מטה, וצומת 1 יגיע כלפי מעלה כפי שמוצג להלן:

כפי שאנו רואים באיור לעיל שצומת 1 הפך לצומת השורש של העץ; לכן, החיפוש הושלם.

נניח שאנו רוצים לחפש 20 בעץ למטה.

על מנת לחפש 20, עלינו לבצע שני סיבובים שמאלה. להלן השלבים הנדרשים לחיפוש צומת 20:

שלב 1: ראשית, אנו מבצעים את פעולת החיפוש הסטנדרטית של BST. מכיוון ש-20 גדול מ-10 ו-15, כך הוא יהיה מימין לצומת 15.

שלב 2: השלב השני הוא לבצע splaying. במקרה זה, יבוצעו שני סיבובים שמאלה. בסיבוב הראשון, צומת 10 יזוז כלפי מטה, וצומת 15 יזוז כלפי מעלה כפי שמוצג להלן:

בסיבוב השני שמאלה, צומת 15 ינוע כלפי מטה, וצומת 20 הופך לצומת השורש של העץ, כפי שמוצג להלן:

כפי שראינו שמבוצעים שני סיבובים שמאלה; אז זה ידוע בתור סיבוב זיג זיג שמאלה.

סיבובי זיג זג

עד עכשיו, קראנו שגם הורה וגם סבא וסבתא נמצאים במערכת יחסים RR או LL. כעת, נראה את הקשר RL או LR בין ההורה והסבא.

בואו נבין את המקרה הזה באמצעות דוגמה.

נניח שאנו רוצים לחפש אלמנט 13 בעץ שמוצג להלן:

שלב 1: ראשית, אנו מבצעים פעולת חיפוש BST רגילה. מכיוון ש-13 גדול מ-10 אך פחות מ-15, כך שצומת 13 יהיה הילד השמאלי של צומת 15.

שלב 2: מכיוון שצומת 13 נמצא משמאל ל-15 וצומת 15 נמצא מימין לצומת 10, כך שקיים קשר RL. ראשית, אנו מבצעים את הסיבוב הימני בצומת 15, ו-15 ינוע כלפי מטה, וצומת 13 יבוא כלפי מעלה, כפי שמוצג להלן:

ובכל זאת, צומת 13 אינו צומת השורש, ו-13 נמצא מימין לצומת השורש, אז נבצע סיבוב שמאלה המכונה סיבוב זג. הצומת 10 ינוע כלפי מטה, ו-13 הופך לצומת השורש כפי שמוצג להלן:

כפי שאנו יכולים לראות בעץ לעיל שצומת 13 הפך לצומת השורש; לכן, החיפוש הושלם. במקרה זה, ביצענו תחילה את סיבוב הזיג ולאחר מכן את סיבוב הזג; אז זה ידוע בתור סיבוב זיג זג.

סיבוב זג זיג

בואו נבין את המקרה הזה באמצעות דוגמה.

נניח שאנו רוצים לחפש אלמנט 9 בעץ, שמוצג להלן:

שלב 1: ראשית, אנו מבצעים את פעולת החיפוש הסטנדרטית של BST. מכיוון ש-9 הוא פחות מ-10 אך גדול מ-7, כך הוא יהיה הילד הנכון של צומת 7.

שלב 2: מכיוון שצומת 9 נמצא מימין לצומת 7, וצומת 7 נמצא משמאל לצומת 10, כך שקיים קשר LR. ראשית, אנו מבצעים את הסיבוב שמאלה בצומת 7. הצומת 7 יזוז כלפי מטה, והצומת 9 זז כלפי מעלה כפי שמוצג להלן:

עדיין הצומת 9 אינו צומת שורש, ו-9 נמצא משמאל לצומת השורש, אז נבצע את הסיבוב הימני המכונה סיבוב זיג. לאחר ביצוע הסיבוב הימני, צומת 9 הופך לצומת השורש, כפי שמוצג להלן:

כפי שאנו יכולים לראות בעץ לעיל שצומת 13 הוא צומת שורש; לכן, החיפוש הושלם. במקרה זה, ביצענו תחילה את סיבוב הזג (סיבוב שמאלה), ולאחר מכן מתבצע סיבוב זיג (סיבוב ימינה), כך שהוא ידוע כסיבוב זג זיג.

היתרונות של עץ Splay

• בעץ הספליי, איננו צריכים לאחסן את המידע הנוסף. לעומת זאת, בעצי AVL, עלינו לאחסן את גורם האיזון של כל צומת הדורש שטח נוסף, ועצים אדומים-שחורים דורשים גם לאחסן ביט נוסף אחד של מידע שמציין את צבע הצומת, אדום או שחור.
• זהו הסוג המהיר ביותר של עץ חיפוש בינארי עבור יישומים מעשיים שונים. הוא משמש ב מהדרים של Windows NT ו-GCC .
• זה מספק ביצועים טובים יותר מכיוון שהצמתים הנגישים לעתים קרובות יתקרבו לצומת השורש, ובגלל זה ניתן לגשת לאלמנטים במהירות בעצי חלוקה. הוא משמש בהטמעת המטמון שכן הנתונים שניגשו לאחרונה מאוחסנים במטמון כך שלא נצטרך ללכת לזיכרון כדי לגשת לנתונים, וזה לוקח פחות זמן.

חסרון של עץ Splay

החיסרון העיקרי של עץ הפרוס יהיה שהעצים אינם מאוזנים בקפדנות, כלומר, הם מאוזנים בערך. לפעמים עצי הפרוס הם ליניאריים, כך שזה ייקח מורכבות זמן O(n).

פעולת הכנסה בעץ Splay

בתוך ה הַכנָסָה הפעולה, תחילה אנו מכניסים את האלמנט לעץ ולאחר מכן מבצעים את פעולת ה-splaying על האלמנט שהוכנס.

15, 10, 17, 7

שלב 1: ראשית, אנו מכניסים את צומת 15 לעץ. לאחר ההכנסה, עלינו לבצע splaying. מכיוון ש-15 הוא צומת שורש, אז אנחנו לא צריכים לבצע splaying.

שלב 2: האלמנט הבא הוא 10. מכיוון ש-10 הוא פחות מ-15, כך שצומת 10 יהיה הילד השמאלי של צומת 15, כפי שמוצג להלן:

עכשיו, אנחנו מופיעים מתפזרים . כדי ליצור 10 כצומת שורש, נבצע את הסיבוב הנכון, כפי שמוצג להלן:

שלב 3: האלמנט הבא הוא 17. מכיוון ש-17 גדול מ-10 ו-15 כך הוא יהפוך לילד הנכון של צומת 15.

כעת, נבצע ספלייינג. כשגיל 17 יש הורה וגם סבא וסבתא כך נבצע סיבובי זיג זיג.

באיור לעיל, אנו יכולים לראות ש-17 הופך לצומת השורש של העץ; לכן, ההכנסה הושלמה.

שלב 4: האלמנט הבא הוא 7. מכיוון ש-7 הוא פחות מ-17, 15 ו-10, כך שצומת 7 יישאר בן 10.

עכשיו, אנחנו צריכים לפזר את העץ. מכיוון של-7 יש הורה וגם סבא וסבתא, כך נבצע שני סיבובים ימניים כפי שמוצג להלן:

עדיין הצומת 7 אינו צומת שורש, הוא צאצא שמאלי של צומת השורש, כלומר, 17. לכן, עלינו לבצע עוד סיבוב ימני אחד כדי להפוך את צומת 7 לצומת שורש כפי שמוצג להלן:

אלגוריתם לפעולת הכנסה

 Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n) 

באלגוריתם לעיל, T הוא העץ ו-n הוא הצומת שאנו רוצים להכניס. יצרנו משתנה טמפ' המכיל את הכתובת של צומת השורש. נריץ את לולאת while עד שהערך של temp יהפוך ל-NULL.

לאחר השלמת ההחדרה, יתבצע פיזור

אלגוריתם לפעולת Splaying

 Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y 

ביישום לעיל, x הוא הצומת עליו מבוצע הסיבוב, ואילו y הוא הילד השמאלי של הצומת x.

יישום של left.rotation(T, x)

 left.rotation(T, x) y=x->right x->right = y->left y->left = x return y 

ביישום לעיל, x הוא הצומת עליו מבוצע הסיבוב ו-y הוא הילד הימני של הצומת x.

מחיקה בעץ Splay

כפי שאנו יודעים שעצי splay הם הווריאציות של עץ החיפוש הבינארי, אז פעולת המחיקה בעץ ה-splay תהיה דומה ל-BST, אך ההבדל היחיד הוא שפעולת המחיקה מלווה בעצי ה-splay על ידי פעולת ה-splaying.

סוגי מחיקות:

ישנם שני סוגים של מחיקות בעצי הספליי:

1. התפשטות מלמטה למעלה
2. התפשטות מלמעלה למטה

התפשטות מלמטה למעלה

ב-splaying מלמטה למעלה, תחילה אנו מוחקים את האלמנט מהעץ ולאחר מכן אנו מבצעים את ה-splaying על הצומת שנמחק.

בואו נבין את המחיקה בעץ ה-Splay.

נניח שאנו רוצים למחוק 12, 14 מהעץ המוצג להלן:

מערכות הפעלה מק

• ראשית, אנו פשוט מבצעים את פעולת המחיקה הרגילה של BST כדי למחוק 12 אלמנטים. כפי ש-12 הוא צומת עלה, אז אנחנו פשוט מוחקים את הצומת מהעץ.

המחיקה עדיין לא הושלמה. אנחנו צריכים לפזר את האב של הצומת שנמחק, כלומר, 10. אנחנו צריכים לבצע Splay(10) על העץ. כפי שאנו יכולים לראות בעץ לעיל ש-10 נמצא מימין לצומת 7, וצומת 7 נמצא משמאל לצומת 13. לכן, ראשית, אנו מבצעים את הסיבוב שמאלה בצומת 7 ולאחר מכן אנו מבצעים את הסיבוב הימני בצומת 13, כפי שמוצג להלן:

ובכל זאת, צומת 10 אינו צומת שורש; צומת 10 הוא הילד השמאלי של צומת השורש. אז, אנחנו צריכים לבצע את הסיבוב הנכון על צומת השורש, כלומר, 14 כדי להפוך את צומת 10 לצומת שורש כפי שמוצג להלן:

• כעת, עלינו למחוק את האלמנט 14 מהעץ, שמוצג להלן:

כפי שאנו יודעים שאיננו יכולים פשוט למחוק את הצומת הפנימי. נחליף את הערך של הצומת באמצעות קודמו בהזמנה אוֹ יורש לא-סדר . נניח שאנו משתמשים ב-inorder successor שבו נחליף את הערך בערך הנמוך ביותר שקיים בתת-עץ הימני. הערך הנמוך ביותר בתת-עץ הימני של צומת 14 הוא 15, אז אנחנו מחליפים את הערך 14 ב-15. מכיוון שצומת 14 הופך לצומת העלה, אז אנחנו יכולים פשוט למחוק אותו כפי שמוצג להלן:

ובכל זאת, המחיקה לא הושלמה. אנחנו צריכים לבצע עוד פעולה אחת, כלומר, splaying שבה אנחנו צריכים להפוך את האב של הצומת שנמחק כצומת השורש. לפני המחיקה, האב של צומת 14 היה צומת השורש, כלומר, 10, אז אנחנו צריכים לבצע כל ספלייינג במקרה זה.

התפשטות מלמעלה למטה

ב-splaying מלמעלה למטה, אנו מבצעים תחילה את ה-splaying שעליו יש לבצע את המחיקה ולאחר מכן מוחקים את הצומת מהעץ. לאחר מחיקת האלמנט, נבצע את פעולת הצטרפות.

הבה נבין את ההפרשה מלמעלה למטה דרך דוגמה.

נניח שאנו רוצים למחוק 16 מהעץ שמוצג להלן:

שלב 1: ב-splaying מלמעלה למטה, ראשית אנו מבצעים splaying על הצומת 16. לצומת 16 יש גם הורה וגם סבא וסבתא. הצומת 16 נמצא בצד ימין של האב שלו וצומת האב נמצא גם בצד ימין של ההורה שלו, אז זה מצב של זג זג. במקרה זה, ראשית, נבצע את הסיבוב שמאלה בצומת 13 ולאחר מכן 14 כפי שמוצג להלן:

הצומת 16 עדיין אינו צומת שורש, והוא בן ימני של הצומת השורש, ולכן עלינו לבצע סיבוב שמאלה על הצומת 12 כדי להפוך את הצומת 16 לצומת שורש.

ברגע שהצומת 16 הופך לצומת שורש, נמחק את הצומת 16 ונקבל שני עצים שונים, כלומר תת-עץ שמאלי ותת-עץ ימני כפי שמוצג להלן:

כפי שאנו יודעים שהערכים של תת-העץ השמאלי תמיד נמוכים יותר מהערכים של תת-העץ הימני. השורש של תת העץ השמאלי הוא 12 והשורש של תת העץ הימני הוא 17. השלב הראשון הוא למצוא את האלמנט המקסימלי בתת העץ השמאלי. בתת-עץ השמאלי, האלמנט המקסימלי הוא 15, ואז עלינו לבצע פעולת חלוקה על 15.

כפי שאנו יכולים לראות בעץ לעיל שלאלמנט 15 יש הורה וגם סבא וסבתא. צומת נמצא מימין להאב שלו, וצומת האב נמצא גם מימין להאב שלו, אז אנחנו צריכים לבצע שני סיבובים שמאלה כדי להפוך את צומת 15 לצומת שורש כפי שמוצג להלן:

לאחר ביצוע שני סיבובים על העץ, צומת 15 הופך לצומת השורש. כפי שאנו יכולים לראות, הילד הימני של ה-15 הוא NULL, אז אנו מצמידים את הצומת 17 בחלק הימני של ה-15 כפי שמוצג להלן, והפעולה הזו ידועה בתור לְהִצְטַרֵף מבצע.

הערה: אם האלמנט אינו קיים בעץ ה-splay, שאמור להימחק, יתבצע splaying. ה-splaying יבוצע על הרכיב האחרון שניגש אליו לפני הגעה ל-NULL.

אלגוריתם של פעולת מחיקה

 If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root 

באלגוריתם הנ'ל, קודם כל בודקים אם השורש הוא Null או לא; אם השורש הוא NULL פירושו שהעץ ריק. אם העץ לא ריק, נבצע את פעולת ה-splaying על האלמנט שאמור להימחק. לאחר השלמת פעולת ה-splaying, נשווה את נתוני השורש עם האלמנט שאמור להימחק; אם שניהם אינם שווים פירושו שהאלמנט אינו קיים בעץ. אם הם שווים, המקרים הבאים יכולים להתרחש:

תיק 1 : השמאלי של השורש הוא NULL, ימין השורש הופך לצומת השורש.

מקרה 2 : אם קיימים גם שמאל וגם ימין, אז אנו מפיצים את האלמנט המקסימלי בתת העץ השמאלי. לאחר השלמת הפיזור, האלמנט המקסימלי הופך לשורש של תת-העץ השמאלי. תת-העץ הימני יהפוך לילד הימני של השורש של תת-העץ השמאלי.