关于树的一些基础理论请参照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
https://zhuanlan.zhihu.com/p/370703859

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

特征：

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