右旋
Coddy AVL 树：数据结构系列 #10 课程的第 7 课，共 16 课。
当一个节点的左侧过高时，可以通过右旋来修复。将失衡的节点称为 y，它的左子节点称为 x。旋转会将 x 提升到 y 原来的位置：x 成为新的子树根节点，y 成为 x 的右子节点，而 x 原来的右子树（称为 T2）会重新连接为 y 新的左子节点，因为 T2 中的每个值仍然大于 x 且小于 y。
重新连接指针后，需要重新计算 y 和 x 的 height，先计算 y，因为它现在在树中的位置更低。
挑战
简单在 AVLTree 上编写方法 rotateRight(y)。令 x = y.left，并令 T2 = x.right。设置 x.right = y 和 y.left = T2，先重新计算 y 的 height，再计算 x 的 height，计算方式为 1 + max(getHeight(left), getHeight(right))，然后返回 x 作为新的子树根节点。
亲手试试
#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;
}
AVL 树：数据结构系列 #10中的所有课
自己练习： C 在线编译器