Linksrotation

Lektion 8 von 16 im Kurs AVL-Baum - Datenstrukturen-Serie #10 von Coddy.

Eine Linksrotation ist das Spiegelbild der Rechtsrotation, die Sie gerade geschrieben haben, und wird verwendet, wenn die rechte Seite eines Knotens zu hoch ist. Nennen Sie den unausgeglichenen Knoten x und sein rechtes Kind y. y wird die neue Teilbaum-Wurzel, x wird das linke Kind von y, und der alte linke Teilbaum von y (T2) wird als neues rechtes Kind von x wieder angehängt.

Dieselbe Regel für Höhen: Berechnen Sie zuerst x neu, dann y, da x jetzt der untere Knoten ist.

Aufgabe

Einfach

Schreiben Sie eine Methode rotateLeft(x) für AVLTree. Sei y = x.right und T2 = y.left. Setzen Sie y.left = x und x.right = T2, berechnen Sie die height von x und dann von y neu, und geben Sie y als neue Wurzel des Teilbaums zurück.

Probier es selbst

#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* x = Node_create(10);
            x->height = 3;
            Node* y = Node_create(20);
            y->height = 2;
            Node* t2 = Node_create(30);
            t2->height = 1;
            y->right = t2;
            x->right = y;
            Node* newRoot = AVLTree_rotateLeft(tree, x);
            printf("%d %d %d %d\n", newRoot->value, newRoot->height, newRoot->left->value, newRoot->right->value);
        }
        if (strcmp(line, "2") == 0) {
            Node* x = Node_create(20);
            x->height = 3;
            Node* y = Node_create(40);
            y->height = 2;
            y->left = Node_create(30);
            y->left->height = 1;
            y->right = Node_create(50);
            y->right->height = 1;
            x->left = Node_create(10);
            x->left->height = 1;
            x->right = y;
            Node* newRoot = AVLTree_rotateLeft(tree, x);
            printf("%d %d %d %d %d %d\n", newRoot->value, newRoot->height, newRoot->left->value, newRoot->right->value, newRoot->left->left->value, newRoot->left->right->value);
        }
    }
    return 0;
}