文章目录
tree
一棵树是由N个节点和N - 1条边组成。
没有子节点的节点叫做树叶(leaf)
根节点为root
如果存在一个路径从n1到n2，则n1是n2的一位祖先（ancestor），n2是n1的一位后裔（descendant）
对于任意节点ni，ni的深度（depth）是从根到ni的唯一路径的长，ni的高度（height）是从ni到一片树叶的最长路径的长。因此根的深度为0，所有树叶的高度为0
先序遍历（preorder traversal），对节点的处理工作是在它诸多儿子节点被处理之前（pre）进行的。
后序遍历（postorder traversal），对节点的处理工作是在它诸多儿子节点被计算之后进行的
中序遍历（inorder traversal），左，节点，右
二叉树（binary tree）
- 平均二叉树的平均深度为 O(N^1/2)，二叉查找树深度平均值为 O(logN)
- 具有N个节点的二叉树都将需要N + 1个NULL指针 （可以由 2N条边（满）减去 N-1条边（实际）来获得）
二叉查找树
对于树中的每一个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树种所有关键字值大于X的关键字值
复杂度
除了MakeEmpty外，其他操作基本都在 O(logN)
- 一棵树的所有节点的深度的和称为内部路径长
AVL
- 左-左、右-右：单旋转
- 右-左、左-右：双旋转
B-树
阶为M的B-树是一棵具有下类结构特性的树
- 树的根或者是一片树叶，或者其儿子数在2-M之间
- 除树根和树叶外，其他节点的儿子数在 M / 2 到 M 之间
- 所有树叶都在同一深度上
B-树的深度最多是logM/2(N)
