红黑树和其他的平衡二叉查找树一样，比简单的二叉查找树实现复杂得多。不过这个代价通常是值得的，因为我们可以很明显地看到性能的改进。红黑树有两个存储方面的需求。 ·每一个节点需要存储其颜色，至少需要一个bit，但是事实上大多数实现都使用了至少一个字节。 ·每一个节点都必须有一个父节点的链接，这个在二叉查找树中是不需要的。 红黑树的根节点必须是空值的。程序员能够让所有的叶子节点的指针都指向这个单个空值节点。