تریپ

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