فهرست پرشی کیست؟ توضیح بده.
فهرست پرشی داده ساختاری(ساختمان داده یا Date Structure) احتمالاتی مبنی بر لیست پیوندی موازی است که در سال 1989 توسطWilliam Pugh ابداع شد .این داده ساختار می‌تواند مانند درخت دودویی جستجو، عملیات جستجو، درج و حذف را به‌طور میانگین در formula_1 انجام دهد .در واقع فهرست پرشی یک فهرست پیوندی است که هر گره (node) آن می‌تواند چند گره بعد از خودش اشاره کند که تعداد آن به صورت تصادفی مشخص می‌شود ( هر گره در یک فهرست پیوندی از دو بخش تشکیل شده است؛ یک قسمت برای نگهداری اطلاعات و قسمت دیگر مختص اشاره گرهایی به گره‌های بعدی ویا قبلی ویا هردو است .) ← به تعداد گره‌هایی که هر گره می‌تواند اشاره کند سایز گره می گوییم.شرح ساختار.در لیست‌های پیوندی معمولی هزینه جستجو، درج و حذف formula_2 است زیرا برای پیدا کردن گره دادهٔ مربوط، گره‌ها به ترتیب باید پیمایش شوند در این صورت اگر ما بتوانیم از روی بعضی گره‌ها بپریم می‌توانیم هزینه جستجو را پایین بیاوریم مثلاً به داده ساختار زیر دقت کنید :در این شبه فهرست پرشی سایز هر دو گره متوالی 2، سایز هر چهار گره متوالی 3 و سایز هر formula_3 گره متوالی formula_4 است همچنین سایز گرهٔ آغازین از همه بیشتر است .شیوه جستجو در این شبه فهرست پرشی مانند جستجوی دودویی است یعنی برای پیدا کردن داده مورد نظر ،هر بار با پایین آمدن تعداد اعداد نصف می‌شوند(ابتدا از بالاترین مرحله شروع می کنیم مثلاً اگر فهرست ما 32 گره داشته باشد، ابتدا از گره شانزدهم شروع می کنیم و هر بار با جلو رفتن یا پایین آمدن، تعداد اعداد نصف می‌شوند )؛ واضح است که هزینه جستجو در این داده ساختار از مرتبه formula_1 است دقیقاً شبیه جستجوی دودویی.شبه کد جستجو در فهرست پرشی.Comparable &amp;find(const Comparable &amp;X) node=header node; for(reference level of node from (nodesize - 1) down to 0) while(the node referred to is less than X) node = node referred to ; if(node referred to has value X) return node value; else return item_not_found;اما اگر ما بخواهیم داده‌ای را درج یا حذف کنیم چون این فهرست داده‌های مرتبی دارد، مجبور کل داده‌ها را یکبار شیفت دهیم پس هزینه درج یا حذف داده از مرتبه formula_2 است.که برای پایین آوردن زمان درج و حذف، سایز همهٔ گره‌هایمان را با توزیع یکنواخت احتمالاتی تعیین می کنیم در این صورت چون سایز گره‌ها به صورت تصادفی مشخص می‌شود، برای حذف و درج دیگر نیازی به جابجا کردن بقیه داده‌ها نداریم و فقط کافیست مکان داده مورد نظر را پیدا کنیم که آنهم از مرتبه formula_1 است :همان طور که مشاهده می‌شود توزیع سایز گره همانند شکل 1 است فقط الگو و جای قرار گرفتن گره‌ها عوض شده‌است مثلاً 50% گره‌ها سایزشان 1 است ، 25% سایز 2 دارند و ... .در هنگام درج سایز گره را با استفاده از یک تابع احتمال تعیین می کنیم :هر فهرست پرشی دارای احتمال formula_8 است که توزیع گره‌ها را مشخص می‌کند :formula_9 گره‌هایی که حداقل سایزformula_10 دارند، سایز formula_11 خواهند داشت در واقع formula_9 گره‌ها که در مرحله formula_13-ام دارای اشاره گر هستند، در مرحله formula_4-ام هم دارای اشاره گر هستند یعنی اگر formula_15 کسری از گره‌ها که دقیقاً formula_16 اشاره گر رو به جلو دارند ( سایز formula_16 دارند) باشند آنگاه : formula_18 که در نتیجه آن مثلاً بدست می‌آید که :formula_19شبه کد عملیات درج در یک فهرست پرشی.int generateNodeLevel(double P,int maxLevel) int level = 1; while(drand48()&lt;P) level++; return (level&gt;maxLevel) ? maxLevel : level;وقتی که به یک گره برای درج کردن یک داده در فهرست احتیاج داریم، سایز آن با استفاده از تابع تولید اعداد تصادفی formula_20 تعیین می‌شود در حالیکه سایز گره جدید مستقل از سایز بقیه گره‌های فهرست است و تنها به formula_21 بستگی دارد.دراین صورت میانگین مقایسه‌های لازم برای جستجوformula_22 خواهد بود که امید ریاضی آن از مرتبه formula_23 است .