Hashing menggunakan pohon pencarian, bukan daftar

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?

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.$O(1)$$O(n)$$O(n)$$O(n)$$O(\log n)$$O(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 .$O(\log n)$

$O(n)$$n$$n$$n-1 = \Theta(n)$$n-1$$O(n)$$O(1)$

$O(\log n)$

$O(1)$

$n$$n/2$$\Theta(n)$$\Theta(\log n)$