定义一棵“红黑树”
红黑树中的节点，一类被标记为黑色，一类被标记为红色，除此之外，一颗红黑树还需要满足：
1 根节点是黑色的。
2 每个叶子节点都是黑色的空节点，也就是说，叶子节点不存储数据。
3 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开。
4 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。
红黑树的近似平衡
平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。
总结
红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似
，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是
。