查找.md

查找

[TOC]

1.无序链表中的顺序查找

无序链表中顺序查找：

最坏情况查找	最坏情况插入	平均情况查找	平均情况插入	是否高效支持有序性
N	N	$$ N/2$$	N	否

2.有序数组中的二分查找

有序数组中二分查找：

最坏情况查找	最坏情况插入	平均情况查找	平均情况插入	是否高效支持有序性
$$lg(N)$$	2N	$$lg(N)$$	N

3.二叉查找树

​ 一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的数据结构。即二叉查找树。

4.红黑树

5.散列表

AVL 树和红黑树的区别：

http://blog.csdn.net/hustyangju/article/details/27214251