什么是“平衡二叉查找树”？

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。

如何定义一棵“红黑树”？

• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

为什么说红黑树是“近似平衡”的？

“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

左旋

围绕某个节点的左旋

右旋

围绕某个节点的右旋

插入操作的平衡调整

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。所以，关于插入操作的平衡调整，有这样两种特殊情况，但是也都非常好处理。

• 如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
• 如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。