树
节点的祖先节点包括其本身 后代节点也 包括其本身
edge
（A，B）A 为 B 的父节点，则 AB 的边为（A，B）
path
ABC 的 path 为（A，B，C）
degree
degree（A）A 的子节点
高度
某节点高度，某节点到叶节点的最長路径的边数，叶节点高度为 0 树的高度，根节点到叶节点的高度
深度
某节点深度，某节点到根节点的边数
平衡二叉树
每一个节点的左右子树的高度差不能大于 1
满二叉树
除了叶节点外每一个结点都有左右子叶，且叶节点位于二叉树底部
但不一定集中在左侧
完全二叉树
除了最后一层，其他各层都被填满，第 n 层的叶结点都连续集中在最左边
二叉搜索树（BST）
每个节点都满足，左子节点值小于该节点值，右子节点大于等于该节点值 增删改查数据时间复杂度 O（logN）
最小值是树最左端的节点，最大值是树最右端的节点
假设一直递增或递减的增数据会退化为链表，时间复杂度趋于 O(n)
使用平衡二叉查找树可以解决这一问题
平衡二叉查找树（AVL）
既满足平衡二叉树又满足二叉搜索树
红黑树
是一种特殊的二叉查找树，除了满足二叉查找树还满足自平衡的条件
- 节点必须是红色或黑色
- 根节点必须是黑色的
- 所有叶节点必须是值为 null 的黑色节点
- 如果一个节点是红色的，则它的两个子节点都是黑色的
- 从任一节点到达它的每个叶节点的所有路径，都有相同数目的黑色节点 保证红黑树从根节点到达每一个叶节点的最长路径都不会超过最短路径的两倍 所以最坏情况下增删改查的时间复杂度不会超过 O(logN)
和 AVL 树对比
插⼊和删除操作，⼀般认为红⿊树的删除和插⼊会⽐ AVL 树更快。因为，红⿊树不像 AVL 树那 样严格的要求平衡因⼦⼩于等于 1，这就减少了为了达到平衡⽽进⾏的旋转操作次数，可以说是 牺牲严格平衡性来换取更快的插⼊和删除时间。
红⿊树不要求有严格的平衡性控制，但是红⿊树的特点，使得任何不平衡都会在三次旋转之内解决。
⽽ AVL 树如果不平衡，并不会控制旋转操作次数，旋转直到平衡为⽌。
查找操作，AVL 树的效率更⾼。因为 AVL 树设计⽐红⿊树更加平衡，不会出现平衡因⼦超过 1 的情况，减少了树的平均搜索⻓度。
Trie 树，字典树或前缀树
Trie 树的本质是利⽤字符串的公共前缀，将重复的前缀合并在⼀起，其中根节点不包含任何信息，每 个节点表示⼀个字符串中的字符，从根节点到叶节点的路径，表示⼀个字符串。
多叉查找树
多叉查找树允许⼀个节点存储多个元素，并且可以拥有多个⼦树
B 树-平衡多叉查找树
- 左小右大
- M 叉 K 关键字
- ⼦节点数：⾮叶节点的⼦节点数>1，且<=M ，且 M>=2，空树除外
- 关键字数：枝节点（⾮根⾮叶）的关键字数（K）应满⾜ (M+1)/2 < K < M
- 所有叶⼦节点均在同⼀层、叶⼦节点除了包含了关键字和关键字记录的指针外也有指向其⼦节点的指针，只不过其指针地址都为 null 对
B+树
改进了 B 树，让内结点（⾮叶节点）只作索引使⽤，去掉了其中指向 data 的指针，使得每个结 点中能够存放更多的 key， 因此能有更⼤的出度。 这有什么⽤？这样就意味着存放同样多的 key，树的层⾼能进⼀步被压缩，使得检索的时间更短 中间节点的元素数 与⼦树⼀致，⽽ B 树⼦树数 与元素数 多 1
叶⼦节点是⼀个链表，可以通过指针顺序查找
前序遍历
先打印结点然后打印左子树，最后右子树
中序遍历
先打印左子树，然后节点，最后右子树
后序遍历
先打印左子树，然后右子树，最后该节点