Drzewo RST

Z Wikipedii, wolnej encyklopedii

Drzewo RST – drzewo poszukiwań pozycyjnych. Rozgałęzienia są dokonywane nie przez wartości elementów (drzewo BST, AVL), ale na podstawie wartości kolejnego bitu wyszukiwanego słowa v. Na pierwszym poziomie drzewa decydujące znaczenie ma pierwszy bit vmaxh, tzn. elementy ze zbioru S z bitem 0 na pierwszej pozycji trafią do lewego poddrzewa, a elementy z bitem 1 do prawego. Na drugim poziomie decydujące znaczenie ma drugi bit, itd.