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

در علوم کامپیوتر، درخت جستجو بندانگشتی یک نوع درخت جستجوی دودویی است که یک سری اشاره‌گر به گره‌های داخلی درخت یا همان (بندانگشت) نگه می‌دارد. این اشاره‌گرها به عملیات‌های جستجو، حذف و درج برای اعضایی که نزدیک آن بندانگشت باشند، سرعت می‌یخشند به طوری که مرتبه زمانی سرشکن جستجو برابر (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 ارائه داده که احتیاجی به نگه‌داری حافظه اضافی ندارد؛ به اینگونه که به طور همزمان از تمام کاندیداهای پایین‌ترین جد مشترک گره هدف را جستجو می‌کنیم.

منابع

↑ Guibas, L.J. (1977), "A new representation for linear lists", Proceedings of the ninth annual ACM symposium on Theory of computing: ۴۹–۶۰
↑ Huddleston; Mehlhorn, Kurt (1982). "A New Data Structure for Representing Sorted Lists". Acta Informatica. 17 (2): 157–184. doi:10.1007/BF00288968. Retrieved 25 April 2014.
↑ Tsakalidis, Athanasios K. (1985). "AVL-Trees for Localized Search". Information and Control. 67: 173–194. doi:10.1016/S0019-9958(85)80034-6.
↑ Brodal, Gerth Stølting (2005). "11. Finger Search" (PDF). In Mehta, Dinesh P.; Sahni, Sartaj (eds.). Handbook of Data Structures and Applications. Chapman & Hall / انتشارات سی‌آرسی. ISBN 1-58488-435-5. Retrieved 1 January 2013.
↑ Seidel, R.; Aragon, C.R. (1996). "Randomized search trees". Algorithmica. 16 (4–5): 464–497. doi:10.1007/BF01940876.

[1] Guibas, L.J. (1977), "A new representation for linear lists", Proceedings of the ninth annual ACM symposium on Theory of computing: ۴۹–۶۰

[2] Huddleston; Mehlhorn, Kurt (1982). "A New Data Structure for Representing Sorted Lists". Acta Informatica. 17 (2): 157–184. doi:10.1007/BF00288968. Retrieved 25 April 2014.

[tsakalidis-3] Tsakalidis, Athanasios K. (1985). "AVL-Trees for Localized Search". Information and Control. 67: 173–194. doi:10.1016/S0019-9958(85)80034-6.

[brodal-4] Brodal, Gerth Stølting (2005). "11. Finger Search" (PDF). In Mehta, Dinesh P.; Sahni, Sartaj (eds.). Handbook of Data Structures and Applications. Chapman & Hall / انتشارات سی‌آرسی. ISBN 1-58488-435-5. Retrieved 1 January 2013.

[treap-5] Seidel, R.; Aragon, C.R. (1996). "Randomized search trees". Algorithmica. 16 (4–5): 464–497. doi:10.1007/BF01940876.