0

AVL ツリーの次のコードを理解しようとしていますが、問題があります。木が重いままだと右回転することを知っています。右重い場合も同様で、左回転します。以下のコードを理解する上で、誰かが説明したり、正しい方向に向けてくれたりしていただければ幸いです。

static void avl_rotate_right(TLDList *tld, TLDNode *node) {
    if (node->parent != NULL) {
        if (node->parent->left == node)
            node->parent->left = node->left;
        else
            node->parent->right = node->left;
    } else
        tld->root = node->left;

    node->left->parent = node->parent;
    node->parent = node->left;
    node->left = node->left->right;

    if (node->left != NULL)
        node->left->parent = node;
    node->parent->right = node;
}
4

1 に答える 1

0

基本的に、このコードは、回転するノードがルートかどうかをチェックしています。その場合、ルートは以前のルートの左の子になるように再割り当てされます。回転されるノードがルートではなく、回転されるノードが左の子である場合、それはそれ自身の左の子に置き換えられます。右の子である場合、親ノードの右の子はノードの左の子に置き換えられます。

次に、ノードの左の子の親がノードの親になるように割り当てられます。次に、ノードの親がノードの左の子として割り当てられます。次に、ノードの左の子が、ノードの左の子の右の子になるように割り当てられます。ノードの左の子が null でない場合、ノードの左の子の親がノードに割り当てられます。ノードの左の子が null の場合、ノードの親の右の子がノードに設定されます。

役に立った？

于 2013-10-26T09:43:13.933 に答える