Slajd 13 z 17

Drzewo Patricia to struktura danych ulepszona w stosunku do drzewa Trie. Kompresujemy ścieżki w drzewie, czyli usuwamy wierzchołki z dokładnie jednym synem, zapamiętując odpowiedni ciąg bitów prowadzący po ścieżce.

Dla dużej przestrzeni adresowej (np. 2^64), drzewo Trie jest rzadkie, bo jest dużo więcej kluczy (adresów logicznych) niż wartości (ramek). Zatem często pojawia się okazja do kompresji ścieżek. Średnia głębość drzewa maleje - zależy w przybliżeniu logarytmicznie od ilości przydzielonej pamięci (stopień każdego wierzchołka wewnętrznego wynosi co najmniej 2).