جستجوی درختی
From Wikipedia, the free encyclopedia
جستجوی درختی از جمله پرکاربردترین استفاده از یک درخت است. درخت یک مدل مناسب برای نمایش بسیاری از مفاهیم، پدیدهها و رابطهٔ بین آنهاست. مثلاً درخت فامیلی، سلسله مراتب اداری، عبارات ریاضی و بسیاری از بازیها با درخت مدل میشوند. در واقع درختها، گرافهای خاصی هستند که در مورد ویژگیهای آنها نتایج نظری زیادی وجود دارد.[1]
درختها بسته به نوع نیاز، تعداد برگهای مختلفی دارند. الگوریتم جستجو مختص به تعداد برگهای درخت میباشد که عبارتند از:درخت جستجوی سهتایی ،درخت جستجوی دودویی خود-متوازن ،درخت جستجوی دودویی متوازن وزندار ،درخت جستجوی تعمیمیافته، درخت جستجو بندانگشتی و... در اینجا سه نوع جستجوی رایج را در درخت دودویی و درخت با تعداد برگ نامشخص و ترای (همان درخت پیشوندی است که برای جستجوی رشتهای مناسب است) بررسی میکنیم.