עץ Splay – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ מיון חדש לקטגוריה:עצי חיפוש: "Splay" באמצעות HotCat |
אין תקציר עריכה תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
||
שורה 1:
ב[[מדעי המחשב]], עץ Splay הוא [[מבנה נתונים]] של [[עץ חיפוש]] בינארי לא בהכרח מאוזן בעל התכונה המאפשרת גישה חוזרת מהירה לאיברים אליהם בוצעה גישה לאחרונה. הוא מאפשר פעולות בסיסיות כגון הכנסה, חיפוש והסרה של איברים ב[[סיבוכיות זמן]] של <math>\ O(\log n)</math> (ב[[ניתוח לשיעורין]]). עבור פעולות לא אקראיות רבות, עץ Splay מתגלה כיעיל יותר מעצי חיפוש אחרים, אפילו כאשר תבנית רצף הפעולות המסוימת אינה ידועה מראש. עץ ה-Splay הומצא על ידי [[דניאל סליטור]] ו[[רוברט טרג'אן]] ב-[[1985]].
בעץ Splay, לכל הפעולות הרגילות שניתן לבצע על עץ חיפוש בינארי מתווספת פעולה בסיסית נוספת הנקראת ''splaying''. ביצוע splaying לעץ עבור איבר מסוים פירושו ארגון מחדש של העץ כך שהאיבר ימצא בשורשו של העץ. דרך אחת לבצע זאת היא ראשית על ידי ביצוע של חיפוש בינארי רגיל של האיבר בעץ ולאחר מכן להשתמש ב[[פעולות סיבוב בעץ]], בדומה לפעולות הסיבוב המבוצעות ב[[עץ AVL]], כדי להביא את האיבר אל שורש העץ. לחלופין, אלגוריתם top- down יכול לשלב את פעולת החיפוש ופעולת הסידור לכדי שלב ביצוע אחד.
| |||