فهرست پرشی

در لیست‌های پیوندی معمولی هزینه جستجو، درج و حذف ${\displaystyle \mathrm{O}(n)}$

در این شبه فهرست پرشی سایز هر دو گره متوالی 2، سایز هر چهار گره متوالی 3 و سایز هر ${\displaystyle 2^i}$

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

اما اگر ما بخواهیم داده‌ای را درج یا حذف کنیم چون این فهرست داده‌های مرتبی دارد، مجبور کل داده‌ها را یکبار شیفت دهیم پس هزینه درج یا حذف داده از مرتبه ${\displaystyle \mathrm{O}(n)}$

همان طور که مشاهده می‌شود توزیع سایز گره همانند شکل 1 است فقط الگو و جای قرار گرفتن گره‌ها عوض شده‌است مثلاً 50% گره‌ها سایزشان 1 است ، 25% سایز 2 دارند و ... . در هنگام درج سایز گره را با استفاده از یک تابع احتمال تعیین می کنیم : هر فهرست پرشی دارای احتمال ${\displaystyle \mathrm{P}}$

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

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

دراین صورت میانگین مقایسه‌های لازم برای جستجو ${\displaystyle 1+\frac{{\log }_{\frac{1}{P}}n}{P}+\frac{1}{1-P}}$

• لیست پیوندی
• ساختمان داده
• الگوریتم‌های تصادفی