度：指一个节点拥有子节点的个数。
深度：树的层数，根节点为第一层。
叶子节点：度为0的节点，即没有子节点的节点。

树

树的每一个节点，可以有N个子节点，但是每个子节点只有一个前驱节点。

二叉树

除了子节点外，每个节点有两个分支，左右子树，每个节点最大度数为2；

满二叉树

国内定义：

一个二叉树，每一层的节点数都达到最大值。（看上去就是一个三角形）

国外定义：

一个二叉树，非叶子节点度数都是2。（要么度为0，要么度为2）

平衡二叉树（二叉排序树）

树的左右子树高度差不超过1，空树也是平衡二叉树；左子节点比父节点小，父节点比右子节点小。

常用实现方法：红黑树、AVL等。

红黑树

也是平衡二叉树，C++的map、set都是红黑树实现的。

实现

插入、删除，会用左旋、右旋维持树的平衡。

场景

内存排序。

B树

属于多叉树（平衡多路查找树），用在磁盘文件组织，如数据库索引。

相比平衡二叉树，每个节点包含的关键字增多了，层级减少了，从而减少数据查找次数和复杂度。

B+树

B树的升级版，充分利用节点空间，让查询速度更稳定，接近于二叉法查找。

B+树与B树的区别：

• B+树的非叶子节点，不保存关键字记录的指针，每个节点所能保存的关键字个数大大增加；
• B+树的叶子节点，保存了父节点所有关键字和关键字记录的指针，每个叶子节点的关键字从小到大链接；
• B+树的根节点关键字数量和其叶子节点个数相等；
• B+的非叶子节点只进行数据索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样；