Xoay trái
Bài học 8 trên 16 trong khóa học Cây AVL, chuỗi cấu trúc dữ liệu #10 của Coddy.
Phép xoay trái là hình ảnh phản chiếu của phép xoay phải bạn vừa viết, dùng khi nhánh phải của một nút quá cao. Gọi nút mất cân bằng là x và nút con bên phải của nó là y. y trở thành nút gốc mới của cây con, x trở thành nút con bên trái của y, còn cây con bên trái cũ của y (T2) được gắn lại làm nút con bên phải mới của x.
Quy tắc về chiều cao cũng tương tự: tính lại chiều cao của x trước, rồi đến y, vì giờ đây x nằm thấp hơn.
Thử thách
DễViết phương thức rotateLeft(x) trong AVLTree. Đặt y = x.right và T2 = y.left. Gán y.left = x và x.right = T2, tính lại height của x rồi đến y, sau đó trả về y làm gốc mới của cây con.
Tự làm thử
#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;
}
Tất cả bài học trong Cây AVL, chuỗi cấu trúc dữ liệu #10
Tự luyện tập: Trình biên dịch C online