Otsingupuu on andmestruktuur, mida kasutatakse arvutiprogrammeerimises andmete loendi sisaldamiseks ja korraldamiseks. Iga otsingupuu koosneb järjestatud sõlmede komplektist. Need sõlmed võivad olla ühendatud nulli või enama muuga sõlmed. Üksikud sõlmed sisaldavad nii mõningaid andmeid kui ka linke muudele sõlmedele. Puu sõlmedes sisalduvad andmed on sageli mingil viisil järjestatud, et võimaldada tõhusatel algoritmidel otsida, sõlmede lihtne sisestamine ja eemaldamine.
Otsingupuu sõlmpunkte kirjeldatakse nelja olulise terminiga Puu tippu, kus asub esimene sõlm, nimetatakse juureks Kui sõlm sisaldab linke alam -sõlmed, seda sõlme nimetatakse vanemaks. Sõlme, mis asuvad vanema all, nimetatakse lasteks ja iga sõlme, millel pole alamsõlme, nimetatakse lehtedeks. Niisiis, juursõlm tuvastatakse, kuna sellel pole vanemat ja lehesõlmedel ei ole lapsi.
Programm on võimeline liikuma läbi puu, otsides andmeid, alustades konkreetsest sõlmest, tehes tingimusliku kontrolli ja seejärel liikudes järgmisele loogilisele sõlmele, kui vajalikud andmed puuduvad. Olenevalt kasutatavast andmestruktuurist , võib see otsing võtta erineva aja. Kui otsingupuu korraldatakse sõlmede lisamise ja eemaldamise käigus, võib otsing olla väga kiire. Kui puu on kokku pandud juhuslikult, on sorteerimata või lubab mitut vanemat, võib otsing võtta väga kaua aega.
Üks tegur, mis mõjutab otsingupuude kasutamist, on tasakaalu küsimus. Tasakaalustatud puu on selline, kus juursõlme parem- ja vasakpoolsed alamsõlmed sisaldavad kas sama sügavust alamsõlme või on ühe sõlme arvu piires. Puu sügavus on sõlmede arv puu madalaimast lehest juureni. Tasakaalustamata puul võivad kõik sõlmed olla ainult ühel küljel või kõik sõlmed sõlmed on paigutatud lineaarselt ilma oksteta. Kui puu sügavus suureneb, võib otsingualgoritmide kiirus dramaatiliselt väheneda.
On teatud tüüpi otsingupuid, mida kirjeldatakse isetasakaalustavatena. Need puud kasutavad selliseid toiminguid nagu puu pööramine, et aidata säilitada tasakaalu, säilitades samal ajal lehtede andmete järjekorra. puude pööramine võib sõlmede lisamisel ja eemaldamisel programmi aeglustada, selle vastu aitab andmete toomise kiirus.
Kuigi otsingupuid on mitut tüüpi, on kõige levinum puu andmestruktuur binaarne otsingupuu. See andmetüüp koosneb sõlmedest, millest igaühel on null kuni kaks alamsõlme. Seal on ainult üks juursõlm, ja kõik puu lehed on järjestatud vasakult paremale kasvavates väärtustes vastavalt nendes sisalduvatele andmetele. Binaarsete otsingupuude jaoks on palju algoritme, mis võivad muutke andmete tellimine väga lihtsaks.
Otsingupuu sõlmede jaoks pole ühtset standardset teostust. Sõlme saab esitada mitmesuguste andmestruktuuridega. Kasutada saab massiivide massiive, nagu ka lingitud loendite korrutamist. Sageli otsingupuu kasutab kohandatud andmestruktuuri, mis on loodud aitama programmi poolt vajalike toimingute lõpuleviimisel.Mõned standardsed programmeerimisteegid sisaldavad isegi oma sisemisi otsingupuude rakendusi.