مرتب‌سازی انفجاری

جستجو

جستجو در یک درخت پیشوندی انفجاری از دو گام مجزای زیر تشکیل شده‌است. ورودی این عملیات یک رشته  حرفی  و خروجی اشاره‌گری به یک رکورد یا در صورت جستجوی ناموفق اشاره‌گری به نال است.
- گام اول:
درخت پیشوندی دسترسی با توجه به حروف ابتدایی رشته مورد جستجو قرار گرفته طی می‌شود. شیء فعلی در مرحله اول برابر با ریشه درخت پیشوندی دسترسی و ارتفاع فعلی هم برابر با یک است. تا زمانی که شیء فعلی یکی از گره‌های درخت پیشوندی دسترسی است و ارتفاع  کمتر از  است:
الف) شیء فعلی را برابر با گره یا ظرف اشاره شده توسط  امین عنصر آرایه  قرار داده می‌شود،
ب)  یکی زیاد می‌شود.
اگر شیء فعلی گره درخت پیشوندی با ارتفاع  بود، شیء فعلی برابر با شیء اشاره شده توسط اشاره‌گر تهی (که برای سادگی می‌تواند یک ظرف حاوی صفر یا یک رکورد در نظر گرفته‌شود) قرار داده می‌شود. در غیر اینصورت، اگر شیء فعلی نال بود این رشته در درخت پیشوندی انفجاری وجود ندارد و جستجو خاتمه می‌یابد.
- گام دوم:
شیء فعلی یک ظرف معتبر است. اگر ، از حروف باقی مانده  جهت جستجو در ظرف استفاده می‌شود که در صورت پیدا شدن رکورد مربوطه، آن رکورد و در غیر اینصورت نال برگردانده می‌شود؛ وگرنه شیء فعلی برابر با یک ظرف حاوی صفر یا یک رکورد است که توسط یک اشاره‌گر تهی در دسترس قرار گرفته‌است. در انتها چون تمامی رشته در پیمایش درخت پیشوندی مورد استفاده قرار گرفته‌است، این اشاره‌گر برگردانده می‌شود.

مثال

برای مثال، جهت جستجوی عبارت "came" در درخت پیشوندی شکل زیر، ابتدا اشاره‌گر را از خانه 'C' گره ریشه تا گره بعدی درخت پیشوندی دنبال می‌کنیم. سپس از خانه 'A' به چپ‌ترین ظرف آن می‌رویم و در آنجا به دنبال زیررشته "me" می‌گردیم. ظرف‌های ما به شکل داده ساختار درخت دودویی جستجو هستند؛ بنابراین در این مرحله از الگوریتم جستجوی یک رشته در یک درخت دودویی جستجو استفاده می‌کنیم.

درج

با فرض اینکه قصد داریم یک رشته  حرفی  را در درخت پیشوندی انفجاری درج کنیم، دو گام باید پیموده شود:
- گام اول:
ابتدا باید ظرفی (با ارتفاع ) که رکورد باید در آن درج شود را پیدا کنیم. اگر  بود، ظرف مورد نظر زیر اشاره‌گر تهی قرار گرفته‌است.
- گام دوم:
در غیر اینصورت اگر  بود، از الگوریتم معمول درج در داده ساختار ظرفمان (که برای مثال می‌تواند درخت دودویی جستجو باشد) جهت درج رکورد مربوطه استفاده می‌کنیم. این کار را با استفاده از حروف  رشته انجام می‌دهیم.

حذف

عملیات حذف در این داده ساختار کمی پیچیده‌تر از سایر عملیات است. برای حذف یک رکورد، ابتدا باید آن را جستجو کنیم، بیابیم و با استفاده از روش معمول حذف در داده ساختار ظرفمان آن را از ظرف حذف کنیم. اگر حذف باعث خالی شدن یک ظرف شود، گره‌ای که پدر آن ظرف است باید به‌روزرسانی شود. در صورتی که گره هیچ بچه‌ای نداشته باشد، از درخت پیشوندی انفجاری حذف می‌شود و این عملیات می‌تواند به‌طور بازگشتی تا ریشه ادامه پیدا کند.

انفجار

به فرایند جایگزینی یک ظرف در عمق  با یک گره از درخت پیشوندی و مجموعه‌ای از ظرف‌های جدید در عمق  (که تمامی رکوردهای موجود در ظرف اصلی بین آن‌ها نگهداری می‌شود) انفجار گفته می‌شود. یک استراتژی موفق انفجار باید سریع پیدا شدن رشته‌های معمول بدون جستجوی اضافه در ظرف‌ها را تضمین کند. مدیریت مناسب ظرف‌ها می‌تواند در کاهش هزینه جستجو مؤثر واقع شود. باید توجه داشت که ظرف‌هایی که به ندرت در دسترس قرار می‌گیرند نباید منفجر شوند، زیرا ظرف‌ها باید در قیاس با گره‌ها از فضای موجود بهره بیشتری ببرند. انفجار با پیمودن سه گام زیر انجام می‌شود:
- گام اول:
یک گره جدید در درخت پیشوندی دسترسی با نام  ایجاد می‌شود و تمام اشاره‌گرهای آن به یک ظرف خالی اشاره می‌کنند.
- گام دوم:
برای هر رکورد  در ظرف اصلی،
الف) حرف اول آن رشته () برداشته می‌شود، و
ب) این رکورد به ظرفی که پوینتر  گره b به آن اشاره می‌کند، اضافه می‌شود. در صورتی که رکورد یک رشته خالی بود، زیر اشاره‌گر تهی  افزوده می‌شود.
- گام سوم:
ظرف اصلی دور انداخته می‌شود.