二叉树、平衡二叉树、红黑树

树是具有“一对多”关系的、非线性存储结构的数据元素的集合。树的最坏时间复杂度是O(n).

二叉树是具有特殊性质的树，满足下面两个条件的树就是二叉树：

1. 
   
2. 本身是有序树
   
3. 树中包含的所有节点的度不能超过2（度是节点包含子树的数量）
   

二叉树的特殊性质：

1. 
   
2. 二叉树的第i层最多有2i−12^{i-1}2i−1个节点
   
3. 深度为K的二叉树，最多有2K2^K2K-1个节点
   
4. 二叉树中，终端结点数（叶子结点数）为n0n_0n0，度为2的结点数为n2n_2n2，则n0n_0n0=n2n_2n2+1。计算方法：
   

对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 n1），那么总结点 n=n0+n1+n2。同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的，即 B=n1+2n2。所以，n 用另外一种方式表示为 n=n1+2n2+1。两种方式得到的 n 值组成一个方程组，就可以得出 n0=n2+1。

满二叉树：每个非叶子节点的度都为2的二叉树

完全二叉树：除去最后一层的节点为满二叉树，且最后一层的节点依次从左到右排列的二叉树

平衡二叉树 是任何两个子树的高度差不超过1（平衡因子）的二叉树（可以是空树）。

平衡二叉树为了保持“完全平衡”，当由于增删数据发生不平衡时，会通过旋转达到平衡的目的。旋转方式：

• 
  
• 左旋
  

• 
  
• 右旋
  

红黑树是一种含有红黑节点，并能自平衡的二叉查找树。红黑树必须具有以下特性：

1. 
   
2. 所有节点必须是红色或黑色
   
3. 根节点是黑色
   
4. 所有叶子节点（NIL）都是黑色
   
5. 每个红色节点的两个子节点一定都是黑色
   
6. 每个节点到叶子节点的路径上，都包含相同数量的黑色节点
   
7. 如果一个节点为黑色，那么这个节点一定有两个子节点
   

红黑树是一种完全平衡的二叉查找树，如图，根节点的左子树明显比右子树高，但是左子树和右子树的黑色节点的层数是相等的，即属性5。每次添加、删除节点，红黑树会通过旋转和变色来保持自平衡，且旋转次数最多为3，复杂度是O(lgn)。

1. 
   
2. 从根节点开始查找，把根节点设置为当前节点
   
3. 若当前节点为null，返回null
   
4. 若当前节点不为null，用当前节点的Key和查找key对比
   
5. 若当前节点的key等于查找key，返回当前节点
   
6. 若当前节点的key大于查找key，设置当前节点的左子节点为当前节点，重复步骤2
   
7. 若当前节点的key小于查找key，设置当前节点的右子节点为当前节点，重复步骤2