Interaktywne wprowadzenie do drzew czworobocznych

Dlaczego Quadtrees mają większe znaczenie niż myślisz

Za każdym razem, gdy przesuwasz palcem, aby powiększyć mapę cyfrową, pytasz o pobliskie restauracje lub oglądasz, jak moduł śledzenia floty w czasie rzeczywistym aktualizuje dziesiątki ikon pojazdów bez zatrzymywania przeglądarki, istnieje duża szansa, że drzewo czworokątne wykonuje ciężką pracę za kulisami. Quadtrees to jedna z tych eleganckich struktur danych, o których większość ludzi nigdy nie słyszała, a mimo to po cichu zasilają niektóre z najbardziej krytycznych pod względem wydajności systemów współczesnego oprogramowania — od wykrywania kolizji w grach wideo po systemy informacji geograficznej przetwarzające miliony zapytań przestrzennych na sekundę. Zrozumienie, jak one działają, nie tylko sprawi, że staniesz się lepszym programistą; zasadniczo zmienia to sposób myślenia o organizowaniu i przeszukiwaniu danych przestrzennych. Niezależnie od tego, czy budujesz platformę logistyki dostaw, pulpit analityczny oparty na lokalizacji, czy po prostu próbujesz wyrenderować 50 000 punktów danych na płótnie bez zawieszania przeglądarki, quadtrees oferują rozwiązanie, które jest zarówno intuicyjne, jak i niezwykle wydajne.

Czym właściwie jest drzewo czworokątne?

Drzewo czwórkowe to drzewiasta struktura danych, w której każdy węzeł wewnętrzny ma dokładnie czworo dzieci, z których każdy reprezentuje jedną ćwiartkę dwuwymiarowej przestrzeni. Wyobraź sobie, że bierzesz kwadratowy obszar i dzielisz go na cztery równe kwadraty — północny zachód, północny wschód, południowy zachód i południowy wschód. Każdy z tych kwadratów można dalej podzielić na cztery kolejne kwadraty i tak dalej, rekurencyjnie, aż do osiągnięcia warunku zatrzymania. Warunek zatrzymania to zazwyczaj maksymalna głębokość lub próg określający, ile punktów danych może pomieścić pojedynczy węzeł, zanim będzie musiał się podzielić.

Piękno tego podejścia leży w jego adaptacyjnym charakterze. Obszary gęste z punktami danych dzielą się na coraz drobniejsze komórki, podczas gdy rzadkie obszary pozostają dużymi, niepodzielnymi regionami. Drzewo czworokątne przechowujące lokalizacje 10 000 kawiarni w całym kraju stworzyłoby głębokie, szczegółowe podziały na Manhattanie – gdzie na kilku kilometrach kwadratowych mogłoby znajdować się 300 sklepów – zachowując jednocześnie rozległe obszary wiejskie Wyoming jako pojedynczy, niepodzielony węzeł zawierający zero lub jeden punkt. Ta adaptacyjna rozdzielczość sprawia, że ​​drzewa czworokątne są tak potężne w porównaniu z płaską siatką, która marnowałaby ogromne ilości pamięci na puste komórki.

Koncepcja została po raz pierwszy opisana przez Raphaela Finkela i J.L. Bentleya w 1974 roku i od tego czasu podzieliła się na kilka wariantów: drzewa czworokątne punktów przechowują pojedyncze pary współrzędnych, drzewa czworokątne regionu reprezentują obszary przestrzenne (przydatne do kompresji obrazu), a drzewa czworokątne krawędzi obsługują linie i krzywe. Każdy wariant optymalizuje się pod kątem różnych przypadków użycia, ale podstawowa zasada podziału rekurencyjnego pozostaje taka sama we wszystkich.

Jak działa wstawianie i wykonywanie zapytań

Aby wstawić punkt do drzewa czworokątnego, zaczynasz od węzła głównego i określasz, do której z czterech ćwiartek należy ten punkt. Następnie powracasz do węzła podrzędnego tej ćwiartki i powtarzasz proces. Jeśli dojdziesz do węzła liścia, który nie przekroczył swojej pojemności (zwykle ustawionej na 1 lub 4 punkty), po prostu przechowujesz tam punkt. Jeśli liść ma już pełną pojemność, dzieli się na czworo dzieci, rozdziela między nie istniejące punkty, a następnie wstawia nowy punkt do odpowiedniego dziecka. W przypadku zrównoważonej dystrybucji proces ten zwykle kończy się w czasie O(log n), chociaż najgorsze scenariusze z silnie klastrowanymi danymi mogą obniżyć wydajność.

Zapytanie o zakres — znajdowanie wszystkich punktów w danym prostokątnym obszarze — to miejsce, w którym drzewa czworokątne naprawdę błyszczą. Zamiast sprawdzać każdy pojedynczy punkt zbioru danych (operacja O(n)), zaczynasz od korzenia i zadajesz proste pytanie w każdym węźle: czy granica tego węzła przecina się z moim prostokątem wyszukiwania? Jeśli nie, przycinasz całe poddrzewo, co potencjalnie eliminuje tysiące punktów z jednego porównania. Jeśli istnieje skrzyżowanie, powracasz do odpowiednich dzieci. Punkty znalezione w węzłach liści, które mieszczą się w prostokącie wyszukiwania, są dodawane do zestawu wyników.

Rozważmy praktyczny przykład: masz zbiór danych

Related Posts

• Tak to jest spędzić życie w więzieniu (2023) [wideo]
• Kryptograficzna Odyseja DJB: Od Bohatera Kodu do Krytyka Standardów
• Dyrektor Waymo ujawnia, że ​​firma korzysta z pracowników zdalnych na Filipinach
• Jak wybrać między pisaniem Hindley-Milner a pisaniem dwukierunkowym