Ten artykuł od 2025-12 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Google Books • Google Scholar • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Substitution tree – metoda indeksowania termów polegająca na trzymaniu w każdym termie podstawienia, które należy wykonać na węźle rodzicu żeby uzyskać dany term.

W substitution tree inaczej traktowane są zmienne zewnętrzne (czyli po prostu pewne symbole) oraz zmienne wewnętrzne (służące wyłącznie do opisywania części wspólnych drzew).

Przykład dla ${\displaystyle g(b),}$ ${\displaystyle f(a,g(b))}$ i ${\displaystyle f(b,g(b)){:}}$

${\displaystyle x}$ i ${\displaystyle y}$ są tu zmiennymi wewnętrznymi.

W substitution tree ma miejsce o wiele więcej współdzielenia niż w drzewie dyskryminacyjnym, jest więc ono pamięciowo o wiele bardziej wydajne. Wciąż jednak ${\displaystyle g(b)}$ jest dzielone jedynie pomiędzy niektórymi wystąpieniami.