است که در واقع از ترکیب دو داده ساختار و استفاده می‌کند.
 قبل از توضیح این داده ساختار اندکی در مورد ایراد جستجو و هرم توضیح می‌دهیم.
 دو نوع کلی دارد. و . برای مثال هرم بیشینه درختی می‌باشد که هر پدری حداکثر دو فرزند دارد و مقدار کلید پدر از فرزندانش بیشتر می‌باشد. این داده ساختار به راحتی با قابل پیاده‌سازی می‌باشد. مهمترین مشکل این داده ساختار جستجوی یک عضو در آن می‌باشد. زیرا آن می‌شود؛ ولی درج عنصر در این داده ساختار از می‌باشد. حذف عنصر هم به دلیل اینکه نیاز به جستجو این عنصر داریم باز خطی می‌شود.
 یه درخت دودویی است که همهٔ کلیدهای گره‌های زیردرخت چپ هر گره آن با کلید k، کوچک‌تر از k و همهٔ کلیدهای گره‌های زیر درخت راست آن بزرگتر از k باشد.
 عملیات ای شامل جستجو، درج و حذف در زمان اجرای O(h) انجام می‌دهد؛ که h همان ارتفاع درخت می‌باشد. ارتفاع درخت دودویی جستجو در حالت میانگین معادل lgn است؛ ولی ممکن است تا n هم پیش رود؛ بنابراین ضعف این داده ساختار مشخص شد. این در صورتی اتفاق می‌افتد که داده‌ها مثلاً به صورت در درخت دودویی جستجو درج بشوند. با تکنیک‌هایی مانند می‌توان کاری کرد که این درخت همواره در ارتفاع lgn بماند، ولی معمولاً پیاده‌سازی سختی دارند. به علاوه اینکه ضریت ثابت lgn در درخت قرمز و سیاه ممکن است خیلی بزرگ باشد.
 تکنیکی دیگری می‌باشد برای اینکه ارتفاع درخت دودویی جستجو را با احتمال بالایی لگاریتمی نگه داریم. پیاده‌سازی آن هم بسیار ساده می‌باشد.
 داده ساختار اولین بار در سال ۱۹۸۹ توسط سیسیلیا ر آراگون و ریموند سیدل معرفی شد.
 در هر گره آن دارای دو کلید می‌باشد. گره‌ها بر اساس یکی از این کلیدها به ترتیب درخت دودویی جستجو درج می‌شوند، بعد از درج هر گره، به کلید دوم این گره نگاه می‌کنیم؛ و این سؤال پرسیده می‌شود که آیا بر اساس مقدار کلید دوم ترتیب هرم بیشینه در این داده ساختار رعایت شده است یا نه؟ اگر کلید دوم این گره از پدرش کمتر بود که کار تمام است. یعنی درج این عنصر به پایان رسیده است؛ ولی اگه مقدار کلید دومش از همتای پدرش بیشتر بود را تا وقتی که ترتیب هرم بیشینه درست شود انجام می‌دهیم. مقدار کلید دوم هم از قبل معلوم نیست و هنگام ایجاد گره مورد نظر به صورت تصادفی مقدار دهی می‌شود و به این کلید اولویت عددی هم می‌گویند. این طوری با خیلی قوی درخت دودویی جستجو لگاریتمی می‌ماند.
 لازم به توضیح است که می‌توان ترتیب گره‌ها را بر حسب کلید اولویت عددی را بر اساس ترتیب که مقدار کلید هر گره از فرزندانش کمتر است در نظر گرفت.
 برای جستجوی کلید داده شده بدون در نظر گرفتن کلید اولویت عددی همان الگوریتم جستجوی درخت دودویی جستجو در به کار می‌بریم. توجه به این نکته لازم است که هیچ موقع جستجو بر اساس کلید اولویت انجام نمی‌شود. زیرا مقدار این کلیدها به طور تصادفی انتخاب شده و ارزشی جز در این که درخت را با احتمال خوبی لگاریتمی نگه دارند ندارند.
 برای درج کلید x در تریپ ابتدا یک اولویت تصادفی برای x تولید می‌کنیم و نامش را برای مثال y می‌گذاریم. سپس را برای کلید x به کار می‌گیریم، تا جایی را که باید این کلید درج شود پیدا شود. گره‌ای با این کلیدها می‌سازیم و در جای مربوطه درج می‌کنیم. سپس تا موقعی که این گره برابر ریشه درخت نشده و کلید اولویت کمتری (ترتیب هرم کمینه) نسبت به پدرش را دارد عمل دوران را در درخت انجام می‌دهیم.
 اگر کلید مورد نظر بود که به راحتی این گره را حذف می‌کنیم. اگر این گره فقط یک فرزند داشت فرزند این گره را به عنوان فرزند پدر این گره قرار می‌دهیم؛ و این گره را حذف می‌کنیم. اگر هم احیاناً این گره پدری نداشت فرزندش به عنوان ریشه این درخت قرار می‌گیرد؛ ولی اگر دو فرزند داشت، موقعیت این گره را با گره عنصر بعدی این گره عوض می‌کنیم. این حرکت ممکن است ترتیب هرم (کمیه یا بیشینه) را خراب کند، بنابراین احتمالاً نیاز به انجام چند عمل دوران نیز داریم تا ترتیب هرم درست بماند.
{"title": "تریپ", "link": "https://fa.wikipedia.org//w/index.php?title=%D8%AA%D8%B1%DB%8C%D9%BE&oldid=27381828", "language": "fa"}