Rotasi Kiri
Pelajaran 8 dari 16 dalam kursus Pohon AVL, Seri Struktur Data #10 di Coddy.
Rotasi kiri adalah cerminan dari rotasi kanan yang baru saja kamu tulis, digunakan ketika sisi kanan sebuah node terlalu tinggi. Sebut node yang tidak seimbang sebagai x dan anak kanannya sebagai y. y menjadi root subtree yang baru, x menjadi anak kiri y, dan subtree kiri lama y (T2) dipasang kembali sebagai anak kanan baru x.
Aturan tinggi tetap sama: hitung ulang x terlebih dahulu, lalu y, karena sekarang x adalah node yang lebih rendah.
Tantangan
MudahTulis sebuah method rotateLeft(x) pada AVLTree. Tetapkan y = x.right dan T2 = y.left. Tetapkan y.left = x dan x.right = T2, hitung ulang height dari x lalu y, dan kembalikan y sebagai root subtree yang baru.
Coba sendiri
#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;
}
Semua pelajaran di Pohon AVL, Seri Struktur Data #10
Latihan sendiri: Compiler C online