Algorytm Sethiego-Ullmana – algorytm konwersji drzewa na taki szereg prostych instrukcji, w którym zostanie użyta minimalna liczba rejestrów (lub zmiennych tymczasowych jeśli rejestry się wyczerpią). Jest to bardzo ważne, ponieważ większość współczesnych komputerów ma relatywnie niewielką ilość rejestrów.
Jego autorami są Ravi Sethi oraz Jeffrey Ullman (stąd nazwa).
Przykład problemu Kod: x = a + (b + (c + (d + x))) można przekształcić zgodnie z zasadą „obliczaj najpierw lewą stronę” na: t1 = a t2 = b t3 = c t4 = d + x t3 = t3 + t4 t2 = t2 + t3 t1 = t1 + t2 x = t1 lub też zgodnie z zasadą „obliczaj najpierw prawą stronę” na: t1 = d + x t1 = c + t1 t1 = b + t1 t1 = a + t1 x = t1
Dla tego wyrażenia korzystniejsza jest ta druga postać.
Algorytm Algorytm Sethiego-Ullmana pozwala nam zawsze znaleźć optymalną postać. Krok pierwszy polega na obliczeniu, ile co najmniej rejestrów tymczasowych jest potrzebnych do obliczenia poddrzewa: każdy liść otrzymuje wartość 0; jeśli węzeł ma 2 podwęzły o różnych wartościach, otrzymuje wartość większego z nich; jeśli węzeł ma 2 podwęzły o takich samych wartościach, otrzymuje tę wartość plus 1.
Takie ponumerowanie da nam dla przykładowego wyrażenia: x = a + (b + (c + (d + x))) 0 0 0 0 0 [ 1 ] [ 1 ] [ 1 ] [ 1 ]