Poszukuję sposobów na utrzymanie względnie zrównoważonego drzewa opinającego wykresu, gdy dodam do niego nowe węzły / krawędzie.
Mam nieukierunkowany wykres, który zaczyna się jako pojedynczy węzeł, „root”.
Na każdym kroku dodaję do wykresu albo nowy węzeł i krawędź łączącą go z wykresem, albo tylko nową krawędź łączącą dwa stare węzły. Gdy rozwijam wykres, utrzymuję drzewo rozpinające. W większości przypadków oznacza to, że kiedy dodam nowy węzeł i krawędź, ustawiam nowy węzeł jako potomek starego węzła, z którym się łączy.
Nie mam kontroli nad kolejnością dodawania nowych węzłów, więc powyższy algorytm budowania drzew może oczywiście prowadzić do niezrównoważonego łączenia drzew.
Czy ktoś wie o heurystyce online, która utrzyma drzewo opinające „względnie zrównoważone”, jednocześnie minimalizując ilość pracy wykonanej przy ponownym drzewkowaniu? Mam pełną kontrolę nad strukturą drzewa. Nie kontroluję połączeń grafowych ani kolejności dodawania nowych węzłów.
Zauważ, że standardowe odpowiedzi Google na terminy takie jak „zrównoważony”, „rozpinanie” i „drzewo” wydają się być drzewami binarnymi i drzewami B, z których żadne nie ma zastosowania. Moje węzły grafowe mogą mieć dowolną liczbę sąsiadów, więc węzły drzewne mogą mieć dowolną liczbę potomków, a nie 2 jak drzewa binarne. B-drzewa utrzymują równowagę, zmieniając swoje listy przylegania i nie mogę zmienić łączności wykresu.
źródło
Odpowiedzi:
Za każdym razem, gdy dodajesz nowy wierzchołek z krawędzią, nie masz opcji. Za każdym razem, gdy dodajesz nową krawędź, jeśli bieżąca odległość do korzenia jest większa niż odległość przez nową krawędź, usuwasz starą krawędź starą najkrótszą ścieżką i dodajesz nową. W przeciwnym razie po prostu nie zmienisz drzewa. Myślę, że w ten sposób otrzymujesz coś bardzo podobnego do drzewa BFS w tym sensie, że poziomy drzewa będą zawierać te same wierzchołki, a odległość od wierzchołka do korzenia będzie taka sama jak odległość w drzewie BFS (i w wykres), ale nie wiem, czy to wystarczy, aby spełnić warunek „idealnego zrównoważonego drzewa opinającego”.
źródło
Skończyło się na tym, że:
Odpowiedź Winicjusza Santosa jest jego pierwszą częścią. Jak mówi, w dowolnej ramce dodaję nowy węzeł i krawędź nadrzędny-podrzędny łączący się z nim lub po prostu dodam poprzeczkę między dwoma istniejącymi węzłami. Krawędzie rodzic-dziecko nie dają możliwości zmiany struktury drzewa, robią to tylko krawędzie krzyżowe. Rozważ dodanie poprzecznej E między węzłami A i B, gdzie B ma większą głębokość drzewa. Jeśli (A.depth + 1) <B.depth, możemy zmniejszyć B.depth, czyniąc go dzieckiem A.
Po zmniejszeniu głębokości B, musimy teraz sprawdzić sąsiadów B, aby zobaczyć, czy mogą zmniejszyć swoją głębokość, stając się dziećmi B. Wykonujemy zatem pierwsze przejście od B, które przecina krawędź od X do Y, jeśli X. głębokość + 1 <Y.depth i ustawia Y na dziecko X.
źródło