Zdecydowanie zrównoważone deterministyczne listy pominięć

W sekcji 2.2 Cache-niepomny B-drzew , stanowczo Weight Balanced wyszukiwania Drzewa są zdefiniowane jako:

Dla niektórych stałych , każdy węzeł na wysokości ma potomków . $d$ $v$ $h$ $\Theta(d^h)$

Oni twierdzą:

Drzewa wyszukiwania spełniające właściwości 1 i 2 obejmują zrównoważone pod względem masy drzewa B, deterministyczne listy pominięć i listy pominięć w oczekiwanym znaczeniu.

Inne artykuły również twierdzą, że deterministyczne listy pominięć są silnie zrównoważone pod względem wagi, w tym współbieżne B-Drzewa B-drzewa nieobsługiwane przez pamięć podręczną i B-drzewa nieobsługujące pamięci podręcznej .

Nie mogę zrozumieć, dlaczego deterministyczne listy pominięć mają tę właściwość. Oryginalny papier na deterministycznych skip-list zauważa, że

Jak widać na ryc. 1, istnieje korespondencja jeden do jednego między 1-2 listami pomijanymi a 2-3 drzewami.

Wydaje mi się jednak, że 2-3 drzewa nie są silnie zrównoważone pod względem masy, ponieważ węzeł na wysokości może mieć od do potomków. $h$ $2^h$ $3^h$

ds.data-structures skip-lists

— jbapple
źródło

To brzmi jak uzasadniony problem. Wszystkie wspomniane artykuły są współautorami, więc może to być stały nadzór. Czy wysłałeś e-mail do autorów?

— Per Vognsen

jak krytyczny dla dowodów jest wąski zasięg dla liczby potomków?

— Suresh Venkat

@Per - Wysłałem e-mailem do współautora. @Suresh - Nie jestem pewien, ale autorzy zdecydowali się oprzeć swoje struktury na zrównoważonych pod względem masy drzewach B, więc moje pytanie nie dotyczy ważności głównych wyników.

— jbapple

Zachowaj ostrożność, aby przypadkowo nie narazić autora na publiczne zawstydzenie. por. meta.cstheory.stackexchange.com/questions/214/…

— Tsuyoshi Ito

@Tsuyoshi: Ponieważ znaczenie tego możliwego błędu jest bardzo niewielkie (o ile mi wiadomo, nie wpływa ono na deklarowane wyniki cytowanych artykułów w żaden sposób), a ponieważ większość „błędów” znajduję w opublikowanych praca jest tylko błędem w moim rozumieniu, pomyślałem, że lepiej byłoby najpierw zapytać tutaj. Nawet jeśli jest to błąd, jest tak niewielki, że podejrzewam, że nie doprowadziłby do zawstydzenia autora.

— jbapple,

Byłem w kontakcie z jednym z autorów. Potwierdził, że to był błąd.

Jak stwierdzono powyżej, nie wpływa to w żaden sposób na żaden z wyników pracy.

— jbapple
źródło