Drzewo Kd: dane przechowywane tylko w liściach vs przechowywane w liściach i węzłach

Question

Próbuję zaimplementować drzewo Kd do wykonania najbliższego sąsiada i przybliżenia najbliższego wyszukiwania sąsiada w C++. Do tej pory natknąłem się na 2 wersje najbardziej podstawowego drzewa Kd.

1. jednej, gdzie dane są przechowywane w węzłach oraz w liściach, takich jak here
2. jednej, gdzie dane są przechowywane tylko w liściach, takich jak here

Wydają się być zasadniczo to samo, o takich samych właściwościach asymptotycznych.

Moje pytanie brzmi: Czy są jakieś powody, dla których warto wybrać jeden nad drugim?

Pomyślałem dwa powody tej pory:

1. drzewa, które przechowuje dane w węzłach też jest płytsza od 1 poziomu.
2. Drzewo, która przechowuje dane wyłącznie w liściach ma łatwiej wdrożyć delete data funkcję

Czy są jakieś inne powody, należy wziąć pod uwagę przed podjęciem decyzji, który z nich zrobić?

Answer 1

Możesz po prostu oznaczyć węzły jako usunięte i odłożyć wszelkie zmiany strukturalne do następnego przebudowy drzewa. Z czasem k-d-drzewa ulegają degradacji, więc musisz często odbudowywać drzewa. k-d-drzewa są świetne dla zestawów danych niskowymiarowych, które się nie zmieniają lub gdzie można łatwo pozwolić sobie na odbudowanie (w przybliżeniu) optymalnego drzewa.

Jeśli chodzi o wdrażanie drzewa, zalecam stosowanie minimalistycznej struktury. Zwykle używam węzłów w postaci , a nie. Używam tablicy odwołań do obiektów danych. Oś jest definiowana przez bieżącą głębokość wyszukiwania, bez potrzeby przechowywania go w dowolnym miejscu. Lewe i prawe sąsiedzi są podane przez drzewo wyszukiwania binarnego tablicy. (W przeciwnym razie po prostu dodaj tablicę o rozmiarze byte, połowę wielkości zbioru danych, do przechowywania użytych osi). Ładowanie drzewa odbywa się przez wyspecjalizowany QuickSort. Teoretycznie najgorszy przypadek to O(n^2), ale z dobrą heurystyką, taką jak mediana 5, można niezawodnie uzyskać O(n log n) przy minimalnym stałym obciążeniu.

Chociaż nie ma to większego znaczenia dla C/C++, w wielu innych językach zapłacisz całkiem sporo za zarządzanie wieloma obiektami. A type*[] to najtańsza struktura danych, którą można znaleźć, a w szczególności nie wymaga dużego nakładu pracy. Aby oznaczyć element jako usunięty, możesz go odszukać i przeszukać obie strony, gdy napotkasz znak null. W przypadku wstawek, najpierw zbierałem je w buforze. A kiedy licznik modyfikacji osiągnie próg, odbuduj.

I o to w tym wszystkim chodzi: jeśli twoje drzewo jest naprawdę tanie w odbudowie (tak tanie jak uciekanie się do prawie wstępnie posortowanej tablicy!), To nie zaszkodzi często odbudowywać drzewo. Skanowanie liniowe na krótkiej "liście wstawiania" jest bardzo przyjazne dla pamięci podręcznej procesora. Pomijanie null s jest również bardzo tanie.

Jeśli chcesz bardziej dynamiczną strukturę, polecam patrząc na R * -trees.W rzeczywistości są one zaprojektowane tak, aby zachować równowagę przy wstawianiu i usuwaniu i organizować dane w zorientowanej dyskowo strukturze bloków. Ale nawet w przypadku drzew R pojawiły się doniesienia, że ​​utrzymanie bufora wstawiania itp. W celu odłożenia zmian strukturalnych poprawia wydajność. A ładowanie zbiorcze w wielu sytuacjach też bardzo pomaga!