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