درخت جستجوی بندانگشتی

در علوم کامپیوتر، درخت جستجو بندانگشتی یک نوع درخت جستجوی دودویی است که یک سری اشاره گر به گره های داخلی درخت یا همان ( بندانگشت ) نگه می دارد. این اشاره گرها به عملیات های جستجو، حذف و درج برای اعضایی که نزدیک آن بندانگشت باشند، سرعت می یخشند به طوری که مرتبه زمانی سرشکن جستجو برابر ( O ( log n و برای حذف و درج نیز ( باز هم به طور سرشکن ) ( O ( 1 طول می کشد. این داده ساختار را با درخت انگشتی یا درخت اسپلی اشتباه نگیرید. هر دوی این داده ساختارها می توانند برای پیاده سازی درخت جستجوی بنداگشتی استفاده شوند. گیباس ( به انگلیسی: Guibas et al ) . [ ۱] درخت جستجو بندانگشتی را براساس درخت - بی ساخت. نسخه اصلی این داده ساختار، عملیات جستجو را ( اگر d را تعداد گره های بین گره هدف و بندانگشت بگیریم ) در زمان ( O ( log d تضمین می کند. عملیات به روز رسانی وقتی فقط ( O ( 1 بندانگشت قابل جابجایی را نگه داریم، ( O ( 1 زمان می گیرد و p خانه جابجا کردن یک بندانگشت، زمان ( O ( log p می گیرد. هادلستون ( Huddleston ) و ملهورن ( Mehlhorn ) این داده ساختار را بهبود داده و درخت - بی - پیوند - مرحله ای را ساختند. [ ۲] ساکالیدیس ( Tsakalidis ) یک نسخه دیگر براساس درخت AVL پیشنهاد داد که جستجو از انتهای درخت را ساده تر می کند. این روش، امکان پیاده سازی یک داده ساختار با چند بندانگشت را با استفاده از چند تا از همین درخت ها می دهد. [ ۳] برای انجام یک جستجوی بندانگشتی در یک درخت دودویی در حالت ایده آل، از یک بندانگشت شروع می کنیم و به سمت ریشه ( بالا ) می رویم تا به گره برگشت[ ۳] یا به پایین ترین جد مشترک[ ۴] [ ۵] این دو گره برسیم؛ و سپس پایین برویم تا عضوی که دنبالش می گردیم را پیدا کنیم. اما تعیین این که یک گره جد گره دیگری هست یا نه، بدیهی نیست.
تیریپ یک داده ساختار تصادفی ( به انگلیسی: randomized ) است که توسط آراگون و سیدل ( به انگلیسی: Seidel and Aragon ) معرفی شد. [ ۵] در این داده ساختار امید ریاضی طول مسیر دو گره با فاصله d برابر ( O ( log d است. این دو نفر برای انجام جستجو بندانگشتی در تیریپ برای این که بتوانیم پایین ترین جد مشترک را سریع تر پیدا کنیم، پیشنهاد کردند که یا یک سری اشاره نگه داریم یا برای هر گره نگه داریم که حداقل و حداکثر گره های زیر درخت شان چیست.
یک فصل از کتابی که در منابع آمده، به درخت جستجو بندانگشتی اختصاص دارد. [ ۴] در این کتاب نویسنده، الگوریتمی برای جستجو دودویی در تیریپ با اردر زمانی ( O ( log d ارائه داده که احتیاجی به نگه داری حافظه اضافی ندارد؛ به اینگونه که به طور همزمان از تمام کاندیداهای پایین ترین جد مشترک گره هدف را جستجو می کنیم.