Co to jest zamek błyskawiczny i jak odnosi się do struktury przypominającej drzewo?

15

Czytałem rozdział w LYAH, który tak naprawdę nie miał dla mnie sensu. Rozumiem, że zamki błyskawiczne mogą dowolnie przechodzić przez strukturę przypominającą drzewo, ale potrzebuję trochę wyjaśnień na ten temat. Czy zamki można uogólnić na dowolną strukturę danych?

n_ary_crazy
źródło
3
Prawdopodobnie jest to bardziej odpowiednie dla informatyki , chociaż praca polegająca na uogólnianiu zamków błyskawicznych obejmuje całkiem sporo technicznych urządzeń.
Dave Clarke,
6
Zamek błyskawiczny to coś, co zawsze powinieneś mieć zamknięte, szczególnie podczas przemierzania drzewa.
Andrej Bauer,

Odpowiedzi:

14

Zamek błyskawiczny to ogólnie struktura danych z dziurą. Do przesuwania / manipulowania strukturami danych używane są zamki błyskawiczne, a otwór odpowiada bieżącemu ogniskowaniu przejścia. Zazwyczaj bierze się również pod uwagę element struktury danych, tak że ma się suwak (lista) i suwak listy lub (drzewo) i drzewo. Zamek błyskawiczny pozwala programiście efektywnie poruszać się po strukturze danych, zastępując nawet element w centrum uwagi. Para zamka błyskawicznego i element w ognisku spełniają warunek, że umieszczenie elementu w ognisku w otworze zapewnia oryginalną strukturę danych.

Zamki błyskawiczne można uogólniać na dowolne typy danych indukcyjnych. Pojęcie to można zdefiniować w sposób indeksowany według typu (patrz typy danych indeksowane według typu ). Są one również związane z ideą pochodnej struktury danych i zostały zbadane z perspektywy teorii teoretycznej .

Dave Clarke
źródło
2

Zamek błyskawiczny to na ogół para rzeczy: to struktura z dziurą, skupienie , reprezentujące miejsce w strukturze, w którym się znajdujesz, wraz ze ścieżką , rejestrujące, jak doszedłeś do tego skupienia. (Ta ścieżka jest śladem LYAH bułki tartej.)

Ścieżka jest sposobem, w jaki faktycznie stosujesz zmiany w strukturze: „idź w dół, idź w lewo, zwiększ wartość”. Poprzez wielokrotne stosowanie „idź w górę” ( go_upw pracy Hueta ) w tym momencie, możesz prześledzić swoje kroki i otrzymać nową, zmutowaną kopię oryginalnej struktury.

Rzeczywiście można je uogólnić na inne struktury:

Frank Shearar
źródło