Stablo pretraživanja je struktura podataka koja se koristi u računalnom programiranju za sadržavanje i organiziranje popisa podataka. Svako stablo pretraživanja sastoji se od uređenog skupa čvorova. Ovi čvorovi se mogu povezati s nula ili više drugih čvorovi. Pojedinačni čvorovi sadrže neke podatke kao i veze s bilo kojim drugim čvorovima. Podaci koji se nalaze u čvorovima stabla vrlo su često poredani na neki način kako bi se omogućilo učinkovitim algoritmima da traže, umetanje i uklanjanje čvorova s lakoćom.
Čvorovi stabla pretraživanja opisani su s četiri važna pojma. Vrh stabla, gdje se nalazi prvi čvor, naziva se korijen. Ako čvor sadrži veze na pod -čvorovi, taj čvor je poznat kao roditelj. Čvorovi koji se nalaze ispod nadređenog nazivaju se djeca, a svaki čvor koji nema podređene čvorove naziva se list. Dakle, korijenski čvor je identificiran jer nema roditelja, a lisni čvorovi neće imati djece.
Program se može kretati kroz stablo tražeći podatke počevši od određenog čvora, izvodeći uvjetnu provjeru i zatim prijeći na sljedeći logički čvor ako traženi podaci nisu prisutni. Ovisno o korištenoj strukturi podataka , ovo pretraživanje može potrajati različito vrijeme. Ako je stablo pretraživanja organizirano tijekom procesa dodavanja i uklanjanja čvorova, pretraga može biti vrlo brza. Kada je stablo sastavljeno nasumično, nije sortirano ili dopušta više roditelja, pretraga može potrajati jako dugo.
Jedan čimbenik koji utječe na korištenje stabala pretraživanja je pitanje ravnoteže. Balansirano stablo je ono u kojem i desna i lijeva djeca korijenskog čvora sadrže ili istu dubinu podređenih čvorova ili su unutar broja jednog čvora jedni od drugih. Dubina stabla je broj čvorova od najnižeg lista stabla do korijena. Neuravnoteženo stablo može imati sve čvorove samo na jednoj strani ili imati sve čvorovi poredani na linearni način bez grana.Kada se dubina stabla povećava, brzina algoritama pretraživanja može se dramatično smanjiti.
Postoje određene vrste stabala pretraživanja koja se opisuju kao samobalansirajuća. Ova stabla koriste operacije kao što je rotacija stabala kako bi pomogla u održavanju ravnoteže uz očuvanje redoslijeda podataka u listovima. Iako izvode rotacije stabala mogu usporiti program prilikom dodavanja i uklanjanja čvorova, čemu se suprotstavlja brzina kojom se podaci mogu dohvatiti.
Iako postoji mnogo vrsta stabala pretraživanja, najčešća struktura podataka stabla je binarno stablo pretraživanja. Ova vrsta podataka sastoji se od čvorova od kojih svaki ima nula do dva podređena čvora. Postoji samo jedan korijenski čvor, a svi listovi u stablu poredani su s lijeva na desno u rastućim vrijednostima prema podacima koje posjeduju. Postoje mnogi algoritmi za stabla binarnog pretraživanja koji mogu učinite naručivanje podataka vrlo jednostavnim.
Ne postoji jedinstvena standardna implementacija za čvorove stabla pretraživanja. Čvorovi se mogu predstaviti širokim rasponom struktura podataka. Mogu se koristiti nizovi nizova, kao i množenje povezanih popisa. Često, stablo pretraživanja koristi prilagođenu strukturu podataka koja je dizajnirana da pomogne u dovršenju potrebnih operacija koje zahtijeva program.Neke standardne programske knjižnice čak uključuju vlastite interne implementacije stabala pretraživanja.