Co to jest Quad Tree?

Drzewo czwórkowe, czasami drzewo czwórkowe, drzewo Q lub QT, to termin informatyki, który odnosi się do metody porządkowania danych w czterech ćwiartkach. Bazy danych czasami wykorzystują drzewa quadów do przechowywania i wyszukiwania swoich rekordów. Ten typ struktury organizacyjnej działa szczególnie dobrze, aby znaleźć określony bit lub piksel na obrazie dwuwymiarowym.

Drzewo quad nieco przypomina strukturę danych drzewa powszechnie używaną w informatyce. Normalna struktura danych drzewa wygląda jak drzewo do góry nogami, w którym nadrzędny węzeł u góry drzewa ma podłączony jeden lub więcej węzłów potomnych. Każdy inny węzeł w drzewie ma jeden węzeł nadrzędny i może mieć dowolną liczbę węzłów podrzędnych, w tym zero.

W przeciwieństwie do normalnej struktury danych drzewa, struktura drzewa czworokątnego wymaga, aby każdy węzeł wewnętrzny miał dokładnie cztery węzły potomne. Podczas ilustrowania większości struktur drzewa quad, zobaczysz węzeł, który ma cztery węzły potomne zwisające z niego, z liniami łączącymi węzeł macierzysty z jego węzłami potomnymi. Ilustracja może być kontynuowana, z czterema dodatkowymi węzłami potomnymi zwisającymi z każdego z czterech oryginalnych węzłów potomnych.

Innym razem ilustracją drzewa quadów będzie region lub kwadrat. Za każdym razem, gdy region osiąga maksymalną pojemność do przechowywania danych, dzieli się go na cztery ćwiartki. Zazwyczaj regiony i ćwiartki są kwadratami, chociaż mogą być również prostokątami lub innymi kształtami.

Drzewo quad jest dobrą strukturą danych do organizowania pikseli na zdjęciu i do organizowania grafiki komputerowej. Obraz można podzielić na ćwiartki, a każdy kwadrant można podzielić na cztery kolejne. Można to powtarzać raz za razem, aż osiągniesz poziom poszczególnych pikseli. Jeśli jednak kwadrant zawiera piksele tego samego koloru, nie ma powodu do dalszego dzielenia kwadrantu.

Chociaż dane przechowywane w strukturze quad-tree mogą wymagać dużo miejsca do przechowywania w porównaniu z innymi metodami organizowania danych do grafiki komputerowej, struktura quad-tree ma kilka zalet. Po pierwsze, możesz usunąć całe zdjęcie lub grafikę w jednym kroku, usuwając węzeł główny, który również usuwa wszystkie jego węzły podrzędne. Po drugie, możesz szybko zmniejszyć rozdzielczość na zdjęciu, po prostu usuwając końcowy poziom węzłów potomnych. Zmniejszy to w ten sposób ilość wymaganego miejsca do przechowywania. Wreszcie, znalezienie określonego obszaru fotografii do manipulacji obrazem jest łatwiejsze dzięki strukturze drzewa quad.

Drzewa quad są również używane w kilku innych sytuacjach, w tym w indeksowaniu przestrzennym. Chociaż drzewa quad są ograniczone do dwuwymiarowych obrazów, reprezentujący trójwymiarowy obraz może mieć podobną strukturę, zwaną oktawą, czyli podziałem sześcianu na ośmioro dzieci.