Hashing menggunakan pohon pencarian, bukan daftar

11

Saya berjuang dengan hashing dan material pohon pencarian biner. Dan saya membaca bahwa alih-alih menggunakan daftar untuk menyimpan entri dengan nilai hash yang sama, juga dimungkinkan untuk menggunakan pohon pencarian biner. Dan saya mencoba untuk memahami apa waktu berjalan kasus terburuk dan rata-rata untuk operasi

  1. insert,
  2. find dan
  3. delete

layak dihargai. kasus rata-rata. Apakah mereka meningkat sehubungan dengan daftar?

forrestGump
sumber
Jika Anda memiliki akses ke analisis ketat runtime tabel hash dengan linear chaining (yaitu daftar linier), ganti bagian di mana biaya rata-rata pada daftar linier terhubung dengan hasil rata-rata kasus implementasi pohon pencarian yang seimbang. Sisanya adalah mekanik. (An jelas, ini membantu.)
Raphael

Jawaban:

4

Untuk daftar, penyisipan, cari dan hapus masing-masing dalam , O ( n ) , O ( n ) . Daftar yang diurutkan lebih buruk. Pencarian biner itu sendiri adalah untuk array yang diurutkan, di mana operasi berada di O ( n ) , O ( log n ) , O ( n ) . Jika Anda ingin operasi "penyisipan" dan "hapus" maka Anda membutuhkan lebih dari sekedar pencarian biner.HAI(1)HAI(n)HAI(n)HAI(n)HAI(catatann)HAI(n)

Anda mungkin menginginkan sesuatu seperti pohon pencarian biner . Jauh lebih mudah untuk menemukan referensi tentang hal itu setelah Anda memiliki terminologi yang tepat. Operasi-operasi ini berada dalam waktu kasus terburuk, misalnya untuk implementasi yang menggunakan pohon AVL dan pohon merah-hitam .HAI(catatann)

jmad
sumber
1
Itu semua benar, tetapi saya tidak melihat bagaimana itu menjawab pertanyaan yang diajukan.
rgrig
Itu bukan pertanyaan yang sama sekali pada saat itu. (Bahkan riwayat edit tidak memiliki pertanyaan asli. Aneh.) Saya dapat memperbarui jawaban saya tetapi itu akan menjadi berlebihan dengan Gilles.
jmad
4

HAI(n)nnn-1=Θ(n)n-1HAI(n)HAI(1)

HAI(catatann)

HAI(1)

nn/2Θ(n)Θ(catatann)

Gilles 'SANGAT berhenti menjadi jahat'
sumber
2
"dengan distribusi rata-rata data" harus membaca "dengan fungsi hash yang cukup acak"
JeffE