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 rodzica lub gałęzi, węzłami i dzieckiem lub liściem, 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ąStagnant i poczekaj 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 limit, węzeł dziecięcy staje się węzłem nadrzędnym, zasadniczo rodząc - tworząc cztery węzły dziecięce, które przyjmują wszystkie dodatkowe dane. Z tego stworzenia zwykle będzie 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 - takich jak cztery, osiem lub 16 części - 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ż jest centralny punkt odktóre wszystkie węzły spływają, w przeciwieństwie do wersji regionu, w której węzły są rozproszone.

Najczęstszym zastosowaniem QuadTree jest oddzielenie i organizowanie bazy danych, ale nie jest to jej jedyne zastosowanie. 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 są wyjątkowo dostosowane do wyszukiwania pikseli.