数据结构基本知识
逻辑结构
逻辑结构指数据对象中数据元素之间的关系。详细有以下几种
集合结构：元素直接没有直接关系，相互平等
线性结构：元素直接一一对应
树形结构：存在一对多情况
图形结构：多对多关系（存在有向图和无向图的区分，此处使用的Java GC回收机制示意图，java GC实现是基于有向图的）
物理结构
物理结构指数据的逻辑结构在计算机中的存储方式；分为线性存储和链式存储结构。
顺序存储结构：（地址连续）
链式存储结构：
算法五特性
有穷性 确定性 可行性 输入 输出
算法的设计要求
正确性 可读性 健壮性 高效率低存储
时间复杂度
算法的时间复杂度指算法的时间度量，他表示随问题的规模扩大，算法的执行时间的增长率。
栈的应用
FILO
两栈共享空间的思想
斐波那契数列
后缀表达式的计算
方法栈的实现（递归层次太多导致内存占用过大，性能降低）
队列
FIFO
循环队列
串
朴素模式匹配算法
效率更高的匹配算法：KMP算法（O（m+n））
树
树的表示法
二叉树
满二叉树（第n层有2的n次方个节点，根节点第零层）
完全二叉树
二叉树的5性质
二叉树的遍历（先根 中根 后根 层次遍历 由先根中根推后根 由中根后根推中根）
森林和树的转换
哈夫曼树（最优二叉树 带权的二叉树）（压缩算法）
图
查找
顺序查找
二分查找
借用树进行的查找：
| 简称 | 特点 | 平衡性 | 查找性能 | 插入 | 删除 | 优势 | 应用 | |
| 二叉搜索树 | BST | 索引树，由于构建不稳定，查找效率不稳定 | 无 | 不稳定，跟具体构建树相关，最好O(logn)，最差O（N） | 直接插入 | 删除的是叶子节点或只有左或右子树比较简单，如同时存在左右子树，那么要找到前驱或后继代替原先节点，再删除 | 性能高于线性查找 | 暂未找到，欢迎补充 |
| 平衡二叉树 | AVL | 索引树，BST进化版，自平衡，查找效率稳定 | 有 | 最好最坏都是O(lgn) | 最多需要2次旋转 | 最多需要lgN次旋转（参考，本人未证实） | 高度平衡，进一步提升查询效率 | 暂未找到，欢迎补充 |
| 红黑树 | RBT | 索引树，BST进化版，自平衡，查找效率相对稳定 | 有 | 基本维持在O(lgn),最坏比AVL略差(2lg(n+1)) | 最多需要2次旋转，3次变色 | 最多需要3次旋转（参考，本人未证实） | 自平衡，进一步提升查询效率 | Java中TreeSet和TreeMap，JDK 8以后，HashMap的设计 |
| B树 | ^ | 多路查找树，提升IO效率，索引树进化而来 | 有 | IO次数取决于高度，减少IO次数 | 1.可以直接插入的情况2.插入后破环平衡，需要进行分裂 | 1.可以直接删除2.直接删除后破环平衡，先向左右子树“借”节点3.直接删除后破环平衡，左右子树“借”不到节点，合并子树 | 降低IO次数 | 文件系统索引和部分非关系型数据库，如MongoDB |
| B+树 | ^ | 多路查找树，提升IO效率，B树进化版 | 有 | 进一步减少IO次数 | 类似B树 | 类似B树 | 进一步降低IO次数，范围查询方便，查询性能稳定 | 大多关系型数据库使用B+树作为索引 |