Drzewo czwórkowe, czasami drzewo czwórkowe, drzewo Q lub QT, to termin informatyczny odnoszący się do metody organizowania danych w czterech kwadrantach. Bazy danych czasami używają drzew poczwórnych do przechowywania i znajdowania swoich rekordów. Ten rodzaj struktury organizacyjnej sprawdza się szczególnie dobrze, aby znaleźć określony bit lub piksel w dwuwymiarowym obrazie.
Drzewo quad w pewnym stopniu odpowiada strukturze danych drzewa powszechnie stosowanej w informatyce. Normalna struktura danych drzewa wygląda jak drzewo do góry nogami, w którym węzeł rodzicielski na szczycie drzewa ma jeden lub więcej połączonych z nim 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 potomnych, w tym zero.
W przeciwieństwie do normalnej struktury danych drzewa, struktura drzewa poczwórnego wymaga, aby każdy węzeł wewnętrzny miał dokładnie cztery węzły potomne. Podczas ilustrowania większości struktur drzewa poczwórnego zobaczysz węzeł, który ma cztery węzły potomne zwisające z niego, z liniami łączącymi węzeł rodzica z jego węzłami potomnymi. Ilustracja może być kontynuowana, z czterema kolejnymi węzłami podrzędnymi zwisającymi z każdego z pierwotnych czterech węzłów podrzędnych.
Innym razem ilustracja drzewa poczwórnego będzie regionem lub kwadratem. Za każdym razem, gdy region osiąga maksymalną pojemność do przechowywania danych, dzieli się go na cztery ćwiartki. Zwykle regiony i ćwiartki są kwadratami, chociaż mogą to być również prostokąty lub inne kształty.
Drzewo poczwórne to dobra struktura danych do porządkowania pikseli na zdjęciu oraz do porządkowania grafiki komputerowej. Obraz można podzielić na ćwiartki, a każdy kwadrant na cztery kolejne. Można to powtarzać raz za razem, aż osiągniesz poziom pojedynczych pikseli. Jeśli jednak kwadrant zawiera piksele, które mają ten sam kolor, nie ma powodu, aby dalej dzielić kwadrant.
Chociaż dane przechowywane w strukturze drzewa poczwórnego mogą wymagać dużo miejsca do przechowywania w porównaniu z innymi metodami organizowania danych dla grafiki komputerowej, struktura drzewa poczwórnego ma kilka zalet. Po pierwsze, możesz usunąć całe zdjęcie lub grafikę w jednym kroku, czyszcząc węzeł główny, który usuwa również wszystkie 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 podrzędnych. Zmniejszy to w ten sposób ilość wymaganej przestrzeni do przechowywania. Wreszcie, znalezienie określonego obszaru zdjęcia do manipulacji obrazem jest łatwiejsze dzięki strukturze drzewa poczwórnego.
Drzewa poczwórne są również używane w kilku innych sytuacjach, w tym w indeksowaniu przestrzennym. Chociaż drzewa czwórkowe są ograniczone do obrazów dwuwymiarowych, reprezentujące obraz trójwymiarowy może mieć podobną strukturę, zwaną ośmiornicą, która jest podziałem sześcianu na ośmioro dzieci.