右回転

Coddyの「AVL Tree - データ構造シリーズ #10」コースのレッスン 7/16。

ノードの左側が高すぎる場合、右回転によって修正します。不均衡なノードを y、その左の子を x と呼びます。回転によって x が y の位置に昇格します。x が新しい部分木の根になり、y は x の右の子になります。そして、x の元の右部分木（T2 と呼びます）は、T2 内のすべての値が x より大きく y より小さいままであるため、y の新しい左の子として再接続されます。

ポインタを再接続した後、y と x の両方の height を再計算する必要があります。y は木の中でより低い位置になったため、先に y を計算します。

チャレンジ

簡単

AVLTree に rotateRight(y) メソッドを記述してください。x = y.left および T2 = x.right とします。x.right = y および y.left = T2 を設定し、y の height、次に x の height を 1 + max(getHeight(left), getHeight(right)) として再計算し、新しいサブツリーのルートとして x を返します。

自分で試してみよう

#include <stdio.h>
#include <string.h>
#include "avltree.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        if (strcmp(line, "1") == 0) {
            Node* y = Node_create(30);
            y->height = 3;
            Node* x = Node_create(20);
            x->height = 2;
            Node* t1 = Node_create(10);
            t1->height = 1;
            x->left = t1;
            y->left = x;
            Node* newRoot = AVLTree_rotateRight(tree, y);
            printf("%d %d %d %d\n", newRoot->value, newRoot->height, newRoot->left->value, newRoot->right->value);
        }
        if (strcmp(line, "2") == 0) {
            Node* y = Node_create(50);
            y->height = 3;
            Node* x = Node_create(30);
            x->height = 2;
            x->left = Node_create(20);
            x->left->height = 1;
            x->right = Node_create(40);
            x->right->height = 1;
            y->left = x;
            y->right = Node_create(60);
            y->right->height = 1;
            Node* newRoot = AVLTree_rotateRight(tree, y);
            printf("%d %d %d %d %d %d\n", newRoot->value, newRoot->height, newRoot->left->value, newRoot->right->value, newRoot->right->left->value, newRoot->right->right->value);
        }
    }
    return 0;
}