> 引自：[https://www.jianshu.com/p/bad1e3f26466](https://www.jianshu.com/p/bad1e3f26466) 红黑树是一种非完美平衡的自平衡二叉树，在搜索时经常使用，它有以下五个规则： * 所有节点都有颜色，要么是红色，要么是黑色 * 根节点是黑色的 * 所有空节点（NIL）都是黑色的空节点 * 红色节点的子节点必须是黑色的(红色节点不能连续） * 任何一个节点到它的叶子节点包含相同的黑色节点