rent = node->parent;
switch(node->bf)
{
case LH: /* 左高: 右子树高度减1 树失去平衡 */
{
lchild = node->lchild;
switch(lchild->bf)
{
case EH: /* LL型: 向右旋转 */
case LH: /* LL型: 向右旋转 */
{
if(EH == lchild->bf)
{
*lower = false;
lchild->bf = RH;
node->bf = LH;
}
else
{
*lower = true;
lchild->bf = EH;
node->bf = EH;
}
avl_set_lchild(node, lchild->rchild);
avl_set_rchild(lchild, node);
avl_replace_child(tree, parent, node, lchild);
break;
}
case RH: /* LR型: 先向左旋转 再向右旋转 */
{
*lower = true;
lrchild = lchild->rchild;
switch(lrchild->bf)
{
case LH:
{
node->bf = RH;
lchild->bf = EH;
lrchild->bf = EH;
break;
}
case EH:
{
node->bf = EH;
lchild->bf = EH;
lrchild->bf = EH;
break;
}
case RH:
{
node->bf = EH;
lchild->bf = LH;
lrchild->bf = EH;
break;
}
}
avl_set_lchild(node, lrchild->rchild);
avl_set_rchild(lchild, lrchild->lchild);
avl_set_rchild(lrchild, node);
avl_set_lchild(lrchild, lchild);
avl_replace_child(tree, parent, node, lrchild);
break;
}
}
break;
}
case EH: /* 等高: 右子树高度减1 树高度不变 */
{
node->bf = LH;
*lower = false;
break;
}
case RH: /* 右高: 右子树高度减1 树变矮 */
{
node->bf = EH;
*lower = true;
break;
}
}
return AVL_SUCCESS;
}
代码5 右子树高度降低后 平衡化处理
/* # 检测节点的指针是否存在异常 # 很有效！ */
void avl_assert(avl_node_t *node)
{
if((NULL == node)
|| (NULL == node->parent))
{
return;
}
if((node->parent->lchild != node)
&& (node->parent->rchild != node))
{
assert(0);
}
if((node->parent == node->lchild)
|| (node->parent == node->rchild))
{
assert(0);
}
}
代码6 节点检测
四、处理结果 左图为原始平衡二叉树，随机删除多个节点后，得到右图。通过观察可知右图依然是一棵平衡二叉树。
图1 测试结果
―― 邹祁峰
2013年12月20日 12时
|