הצגת המקור של הדף "רשימת דילוגים"

{{מבנה נתונים
|תמונה=
|תאריך המצאה=[[1989]]
|ממציא=ויליאם פְּיוּ
|קישור זיכרון=
|זיכרון ממוצע={{משמאל לימין|O(n)}}
|זיכרון במקרה הגרוע={{משמאל לימין|O(n log n)}}
|קישור חיפוש=
|חיפוש ממוצע={{משמאל לימין|O(log n)}}
|חיפוש במקרה הגרוע={{משמאל לימין|O(n)}}
|קישור הכנסה=
|הכנסה ממוצע={{משמאל לימין|O(log n)}}
|הכנסה במקרה הגרוע={{משמאל לימין|O(n)}}
|קישור הוצאה=
|הוצאה ממוצע={{משמאל לימין|O(log n)}}
|הוצאה במקרה הגרוע={{משמאל לימין|O(n)}}
}}
ב[[מדעי המחשב]], '''רשימת דילוגים (skip list)''', הוא [[מבנה נתונים]] הממיין רשימת איברים באמצעות שימוש במספר [[רשימה מקושרת|רשימות מקושרות]]. שיטה זו מאפשרת ביצוע חיפוש בצורה יעילה יחסית.

[[קובץ:Skip_list.svg|מרכז]]

== תיאור ==

רשימת דילוגים בנויה משכבות. השכבה התחתונה ביותר היא [[רשימה מקושרת]] רגילה, בה מופיעים כל האיברים במבנה הנתונים הנתון. האיברים מסודרים מהחוליה הקטנה ביותר לחוליה הגדולה ביותר. כל שכבה מוכלת בשכבה מתחתיה. ההסתברות שחוליה <math>x</math> כלשהי, השייכת לרשימה בשכבה <math>i</math>, תימצא גם ברשימה בשכבה <math>i+1</math> היא 0.5. ככלל, סיכויו של איבר כלשהו להימצא בשכבה <math>i</math> הוא <math>\frac{1}{2^i}</math>, כשהשכבה התחתונה ביותר (אשר מכילה את כל האיברים) מיוצגת על ידי <math>i=0</math>. כל איבר ברשימה מחזיק ארבעה [[מצביע|מצביעים]]: לאיבר שאחריו ברשימה, לאיבר שלפניו, לאיבר הזהה ברשימה מתחתיו ולאיבר הזהה ברשימה מעליו (אם קיים).

חיפוש אחר איבר כלשהו מתחיל מהאיבר הראשון בשכבה העליונה ביותר, וממשיך לעבור על כל איברי שכבה זו, עד שנמצא איבר גדול או שווה לאיבר שאנו מחפשים. אם איבר זה שווה ערך לאיבר שאנו מחפשים- מצאנו את יעד החיפוש. אם הגענו לאיבר גדול מהאיבר שאנו מחפשים, נחזור לאיבר הקודם, ונבצע חיפוש זהה החל מאיבר זה ברמה אחת תחתונה יותר. תהליך החיפוש צורך [[סיבוכיות זמן|זמן ריצה]] של <math>\mathcal{O}(n)</math> במקרה הגרוע ביותר, אך <math>\mathcal{O}(\log n)</math> בלבד במקרה הממוצע.

== היסטוריה ==

רשימת דילוגים הומצאה בשנת [[1989]] על ידי ויליאם פיו, פרופסור ל[[מדעי המחשב]] ב[[אוניברסיטת מרילנד]]. פיו סיפר כי ניסה למצוא תחליף ראוי ל[[עץ חיפוש |עצי חיפוש בינארים]] מאוזנים. רשימות דילוגים צורכות זמן ריצה אסימפטוטי זהה לעצים אלו, צורכות זיכרון מועט יותר, ולטענת פיו נוחות וקלות יותר לבנייה ושימוש.

== קישורים חיצוניים ==
{{ויקישיתוף בשורה}}

*[ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf רשימות מקושרות- אלטרנטיבה לעצי חיפוש מאוזנים] - המסמך המקורי מאת פרופסור ויליאם פיו. 
*[http://people.ksp.sk/~kuko/bak/index.html הדגמה מונפשת לפעולות רשימת דילוגים].

{{מבני נתונים}}
[[קטגוריה:מבני נתונים]]