Co je to Quad Tree?

Quad strom, někdy quadtree, Q-strom nebo QT, je termín informatiky, který odkazuje na metodu organizace dat ve čtyřech kvadrantech. Databáze někdy používají kvadratické stromy k uložení a nalezení svých záznamů. Tento typ organizační struktury funguje obzvláště dobře k nalezení konkrétního kousku nebo pixelu v dvourozměrném obrázku.

Quad strom poněkud sleduje strukturu stromových dat běžně používanou v informatice. Normální struktura dat stromu vypadá jako strom vzhůru nohama, kde nadřazený uzel v horní části stromu má k němu připojen jeden nebo více podřízených uzlů. Každý další uzel ve stromu má jeden nadřazený uzel a může mít libovolný počet podřízených uzlů, včetně nuly.

Na rozdíl od normální struktury dat stromu vyžaduje struktura čtyř stromů, aby každý vnitřní uzel měl přesně čtyři podřízené uzly. Při ilustrování většiny struktur čtyřúhelníků uvidíte uzel, který má viset čtyři podřízené uzly, s linkami spojující nadřazený uzel s podřízenými uzly. Ilustrace může pokračovat, další čtyři dětské uzly visí z každého z původních čtyř dětských uzlů.

Jindy bude ilustrace čtyřúhelníku oblast nebo čtverec. Kdykoli region dosáhne své maximální kapacity pro ukládání dat, je rozdělen do čtyř kvadrantů. Normálně jsou regiony a kvadranty čtverce, i když to mohou být také obdélníky nebo jiné tvary.

Quad strom je dobrá datová struktura pro organizování pixelů na fotografii a pro organizování počítačové grafiky. Obrázek lze rozdělit do kvadrantů a každý kvadrant lze rozdělit na čtyři další. To lze opakovat znovu a znovu, dokud nedosáhnete úrovně jednotlivých pixelů. Pokud však kvadrant obsahuje pixely, které mají stejnou barvu, není důvod tento kvadrant dále dělit.

Ačkoli data uložená ve struktuře čtyřúhelníku mohou vyžadovat hodně úložného prostoru ve srovnání s jinými metodami organizování dat pro počítačovou grafiku, struktura čtyřúhelníku má několik výhod. Nejprve můžete vymazat celou fotografii nebo grafiku v jediném kroku tím, že vymažete kořenový uzel, který také vymaže všechny jeho podřízené uzly. Za druhé, můžete rychle snížit rozlišení na fotografii pouhým vymazáním konečné úrovně dětských uzlů. Tím se sníží množství potřebného úložného prostoru. Konečně, nalezení konkrétní oblasti fotografie pro manipulaci s obrázkem je snazší se strukturou čtyřúhelníku.

Quad stromy se používají také v několika dalších situacích, včetně prostorového indexování. Přestože jsou čtyřúhelníky omezeny na dvourozměrné obrazy, představující trojrozměrný obraz může sledovat podobnou strukturu, nazývanou oktree, což je rozdělení kostky na osm dětí.