树的概念：树是$n$个结点的有限集合，有且仅有一个被称为根的结点。当$n>1$时，其余结点可分为互不相交的有限集合，其中每个集合本身又是一颗树。

树的属性：

• 结点层次（深度）：从上往下数
• 结点的高度：从下往上数
• 树的高度（深度）：总共多少层
• 结点的度：有几个子分支
• 树的度：各个结点最大的度

有序树：树中结点各子树从左到右是有次序的，不能交换。

无序树：~

森林是$m$棵互不相交的树的集合。

树的性质：

度为m的树跟m叉树不一样。

• 结点数 = 总度数 + 1
• m叉树：每个结点最多只能有m个孩子的树
• 度为m的树第i层至多有$m^{i-1}$个结点
• 高度为h的m叉树至多有$\frac{m^h-1}{m-1}$个结点
• 高度h的m叉树至少有h个结点
• 具有n个结点的m叉树的最小高度为$lo{g}_m(n(m-1)+1)$（向上取整）

二叉树

有序树。

• 满二叉树：一颗高度为h，且含有$2^h-1$个结点。
• 完全二叉树：结点编号与满二叉树一一对应。

二叉树性质：

• 非空二叉树中度为0、1、2的结点个数分别为$n_0$、$n_1$、$n_2$，则$n_0=n_2+1$
• 二叉树第i层最多有$2^{i-1}$个结点
• 完全二叉树高度h为$lo{g}_{2}n+1$

二叉树遍历：

• 先序遍历：根左右
• 中序遍历：左根右
• 后续遍历：左右根

二叉排序树

左子树结点值 < 根结点值 < 右子树结点值 的二叉树。

查找效率取决于树的高度，最好O(logn)，最坏O(n)

平衡二叉树

树上任一结点的左子树和右子树的高度之差不超过1。

红黑树

红黑树是二叉排序树

• 每个结点是黑色或红色
• 根节点是黑色
• 叶结点（外部结点、NULL结点）是黑色
• 不存在两个相邻的红结点
• 从一个结点到任一叶子结点中所含黑结点数目相同

平衡二叉树适用于以查为主；红黑树适用于频繁插入删除。

B树

B树，又称多路平衡查找树，B树中所被允许的孩子个数的最大值称为B树的阶，通常用m表示。

1. 书中每个结点最多有m棵子树，最多含有m-1个关键字
2. 若根结点不是终端结点，则至少有两棵子树
3. 除根结点外的非叶结点至少有$m/2$（向上取整）棵子树
4. 所以的叶结点都出现在同一层次且不带有信息

B+树

m阶的B+树需满足：

1. 每个分支结点最多有m棵子树
2. 非叶根节点至少两颗子树，其他每个分支结点至少$m/2$（向上取整）棵子树
3. 结点的子树个数与关键字个数相等
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排序，并且相邻叶结点按大小顺序相互链接起来
5. 所有分支结点中仅包含它的各个子节点中关键字最大值及指向其子结点的指针

B树和B+树区别：

对比项	B树（B-Tree）	B+树（B+Tree）
节点存储	每个节点存储键值和数据	非叶子节点仅存储键值，数据存储在叶子节点
数据存储位置	数据可能存储在叶子节点或内部节点	数据仅存储在叶子节点
搜索方式	可能提前在内部节点找到数据	需要遍历到叶子节点才能找到数据
范围查询	低效，需在多个节点查找	高效，叶子节点通过指针连接，可顺序遍历
磁盘I/O	由于数据分布在各层，索引节点存储较少，访问次数较多	内部节点仅存键值，索引结构更紧凑，磁盘I/O次数更少
插入删除影响	可能会影响所有层级	仅影响叶子节点，索引结构较稳定
树的高度	相对较高，占用更多磁盘块	相对较矮，查询效率更高
应用场景	适用于键值对存储，如内存数据库	适用于数据库索引和文件系统（如 MySQL InnoDB）