关于树的一些基础理论请参照https://blog.51cto.com/4259297/1708154
由于红黑树异常复杂，所以单独成文。

概念

https://www.cnblogs.com/skywang12345/p/3245399.html
http://www.360doc.com/content/18/0904/19/25944647_783893127.shtml

红黑树也是一棵二叉搜索树，和AVL树是并列的层级。但是，注意红黑树并不是平衡二叉树
红黑树与平衡二叉树的区别？

特征：

（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

必须要知道的知识点

树的深度

https://blog.csdn.net/saltriver/article/details/54428750

树的类型

https://blog.csdn.net/linjpg/article/details/80910806

• 平衡二叉树
  它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

• 二叉搜索树（二叉查找树）
  它或者是一棵空树，或者是具有下列性质的二叉树：

  若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  它的左、右子树也分别为二叉排序树

• AVL树（平衡二叉搜索树）
  AVL树是平衡二叉树和二叉搜索树的合体，也叫做”平衡二叉搜索树“。
  特征：

  AVL树是一棵二叉搜索树。
  AVL树的左右子节点也是AVL树。
  AVL树拥有二叉搜索树的所有基本特点。

  每个节点的左右子节点（同一层的兄弟结点）的高度之差的绝对值最多为1，即平衡因子为范围为[-1,1]。

两个重要的操作

旋转

着色

二叉树的旋转、着色等操作相当的复杂，但是最终只有一个目的：将要处理的数据变成二叉树，再变成红黑树（满足它所有的特性）。