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 stromů, které se běžně používají 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.Ilustrace může pokračovat, s dalšími čtyřmi dětskými uzly visícími z každého z původních čtyř uzlů pro děti.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á datová struktura 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.Struktura čtyř stromů má 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.Nakonec je nalezení konkrétní oblasti fotografie pro manipulaci s obrázkem snazší 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é stromy omezeny na dvourozměrné obrazy, představující trojrozměrný obraz může sledovat podobnou strukturu, nazývanou Octree, což je rozdělení krychle na osm dětí.