מהי רשימת דילוגים?

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

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

דלג על מבנה הרשימה

הוא בנוי בשתי שכבות: השכבה הנמוכה ביותר והשכבה העליונה.

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

טבלת המורכבות של רשימת הדילוגים

עבודה של רשימת הדילוגים

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

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

נניח שאתה רוצה למצוא 47 בדוגמה זו. תתחיל את החיפוש מהצומת הראשון של הקו המהיר ותמשיך לרוץ על הקו המהיר עד שתמצא צומת השווה ל-47 או יותר מ-47.

אתה יכול לראות בדוגמה ש-47 לא קיים בקו המהיר, אז אתה מחפש צומת של פחות מ-47, שזה 40. עכשיו, אתה הולך לקו הרגיל בעזרת 40, ומחפש את ה-47, כפי שמוצג בתרשים.

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

דלג על רשימת פעולות בסיסיות

יש את סוגי הפעולות הבאים ברשימת הדילוגים.

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

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

 Insertion (L, Key) local update [0...Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] lvl = random_Level() if lvl > L → level then for i = L → level + 1 to lvl do update[i] = L → header L → level = lvl a = makeNode(lvl, Key, value) for i = 0 to level do a → forward[i] = update[i] → forward[i] update[i] → forward[i] = a 

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

 Deletion (L, Key) local update [0... Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] if a → key = Key then for i = 0 to L → level do if update[i] → forward[i] ? a then break update[i] → forward[i] = a → forward[i] free(a) while L → level > 0 and L → header → forward[L → level] = NIL do L → level = L → level - 1 

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

 Searching (L, SKey) a = L → header loop invariant: a → key level down to 0 do. while a → forward[i] → key forward[i] a = a → forward[0] if a → key = SKey then return a → value else return failure 

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

1. 6 עם רמה 1.
2. 29 עם רמה 1.
3. 22 עם רמה 4.
4. 9 עם רמה 3.
5. 17 עם רמה 1.
6. 4 עם רמה 2.

שנים:

שלב 1: הכנס 6 עם רמה 1

שלב 2: הכנס 29 עם רמה 1

שלב 3: הכנס 22 עם רמה 4

שלב 4: הכנס 9 עם רמה 3

שלב 5: הכנס 17 עם רמה 1

שלב 6: הכנס 4 עם רמה 2

דוגמה 2: שקול את הדוגמה הזו שבה אנו רוצים לחפש מפתח 17.

שנים:

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

1. אם אתה רוצה להוסיף צומת חדש ברשימת הדילוגים, אז זה יכניס את הצומת מהר מאוד מכיוון שאין סיבובים ברשימת הדילוגים.
2. רשימת הדילוגים פשוטה ליישום בהשוואה לטבלת הגיבוב ועץ החיפוש הבינארי.
3. זה מאוד פשוט למצוא צומת ברשימה מכיוון שהוא מאחסן את הצמתים בצורה ממוינת.
4. ניתן לשנות את אלגוריתם רשימת הדילוגים בקלות רבה במבנה ספציפי יותר, כגון רשימות דילוג הניתנות לאינדקס, עצים או תורי עדיפות.
5. רשימת הדילוגים היא רשימה חזקה ואמינה.

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

1. זה דורש יותר זיכרון מהעץ המאוזן.
2. חיפוש הפוך אסור.
3. רשימת הדילוגים מחפשת בצומת הרבה יותר לאט מהרשימה המקושרת.

יישומים של רשימת הדילוגים

1. הוא משמש ביישומים מבוזרים, והוא מייצג את המצביעים והמערכת ביישומים המבוזרים.
2. הוא משמש ליישום תור בו-זמני אלסטי דינמי עם מחלוקת נעילה נמוכה.
3. הוא משמש גם עם מחלקת התבנית QMap.
4. האינדקס של רשימת הדילוגים משמש בהרצת בעיות חציון.
5. רשימת הדילוג משמשת לפרסום קידוד דלתא בחיפוש Lucene.