数据结构

二叉树的性质：

1. 二叉树中，第 i 层最多有 2i-1 个结点
2. 如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点
3. 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1
4. 具有 n 个节点的满二叉树的深度为 log2(n+1)

完全二叉树：

1. 如果二叉树中除去最后一层节点后为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树
2. n 个结点的完全二叉树的深度为 [log2n]+1，[log2n] 表示取小于 log2n 的最大整数
3. 对于任意一个结点 i，当 i>1 时，父亲结点为结点 [i/2]，

深度优先搜索：
广度优先搜索：

红黑树：

1. 本身是一棵二叉查找树，在其基础上附加了两个要求：
   （1）树中的每个结点增加了一个用于存储颜色的标志域；
   （2）树中没有一条路径比其他任何路径长出两倍，整棵树要接近于“平衡”的状态
2. 满足以下性质的二叉查找树才是红黑树：
   （1）树中所有节点不是红的就是黑的
   （2） 根结点的颜色是黑的
   （3）所有为 null 的叶子结点的颜色是黑的
   （4）如果此结点是红的，那么它的两个孩子结点全部都是黑的