一、数组、链表、哈希表；队列、栈
1.数组：
2.链表：
3.哈希表：
4.队列：先进先出
5.栈：先进后出
| 数据结构 | 优点 | 缺点 |
|---|---|---|
| 数组 | 查找快 | 增删慢 |
| 链表 | 增删快 | 查找慢 |
| 哈希表 | 增删、查找都快 | 数据散列，对存储空间有浪费 |
| 栈 | 顶部元素插入和取出快 | 除顶部元素外，存取其他元素都很慢 |
| 队列 | 顶部元素取出和尾部元素插入快 | 存取其他元素都很慢 |
| 二叉树 | 增删、查找都快 | 删除算法复杂 |
| 红黑树 | 增删、查找都快 | 算法复杂 |
| 位图 | 节省存储空间 | 不方便描述复杂的数据关系 |
二、堆、树(二叉树、B树、B+树、红黑树)
1.二叉树分类
时间复杂度最好情况是O(logn) ，最坏情况下时间复杂度O(n)
1）满二叉树：如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
2）完全二叉树：如果一个二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
3）二叉搜索树：左子树都比其根节点小，右子树都比其根节点大，递归定义。
二叉搜索树的中序遍历一定是从小到大排序的。
4）平衡二叉树（红黑树）：要么是一棵空树，要么保证左右子树的高度之差不大于 1，并且子树也必须是一棵平衡二叉树。
平衡二叉树必须是二叉搜索树
性能：平衡二叉树在添加和删除时需要进行复杂的旋转保持整个树的平衡，最终，插入、查找的时间复杂度都是 O(logn)，性能已经相当好了。
5）最优二叉树(哈夫曼树): 树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。应用：哈夫曼编码。
2.红黑树：是一种自平衡的二叉树。应用内存排序。
插入和删除的最坏的时间复杂度是O(log N)
3.B树：平衡多路查找树（查找路径不只两个），不同于常见的二叉树，它是一种多叉树。
4.B+树：B树的一种升级版本，B+树查找的效率要比B树更高、更稳定。应用于数据库搜索。
非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中。
三、图(对现实世界建模)
标签：Java,哈夫曼,复杂度,常见,查找,二叉树,红黑树,增删,数据结构 From： https://www.cnblogs.com/wenxiangchen/p/16594670.html