Co to jest Quadtree?

Czwórka jest drzewiastą strukturą opartą na potędze czterech i wykorzystywaną do organizowania plików w bazie danych. Każdy węzeł nadrzędny lub początkowy ma cztery węzły potomne, a każde dziecko zawiera pewną ilość danych. Kiedy limit danych wyleje się poza jego granicę, z tego węzła powstanie czworo dzieci. Istnieją dwie główne struktury poczwórne: region i drzewo punktów, każda nieco różniąca się wyglądem. Podczas gdy w przypadku baz danych najczęściej stosuje się quadtree, można go również używać do znajdowania pikseli na obrazach dwuwymiarowych (2D), ponieważ piksele na obrazie 2D można zawsze podzielić na cztery części.

Wszystkie struktury drzewiaste są tworzone z nadrzędnymi lub gałęziami, węzłami i potomkami lub liśćmi, węzłami. Nadrzędny jest punktem początkowym i zawiera szerokie dane oparte na kategoriach, podczas gdy dziecko przechowuje pliki i dokumenty. W kwadracie każdy rodzic musi mieć czworo dzieci. Chociaż musi być czworo dzieci, nie wszystkie dzieci muszą zawierać dane; te bez są znane jako węzły zerowe. Te puste węzły często pozostają w zastoju i czekają na dane.

Każdy węzeł potomny w quadtree ma limit danych. Ten limit jest zwykle określany przez ogólny rozmiar bazy danych. Gdy jest tak dużo informacji, że przekracza to limit, węzeł potomny staje się węzłem rodzicielskim, zasadniczo rodząc - tworząc cztery węzły potomne, które zajmują wszystkie dodatkowe dane. Zwykle z tego stworzenia powstanie jeden lub dwa węzły zerowe, ale zależy to całkowicie od ilości danych w węźle.

Istnieją dwa główne kwadraty: region i punkt. Czteroosobowy region służy do dekompozycji całego regionu 2D na części w oparciu o moc czterech - takich jak cztery, osiem lub 16 części - i często jest używany do reprezentacji. Ta struktura jest najlepsza dla obrazów lub wykresów pól danych. Wersja punktowa jest jak drzewo binarne i najlepiej jej używać z uporządkowanymi punktami. Ten wariant jest również prawdziwym drzewem, ponieważ istnieje centralny punkt, z którego wyskakują wszystkie węzły, w przeciwieństwie do wersji regionu, w której węzły są rozproszone.

Najczęstszym zastosowaniem kwadratu jest oddzielenie i zorganizowanie bazy danych, ale nie jest to jedyne użycie. W algorytmach służących do znajdowania określonego piksela na obrazie często stosuje się czterokąty, ponieważ każdy piksel na obrazie można podzielić na cztery równe części. To sprawia, że ​​czwórki są wyjątkowo przydatne do wyszukiwania pikseli.