داده ساختار تیریپ

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

داده ساختار تیریپ داده ساختاری است که در واقع از ترکیب دو داده ساختار درخت دودویی جستجو و هرم استفاده می کند.

قبل از توضیح این داده ساختار اندکی در مورد ایراد درخت دودویی جستجو و هرم توضیح می دهیم.

هرم[ویرایش]

هرم دو نوع کلی دارد. هرم بیشینه و هرم کمینه. برای مثال هرم بیشینه درختی می‌باشد که هر پدری حداکثر دو فرزند دارد و مقدار کلید پدر از فرزندانش بیشتر می باشد. این داده ساختار به راحتی با آرایه قابل پیاده سازی می باشد. مهمترین مشکل این داده ساختار جستجوی یک عضو در آن می باشد. زیرا زمان اجرای آن خطی می شود. ولی درج عنصر در این داده ساختار از O(lgn) می باشد. حذف عنصر هم به دلیل اینکه نیاز به جستجو این عنصر داریم باز خطی می شود.

درخت دودویی جستجو[ویرایش]

درخت دودویی جستجو یه درخت دودویی است که همهٔ کلیدهای گره‌های زیردرخت چپ هر گره آن با کلید k، کوچک تر از k و همهٔ کلیدهای گره‌های زیر درخت راست آن بزرگتر از k باشد.

تحلیل[ویرایش]

عملیات فرهنگ داده ای شامل جستجو، درج و حذف در زمان اجرای O(h) انجام می دهد. که h همان ارتفاع درخت می باشد. ارتفاع درخت دودویی جستجو در حالت میانگین معادل lgn است. ولی ممکن است تا n هم پیش رود. بنابراین ضعف این داده ساختار مشخص شد. این در صورتی اتفاق می افتد که داده‌ها مثلاً به صورت مرتب شده در درخت دودویی جستجو درج بشوند. با تکنیک هایی مانند درخت قرمز و سیاه می توان کاری کرد که این درخت همواره در ارتفاع lgn بماند، ولی معمولاً پیاده سازی سختی دارند. به علاوه اینکه ضریت ثابت lgn در درخت قرمز و سیاه ممکن است خیلی بزرگ باشد.

تیریپ[ویرایش]

در این شکل حروف الفبای انگلیسی کلیدهای اصلی هستن و عددها همان کلید اولویت می باشند.

تیریپ تکنیکی دیگری می‌باشد برای اینکه ارتفاع درخت دودویی جستجو را با احتمال بالایی لگاریتمی نگه داریم. پیاده سازی آن هم بسیار ساده می باشد.

تاریخ چه[ویرایش]

داده ساختار تیریپ اولین بار در سال 1989 توسط سیسیلیا ر آراگون و ریموند سیدل معرفی شد.

پیاده سازی[ویرایش]

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

لازم به توضیح است که می توان ترتیب گره‌ها را بر حسب کلید اولویت عددی را بر اساس ترتیب هرم کمینه که مقدار کلید هر گره از فرزندانش کمتر است در نظر گرفت.

در شکل زیر نحوه درج گره‌ها را در این داده ساختار مشاهده می کنید:

در این شکل حروف الفبای انگلیسی کلیدهای اصلی هستن و عددها همان کلید اولویت می باشند.

عملیات خاص[ویرایش]

جستجو[ویرایش]

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

درج[ویرایش]

برای درج کلید x در تیریپ ابتدا یک اولویت تصادفی برای x تولید می کنیم و نامش را برای مثال y می گذاریم. سپس الگوریتم جستجو را برای کلید x به کار می گیریم، تا جایی را که باید این کلید درج شود پیدا شود. گره ای با این کلیدها می سازیم و در جای مربوطه درج می کنیم. سپس تا موقعی که این گره برابر ریشه درخت نشده و کلید اولویت کمتری (ترتیب هرم کمینه) نسبت به پدرش را دارد عمل دوران را در درخت انجام می دهیم.

حذف[ویرایش]

اگر کلید مورد نظر برگ بود که به راحتی این گره را حذف می کنیم. اگر این گره فقط یک فرزند داشت فرزند این گره را به عنوان فرزند پدر این گره قرار می دهیم. و این گره را حذف می کنیم. اگر هم احیاناً این گره پدری نداشت فرزندش به عنوان ریشه این درخت قرار می گیرد. ولی اگر دو فرزند داشت، موقعیت این گره را با گره عنصر بعدی این گره عوض می کنیم. این حرکت ممکن است ترتیب هرم (کمیه یا بیشینه) را خراب کند، بنابراین احتمالاً نیاز به انجام چند عمل دوران نیز داریم تا ترتیب هرم درست بماند.

جستارهای وابسته[ویرایش]

منابع[ویرایش]