结论

红黑树和其他的平衡二叉查找树一样，比简单的二叉查找树实现复杂得多。不过这个代价通常是值得的，因为我们可以很明显地看到性能的改进。红黑树有两个存储方面的需求。

·每一个节点需要存储其颜色，至少需要一个bit，但是事实上大多数实现都使用了至少一个字节。

·每一个节点都必须有一个父节点的链接，这个在二叉查找树中是不需要的。

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

红黑树的根节点必须是空值的。程序员能够让所有的叶子节点的指针都指向这个单个空值节点。