فهرست پرشی

فهرست پرشی داده ساختاری(ساختمان داده یا ) احتمالاتی مبنی بر فهرست پیوندی موازی است که در سال 1989 توسط
ابداع شد .
این داده ساختار می‌تواند مانند درخت دودویی جستجو، عملیات جستجو، درج و حذف را بطور میانگین در انجام دهد .
در واقع فهرست پرشی یک فهرست پیوندی است که هر گره (node) آن می‌تواند چند گره بعد از خودش اشاره کند که تعداد آن به صورت تصادفی مشخص می‌شود ( هر گره در یک فهرست پیوندی از دو بخش تشکیل شده است؛ یک قسمت برای نگهداری اطلاعات و قسمت دیگر مختص اشاره گرهایی به گره‌های بعدی ویا قبلی ویا هردو است .) ← به تعداد گره‌هایی که هر گره می‌تواند اشاره کند سایز گوه می‌گوییم .
شرح ساختار
در فهرست‌های پیوندی معمولی هزینه جستجو، درج و حذف است زیرا برای پیدا کردن گره داده مربوطه، گره‌ها به ترتیب باید پیمایش شوند در این صورت اگر ما بتوانیم از روی بعضی گره‌ها بپریم می‌توانیم هزینه جستجو را پایین بیاوریم مثلا به داده ساختار زیر دقت کنید :
شکل 1 : یک فهرست پرشی با جهش در -امین گره
در این شبه فهرست پرشی سایز هر دو گره متوالی 2، سایز هر چهار گره متوالی 3 و سایز هر گره متوالی است همچنین سایز گره آغازین از همه بیشتر است .
شیوه جستجو در این شبه فهرست پرشی مانند جستجوی دودویی است یعنی برای پیدا کردن داده مورد نظر ،
هر بار با پایین آمدن تعداد اعداد نصف می‌شوند(ابتدا از بالاترین مرحله شروع می‌کنیم مثلا اگر فهرست ما 32 گره داشته باشد، ابتدا از گره شانزدهم شروع می‌کنیم و هر بار با جلو رفتن یا پایین آمدن، تعداد اعداد نصف می‌شوند )؛ واضح است که هزینه جستجو در این داده ساختار از مرتبه است دقیقا شبیه جستجوی دودویی.
شبه کد جستجو در فهرست پرشی
Comparable -find(const Comparable -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;
اما اگر ما بخواهیم داده‌ای را درج یا حذف کنیم چون این فهرست داده‌های مرتبی دارد، مجبور کل داده‌ها را یکبار شیفت دهیم پس هزینه درج یا حذف داده از مرتبه است.
که برای پایین آوردن زمان درج و حذف، سایز همه گره‌هایمان را با توزیع یکنواخت احتمالاتی تعیین می‌کنیم در این صورت چون سایز گره‌ها به صورت تصادفی مشخص می‌شود، برای حذف و درج دیگر نیازی به جابجا کردن بقیه داده‌ها نداریم و فقط کافیست مکان داده مورد نظر را پیدا کنیم که آنهم از مرتبه است :
شکل 2 : یک فهرست پرشی احتمالاتی
همان طور که مشاهده می‌شود توزیع سایز گره همانند شکل 1 است فقط الگو و جای قرار گرفتن گره‌ها عوض شده‌است مثلا 50% گره‌ها سایزشان 1 است ، 25% سایز 2 دارند و … .
در هنگام درج سایز گره را با استفاده از یک تابع احتمال تعیین می‌کنیم :
هر فهرست پرشی دارای احتمال است که توزیع گره‌ها را مشخص می‌کند :
گره‌هایی که حداقل سایز دارند، سایز خواهند داشت در واقع گره‌ها که در مرحله -ام دارای اشاره گر هستند، در مرحله -ام هم دارای اشاره گر هستند یعنی اگر کسری از گره‌ها که دقیقا اشاره گر رو به جلو دارند ( سایز دارند) باشند آنگاه : که در نتیجه آن مثلا بدست می‌آید که :
شبه کد عملیات درج در یک فهرست پرشی
int generateNodeLevel(double P,int maxLevel)
int level = 1;
while(drand48() maxLevel) ? maxLevel : level;
وقتی که به یک گره برای درج کردن یک داده در فهرست احتیاج داریم، سایز آن با استفاده از تابع تولید اعداد تصادفی تعیین می‌شود در حالیکه سایز گره جدید مستقل از سایز بقیه گره‌های فهرست است و تنها به بستگی دارد.
دراین صورت میانگین مقایسه‌های لازم برای جستجو
خواهد بود که امید ریاضی آن از مرتبه است .
فهرست پیوندی
ساختمان داده
الگوریتم‌های تصادفی
from MITs OpenCourseWare program. (Audio)