1) 每个节点或者是黑色,或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]
(4) 如果一个节点是红色的,则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
因此插入操作的关键在于以下几点:
新插入的节点一定是红色的。(如果是黑色的,会破坏条件5)
如果新插入的节点的父亲是黑色的,则没有破坏任何性质,那么插入完成。
如果插入节点的父节点是红色, 破坏了性质4. 故插入算法就是通过重新着色或旋转, 来维持性质
插入新的数据(红色节点),一定要考虑他的叔叔的情况。并且,插入操作主要是维护颜色来保证树的平衡。将插入操作分为以下几种情况分别考虑:
case 1. 如果插入的节点是根节点,也就是说初始的红黑树为空,这是最简单的情况,直接将该节点标识成黑色即可。
case 2. 如果新插入的节点不是红黑树的根节点,如果新插入的节点的父节点是黑色的话,那么红黑树是不需要调整的。
case 3. 如果新插入的节点的父节点是红色的话,显然这里违反了红黑树中不能存在父节点和子节点同时为红色的性质。
叔节点为红色:修改祖父节点为红色,父节点及叔节点改为黑色。祖父节点再视为新加入节点与上层比对,保证红黑树不被破坏。
修改后:
叔节点为黑色:旋转,使父节点占据祖父节点位置,之后交换P与G的颜色:
旋转后: