情形4:父节点P是红色而叔父节点U是黑色或缺少,并且新节点N是其
父节点P的右子节点而父节点P又是其父节点的左子节点。在这种情形
下,我们进行一次左旋转调换新节点和其父节点的角色;接着,我们按
情形5处理以前的父节点P以解决仍然失效的性质4。注意这个改变会
导致某些路径通过它们以前不通过的新节点N(比如图中1号叶子节
点)或不通过节点P(比如图中3号叶子节点),但由于这两个节点都
是红色的,所以性质5仍有效。
void insert_case4(node *n){
if(n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n->parent);
n = n->left;
} else if(n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(n->parent);
n = n->right;
}
insert_case5 (n);
}
情形5:父节点P是红色而叔父节点U是黑色或缺少,新节点N是
其父节点的左子节点,而父节点P又是其父节点G的左子节点。在
这种情形下,我们进行针对祖父节点G的一次右旋转;在旋转产
生的树中,以前的父节点P现在是新节点N和以前的祖父节点G的
父节点。我们知道以前的祖父节点G是黑色,否则父节点P就不可
能是红色(如果P和G都是红色就违反了性质4,所以G必须是黑
色)。我们切换以前的父节点P和祖父节点G的颜色,结果的树满足性质4。性质5也仍然保持满足,因为通过这
三个节点中任何一个的所有路径以前都通过祖父节点G,现在它们都通过以前的父节点P。在各自的情形下,这都
是三个节点中唯一的黑色节点。
void insert_case5(node *n){
n->parent->color = BLACK;
grandparent (n)->color = RED;
if(n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(grandparent(n));
} else {
/* Here, n == n->parent->right && n->parent == grandparent (n)->right */
rotate_left(grandparent(n));
}
}
注意插入实际上是原地算法,因为上述所有调用都使用了尾部递归。
删除
如果需要删除的节点有两个儿子,那么问题可以被转化成删除另一个只有一个儿子的节点的问题(为了表述方