Paieškos medis yra duomenų struktūra, naudojama kompiuterių programavime, kad būtų galima laikyti ir tvarkyti duomenų sąrašą. Kiekvieną paieškos medį sudaro tvarkingas mazgų rinkinys. Šie mazgai gali būti prijungti prie nulio ar daugiau kitų mazgai. Atskiruose mazguose yra tam tikri duomenys, taip pat nuorodos į kitus mazgus. Duomenys, esantys medžio mazguose, labai dažnai yra tam tikru būdu sutvarkyti, kad būtų galima efektyviai ieškoti, lengvai įdėkite ir pašalinkite mazgus.
Paieškos medžio mazgai apibūdinami keturiais svarbiais terminais. Medžio viršūnė, kurioje yra pirmasis mazgas, vadinama šaknimis. Jei mazge yra nuorodų į sub. -mazgai, tas mazgas žinomas kaip pirminis. Mazgai, esantys po pirminiu, vadinami vaikais, o bet kuris mazgas, kuriame nėra antrinių mazgų, vadinamas lapeliu. Taigi, šakninis mazgas identifikuojamas, nes jis neturi pirminio, o lapų mazgai neturės antrinių.
Programa gali pereiti per medį, ieškodama duomenų, pradėdama nuo konkretaus mazgo, atlikdama sąlyginį patikrinimą ir tada pereidama prie kito loginio mazgo, jei reikiamų duomenų nėra. Priklausomai nuo naudojamos duomenų struktūros. , ši paieška gali užtrukti skirtingą laiką. Jei paieškos medis organizuojamas mazgų pridėjimo ir pašalinimo proceso metu, paieška gali būti labai greita. Kai medis surenkamas atsitiktinai, yra nerūšiuojama arba leidžia keli tėvai, paieška gali užtrukti labai ilgai.
Vienas veiksnys, turintis įtakos paieškos medžių naudojimui, yra pusiausvyros problema. Subalansuotas medis yra toks, kuriame tiek dešinėje, tiek kairėje šaknies mazgo antriniai mazgai turi tą patį gylį arba yra vieno mazgo ribose. vienas nuo kito. Medžio gylis – tai mazgų skaičius nuo žemiausio medžio lapo iki šaknies. Nesubalansuotas medis gali turėti visus mazgus tik vienoje pusėje arba turėti visus mazgai išdėstyti tiesiškai be šakų. Didėjant medžio gyliui, paieškos algoritmų greitis gali smarkiai sumažėti.
Yra tam tikrų tipų paieškos medžiai, kurie apibūdinami kaip savaime balansuojantys. Šie medžiai naudoja tokias operacijas kaip medžių sukimas, kad padėtų išlaikyti pusiausvyrą, išsaugant duomenų tvarką lapuose. Nors jie atlieka medžių sukimas gali sulėtinti programos veikimą, kai pridedami ir pašalinami mazgai, o tai atsveria duomenų gavimo greitis.
Nors yra daugybė paieškos medžių tipų, labiausiai paplitusi medžio duomenų struktūra yra dvejetainis paieškos medis. Šį duomenų tipą sudaro mazgai, kurių kiekvienas turi nuo nulio iki dviejų antrinių mazgų. Yra tik vienas šakninis mazgas, ir visi medžio lapai yra išdėstyti iš kairės į dešinę didėjančiomis reikšmėmis pagal juose turimus duomenis. Yra daug dvejetainių paieškos medžių algoritmų, kurie gali kad duomenų užsakymas būtų labai paprastas.
Nėra vieno standartinio paieškos medžio mazgų diegimo. Mazgai gali būti pavaizduoti įvairiomis duomenų struktūromis. Galima naudoti masyvų masyvus, taip pat dauginti susietus sąrašus. Dažnai paieškos medis naudoja tinkintą duomenų struktūrą, kuri yra skirta padėti atlikti būtinas programos reikalaujamas operacijas. Kai kurios standartinės programavimo bibliotekos netgi apima savo vidinius paieškos medžių diegimus.