Co je to čtyřčlenný strom?

Quad Tree, někdy quadtree, Q-Tree nebo QT, je termín informatiky, který odkazuje na metodu organizace dat ve čtyřech kvadrantech. Databáze někdy používají Quad Trees k ukládání a nalezení jejich záznamů. Tento typ organizační struktury funguje obzvláště dobře pro nalezení konkrétního bitu nebo pixelu ve dvourozměrném obrazu.

Quad strom poněkud sleduje strukturu dat stromu běžně používanou v informatice. Normální struktura dat stromů vypadá jako strom vzhůru nohama, kde má rodičovský uzel v horní části stromu jeden nebo více dětských uzlů. Každý jiný uzel na stromu má jeden rodičovský uzel a může mít libovolný počet dětí uzlů, včetně nuly. Při ilustraci většiny struktur čtyř stromů uvidíte uzel, který z něj visí čtyři uzly pro děti, přičemž řádky spojují nadřazený uzel s dětskými uzly. IlustAtion může pokračovat, se čtyřmi dalšími dětskými uzly visícími z každého z původních čtyř dětí uzlů. Kdykoli region dosáhne své maximální kapacity pro ukládání dat, je rozdělen do čtyř kvadrantů. Oblasti a kvadranty jsou obvykle čtverce, i když mohou být také obdélníky nebo jiné tvary.

Quad Tree je dobrá struktura dat pro organizaci pixelů na fotografii a pro organizaci počítačové grafiky. Obrázek lze rozdělit na kvadranty a každý kvadrant lze rozdělit na další čtyři. 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 k dalšímu rozdělení kvadrantu.

Ačkoli data uložená ve struktuře čtyř stromů mohou vyžadovat hodně úložného prostoru ve srovnání s jinýmiMetody organizace dat pro počítačovou grafiku má struktura čtyř stromů několik výhod. Nejprve můžete smazat celou fotografii nebo grafiku v jednom kroku vyčištěním kořenového uzlu, který také vyčistí všechny jeho uzly pro děti. Za druhé, rychle můžete snížit rozlišení na fotografii pouhým vymazáním konečné úrovně dětských uzlů. Tím se sníží množství úložného prostoru, který vyžaduje. A konečně, nalezení konkrétní oblasti fotografie pro manipulaci s obrazem je jednodušší se strukturou čtyř stromů.

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