Co to jest quadtree?

QuadTree to struktura przypominająca drzewo oparta na mocy czterech i używana do organizowania plików w bazie danych.Każdy rodzic lub początek węzła ma cztery węzły dziecięce, a każde dziecko przechowuje pewną ilość danych.Gdy ograniczenie danych rozlewa się nad jego granicą, z tego węzła zostanie wykonane czworo dzieci.Istnieją dwie główne struktury quadtree: region i drzewo punktowe, każda nieco inne pod względem konstrukcji.Podczas gdy quadtree jest najczęściej używany z bazami danych, 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 przypominające drzewo sąWykonane z rodzicem, gałęzią, węzłami i dzieckiem lub liśćmi, węzłami.Rodzic jest punktem wyjścia i zawiera dane oparte na kategorii, podczas gdy dziecko przechowuje pliki i dokumenty.W QuadTree każdy rodzic musi mieć czworo dzieci.Chociaż musi być czworo dzieci, nie wszystkie dzieci muszą zawierać dane;Osoby nie są znane jako węzły zerowe.Te zerowe węzły często pozostają stagnacyjne i czekają na dane.

Każdy węzeł dziecięcy w quadtree ma limit danych.Ten limit jest zwykle definiowany przez ogólny rozmiar bazy danych.Gdy jest tak wiele informacji, że przekracza granicę, węzeł dziecięcy staje się węzłem nadrzędnym, zasadniczo rodząc i mdash;Tworzenie czterech węzłów dziecięcych, które przyjmują wszystkie dodatkowe dane.Z tego stworzenia zwykle występuje jeden lub dwa węzły zerowe, ale zależy to całkowicie od tego, ile danych było w węźle.

Istnieją dwa główne quadtree: region i punkt.Quadtree regionu służy do rozkładu całego regionu 2D na części oparte na mocy czterech i mdash;takich jak cztery, osiem lub 16 części i mdash;i często używane do reprezentacji.Ta struktura jest najlepsza dla obrazów lub wykresów pola danych.Wersja punktowa jest jak drzewo binarne i jest najlepiej używana z uporządkowanymi punktami.Ten wariant jest również prawdziwym drzewem, ponieważ istnieje centralny punkt, z którego wychodzą wszystkie węzły, w przeciwieństwie do wersji regionu, w której rozproszone są węzły.

Najczęstszym zastosowaniem quadtree jest oddzielenie i uporządkowanie bazy danych, aleTo nie jest jego tylko użycie.Algorytmy stworzone w celu znalezienia określonego piksela na obrazie powszechnie używają quadtrees, ponieważ każdy piksel na obrazie można podzielić na cztery równe części.To sprawia, że QuadTrees jest wyjątkowo dostosowany do wyszukiwania pikseli.