فهرست پرشی

فهرست پرشی داده ساختاری(ساختمان داده یا Date Structure) احتمالاتی مبنی بر لیست پیوندی موازی است که در سال 1989 توسط William Pugh ابداع شد . این داده ساختار می‌تواند مانند درخت دودویی جستجو، عملیات جستجو، درج و حذف را به‌طور میانگین در $\operatorname {O} (\log n)$ انجام دهد . در واقع فهرست پرشی یک فهرست پیوندی است که هر گره (node) آن می‌تواند چند گره بعد از خودش اشاره کند که تعداد آن به صورت تصادفی مشخص می‌شود ( هر گره در یک فهرست پیوندی از دو بخش تشکیل شده است؛ یک قسمت برای نگهداری اطلاعات و قسمت دیگر مختص اشاره گرهایی به گره‌های بعدی ویا قبلی ویا هردو است .) ← به تعداد گره‌هایی که هر گره می‌تواند اشاره کند سایز گره می گوییم.

شرح ساختار

در لیست‌های پیوندی معمولی هزینه جستجو، درج و حذف $\operatorname {O} (n)$ است زیرا برای پیدا کردن گره دادهٔ مربوط، گره‌ها به ترتیب باید پیمایش شوند در این صورت اگر ما بتوانیم از روی بعضی گره‌ها بپریم می‌توانیم هزینه جستجو را پایین بیاوریم مثلاً به داده ساختار زیر دقت کنید :

شکل 1 : یک فهرست پرشی با جهش در $2^{i}$ -امین گره

در این شبه فهرست پرشی سایز هر دو گره متوالی 2، سایز هر چهار گره متوالی 3 و سایز هر $2^{i}$ گره متوالی $i+1$ است همچنین سایز گرهٔ آغازین از همه بیشتر است . شیوه جستجو در این شبه فهرست پرشی مانند جستجوی دودویی است یعنی برای پیدا کردن داده مورد نظر ، هر بار با پایین آمدن تعداد اعداد نصف می‌شوند(ابتدا از بالاترین مرحله شروع می کنیم مثلاً اگر فهرست ما 32 گره داشته باشد، ابتدا از گره شانزدهم شروع می کنیم و هر بار با جلو رفتن یا پایین آمدن، تعداد اعداد نصف می‌شوند )؛ واضح است که هزینه جستجو در این داده ساختار از مرتبه $\operatorname {O} (\log n)$ است دقیقاً شبیه جستجوی دودویی.

شبه کد جستجو در فهرست پرشی

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;
}

اما اگر ما بخواهیم داده‌ای را درج یا حذف کنیم چون این فهرست داده‌های مرتبی دارد، مجبور کل داده‌ها را یکبار شیفت دهیم پس هزینه درج یا حذف داده از مرتبه $\operatorname {O} (n)$ است. که برای پایین آوردن زمان درج و حذف، سایز همهٔ گره‌هایمان را با توزیع یکنواخت احتمالاتی تعیین می کنیم در این صورت چون سایز گره‌ها به صورت تصادفی مشخص می‌شود، برای حذف و درج دیگر نیازی به جابجا کردن بقیه داده‌ها نداریم و فقط کافیست مکان داده مورد نظر را پیدا کنیم که آنهم از مرتبه $\operatorname {O} (\log n)$ است :

همان طور که مشاهده می‌شود توزیع سایز گره همانند شکل 1 است فقط الگو و جای قرار گرفتن گره‌ها عوض شده‌است مثلاً 50% گره‌ها سایزشان 1 است ، 25% سایز 2 دارند و ... . در هنگام درج سایز گره را با استفاده از یک تابع احتمال تعیین می کنیم : هر فهرست پرشی دارای احتمال $\operatorname {P}$ است که توزیع گره‌ها را مشخص می‌کند : $\operatorname {} {\frac {1}{P}}$ گره‌هایی که حداقل سایز $\operatorname {r}$ دارند، سایز $\operatorname {} r+1$ خواهند داشت در واقع $\operatorname {} {\frac {1}{P}}$ گره‌ها که در مرحله $i$ -ام دارای اشاره گر هستند، در مرحله $i+1$ -ام هم دارای اشاره گر هستند یعنی اگر $\operatorname {} L_{k}$ کسری از گره‌ها که دقیقاً $k$ اشاره گر رو به جلو دارند ( سایز $k$ دارند) باشند آنگاه : $\operatorname {} L_{k}=PL_{k-1}$ که در نتیجه آن مثلاً بدست می‌آید که : $\operatorname {} L_{1}=1-P$

شبه کد عملیات درج در یک فهرست پرشی

int generateNodeLevel(double P,int maxLevel)
{
  int level = 1;
  while(drand48()<P)
    level++;
  return (level>maxLevel) ? maxLevel : level;
}

وقتی که به یک گره برای درج کردن یک داده در فهرست احتیاج داریم، سایز آن با استفاده از تابع تولید اعداد تصادفی $r$ تعیین می‌شود در حالیکه سایز گره جدید مستقل از سایز بقیه گره‌های فهرست است و تنها به $\operatorname {} P$ بستگی دارد.

دراین صورت میانگین مقایسه‌های لازم برای جستجو $\operatorname {} 1+{\frac {\log _{\frac {1}{P}}n}{P}}+{\frac {1}{1-P}}$ خواهد بود که امید ریاضی آن از مرتبه $\operatorname {O} (\log n)$ است .

جستارهای وابسته

پیوند به بیرون

SkipList Applet
Thomas Wenger's demo applet on skiplists
Prof. Erik Demaine's lecture on skip lists from MIT's OpenCourseWare program. (Audio)

منابع