作者：禅与计算机程序设计艺术
1.简介
什么是红黑树？
红黑树（英语：Red–black tree）是一种自平衡二叉查找树，它在20世纪70年代由Richard McMeek教授发明，是一种高度组织的数据结构。该树是为了解决普通的二叉查找树在最坏情况下可能出现的严重性能问题而设计出来的。
为什么要用红黑树？
红黑树是一种复杂的平衡数据结构，它的效率不及其他平衡数据结构如AVL树或伸展树，但却比一般平衡二叉树更适合文件系统、数据库索引、缓存等需要大量动态查询的数据结构。因此，对于要求高效查找、插入删除元素的应用场合，红黑树是一个值得考虑的选择。
2.基本概念术语说明
2.1 节点定义
红色结点（red node）：如果一个节点是红色的，那么它左右子节点都是黑色的。 黑色结点（black node）：如果一个节点是黑色的，那么它左右子节点都是红色的或者都为空（NIL）。 叶子结点（leaf node）：如果一个节点没有孩子节点，那么它就是一个叶子结点。 空结点（NIL）：空结点是树中的一种特殊节点，它既没有键也没有值，表示一个空白位置。 路径长度（path length）：从根节点到某一节点所经过边的数量称作该节点的路径长度。<