Comparison of structure characteristics for search operations

When considering the implementations of the search found an interesting table with the characteristics of the structures used to implement the symbol tables. And considered the worst and average cases.

	worst case			average case
	insert	Search	the choice	insert	hit by search	miss while searching
array indexed by keys	one	one	M	one	one	one
ordered array	N	N	one	N / 2	N / 2	N / 2
ordered link list	N	N	N	N / 2	N / 2	N / 2
unordered array	one	N	Nlnn	one	N / 2	N
unordered linked list	one	N	Nlnn	one	N / 2	N
binary search	N	lnN	one	N / 2	lnN	lnN
binary search tree	N	N	N	lnN	lnN	lnN
red-black wood	lnN	lnN	lnN	lnN	lnN	lnN
random tree	N	N	N	lnN	lnN	lnN
hashing	one	N	Nlnn	one	one	one