Czytam wlasnie Cormena, a dokladniej tablice z haszowaniem, metode lancuchowa, ze pod danym indeksem w tablicy mam liste elementow o tym samym kluczu. I jest tam taki fragment : " Jesli listy sa dwukierunkowe to operacje usuniecia mozna wykonac w czasie O(1) ( Zauwazmy ze parametr procedury CHAINED-HASH-DELETE(T,x) jest zelement x a nie jego klucz k. Tak wiec nie musimy zaczynac od wyszukiwania x... "
Moglby mi ktos to wytlumaczyc jakby to mialo dzialac?
0
0
O(1) raczej nie osiagniesz (chyba cos zle przepisales albo ja juz nie mysle o tej porze), na moje oko to bedziesz mial staly w wybraniu lancucha i zmienny w wyszukaniu elementu do usuniecia, chyba, ze usuwasz z konkretnego indeksu lancucha element, wtedy rzeczywiscie dostep jest staly, ew. mowa o usuniecie pierwszego/ostatniego elementu lancucha wtedy dostep rowniez jest staly. Jednak jak musisz szukac elementu w lancuchu to wypada tam jakies drzewko zamiast listy wpakowac.
1
@n0name_l sprawdziłem i faktycznie w Cormenie jest tak napisane. Ale mnie się wydaje że tam jest takie trochę "wyprzedzenie" bo później jest dowód że czas szukania na liscie synonimów przy pewnych założeniach jest stały, w efekcie czas dodawania i usuwania też będzie stały ;]