Rotasi Kanan
Pelajaran 7 dari 16 dalam kursus Pohon AVL, Seri Struktur Data #10 di Coddy.
Ketika sisi kiri sebuah node terlalu tinggi, rotasi kanan memperbaikinya. Sebut node yang tidak seimbang sebagai y dan anak kirinya sebagai x. Rotasi ini mempromosikan x untuk menggantikan posisi y: x menjadi root subtree yang baru, y menjadi anak kanan x, dan subtree kanan lama milik x (sebut T2) dipasang kembali sebagai anak kiri baru y, karena setiap nilai di T2 masih lebih besar dari x dan lebih kecil dari y.
Setelah pointer dipasang kembali, tinggi y dan x perlu dihitung ulang, dengan y terlebih dahulu karena posisinya kini lebih rendah di dalam tree.
Tantangan
MudahTulis method rotateRight(y) pada AVLTree. Tetapkan x = y.left dan T2 = x.right. Tetapkan x.right = y dan y.left = T2, hitung ulang height milik y lalu x sebagai 1 + max(getHeight(left), getHeight(right)), kemudian kembalikan x 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* 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;
}
Semua pelajaran di Pohon AVL, Seri Struktur Data #10
Latihan sendiri: Compiler C online