Xoay phải
Bài học 7 trên 16 trong khóa học Cây AVL, chuỗi cấu trúc dữ liệu #10 của Coddy.
Khi nhánh trái của một nút quá cao, phép xoay phải sẽ khắc phục tình trạng này. Gọi nút mất cân bằng là y và nút con bên trái của nó là x. Phép xoay đưa x lên thay vị trí của y: x trở thành nút gốc mới của cây con, y trở thành nút con bên phải của x, còn cây con bên phải cũ của x (gọi là T2) được gắn lại làm nút con bên trái mới của y, vì mọi giá trị trong T2 vẫn lớn hơn x và nhỏ hơn y.
Sau khi nối lại các con trỏ, cần tính lại height của cả y và x, trước tiên là y vì giờ đây nó nằm thấp hơn trong cây.
Thử thách
DễViết phương thức rotateRight(y) trong AVLTree. Đặt x = y.left và T2 = x.right. Gán x.right = y và y.left = T2, tính lại height của y rồi đến x theo công thức 1 + max(getHeight(left), getHeight(right)), sau đó trả về x 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* 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;
}
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