算法导论之平衡二叉树 - 删除[C语言] - c语言编程

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时

算法导论 之 平衡二叉树 - 删除[C语言](三)

四、处理结果

算法导论之平衡二叉树 - 删除[C语言](三)