基本作用
- 树是图的一种，但是不是首尾连在一起的
- 树的其中一类是从 self-balanced tree BST演变出来的，包括红黑树，AVL，Splay，Treap等等（经常在面试出现但是实际不常用）
- 另一种大类是 Trie（字典树），能保证字典排序。前缀搜索，正则匹配，数据压缩，构建索引等等用处
二叉树，最基础的结构
定义
- 每个数的节点最多只有两个子节点
- 子节点分左右，必须不能颠倒
应用环境
- hash表，sets
- 数据库，优先队列
- LDAP查找信息，在XML/HTML中进行搜索
不同分支：
- full binary tree：除了叶节点（也就是一个子节点都没有的点），其他的都有两个子节点
- complete binary tree：除了最后一层外，其他层的节点都有两个子节点，最后一层的子节点必须是左对齐
- perfect binary tree：形成完美的三角形
BST 二叉搜索树
定义
- 两个子节点里面，左边的必须小于父节点，右边的必须大于父节点
操作
- 插入：
- 如果没有任何点，作为root
- 如果大放到右边的子树，小放到左边的子树
- 重复2直到找到空位
- 删除：
- 删除叶节点：断掉这个点和父节点的联系
- 删除只有一个子节点的点：把父节点对待删除点的reference改为父节点对待删除点子节点的reference
- 两个子节点的点：左节点不动，右边的换到父节点的位置上/右节点不同，左节点换到父节点
- 删除root：需要更改对root的reference
- 遍历
- 顺序：左-> 中 -> 右
- 反序：左 -> 右 -> 中
- DFS：中 -> 左 -> 右
平衡二叉树 AVL树
- 左右两个子树的高度差不超过1
- 且子树本身也是平衡树
- 在构建平衡树的时候确保他们平衡，从而导致最差的时间复杂度也是 logN
- 虽然在插入或者删除的时候，可能会在旋转上花费时间，但是整体性能更加稳定
旋转
- 对于需要旋转的情况来说，一共有四种基本状况
- 对于左左或者右右：但旋转
- 对于左右或者右左：双旋转
红黑树
- 节点是红色或黑色
- 叶节点都是黑色的
- root是黑色的
- 每个红节点必须有两个黑子节点，也就是说不能路径上有两个连续的红色
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
B树
定义
- 用来处理排序后的数据，查找，插入，删除，循序存取都在对数时间完成
- 对于普通的二叉树，可以有多于两个的节点
- 优化大块数据的读写操作，加快存取速度
在构建的时候，每一个点的存储数量是有限的，超过上限的时候，本节点分别成三部分，一个往上移动，另外两个分开
B+树
- 只有达到叶节点才算命中，B树可以在非叶命中
- 更适合文件索引系统
B * 树
- 节点利用率从 1/2变成了 2/3
Trie树 字典树
- hash树的变种，保存大量字符串
- 利用公共前缀减少查找时间
特点
- 根节点不包括字符，除了根节点都只包含一个字符
- 从根节点到某一节点，一路连过去就是相关的字符串
- 每个节点的子节点的字符都不相同