Obecný vyhledávací strom je zakořeněný strom s určeným pořadím synů každého vrcholu. Vrcholy dělíme na vnitřní a vnější, přičemž platí:
- Vnitřní (interní) vrcholy obsahují libovolný nenulový počet klíčů.
- Pokud ve vrcholu leží klíče , pak má synů, které označíme .
- Klíče slouží jako oddělovače hodnot v podstromech, čili platí: kde T(si) značí množinu všech klíčů z daného podstromu. Často se hodí dodefinovat x0 = −∞ a xk+1 = +∞, aby nerovnost xi < T(si) < xi+1 platila i pro krajní syny