تریپ

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

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

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

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

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

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

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

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

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

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

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

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

• درخت دودویی جستجو
• هرم
• درخت قرمز و سیاه

• محمد قدسی (۱۳۸۸)، «۴ و ۷»، داده ساختارها و مبانی الگوریتم‌ها، موسسه فرهنگی فاطمی، شابک ۹۷۸-۹۶۴-۳۱۸-۵۴۹-۷
• http://en.wikipedia.org/wiki/Treap
• http://en.wikipedia.org/wiki/Tree_rotation
• http://www.perlmonks.org/?node_id=289584
• http://babbage.clarku.edu/~achou/cs160fall03/examples/bst_animation/Treap-Example.html^{[پیوند مرده]}