插入
Coddy AVL 树：数据结构系列 #10 课程的第 9 课，共 16 课。
insert 一开始的操作和普通二叉搜索树插入相同：向下遍历并比较值，向左或向右走，然后把新节点放在找到的空槽位中（忽略重复值）。AVL 部分发生在回溯时：放置节点后，路径上的每个祖先都会重新计算自己的 height，并检查平衡因子。
如果某个节点变得不平衡，较重的一侧以及新值的插入位置共同决定适用的四种情况之一：左左和右右需要一次旋转，而左右和右左需要两次旋转，先通过内侧旋转拉直之字形，再进行外侧旋转。
挑战
中等在 AVLTree 上编写一个 insert(value) 方法（使用递归辅助函数是最简洁的做法）。像普通二叉搜索树（BST）一样插入 value，如果它已经存在，就忽略它。向上返回时，重新计算每个节点的高度和平衡因子；如果节点不平衡，就应用对应的旋转（或一对旋转），然后沿调用栈继续返回。
亲手试试
#include <stdio.h>
#include <string.h>
#include "avltree.h"
static void preorderValues(Node* node, int* vals, int* count) {
if (node == NULL) {
return;
}
vals[(*count)++] = node->value;
preorderValues(node->left, vals, count);
preorderValues(node->right, vals, count);
}
int main(void) {
AVLTree* tree = AVLTree_create();
char line[256];
while (fgets(line, sizeof(line), stdin) != NULL) {
line[strcspn(line, "\r\n")] = '\0';
char cmd[32];
int arg;
int parsed = sscanf(line, "%31s %d", cmd, &arg);
if (parsed >= 1 && strcmp(cmd, "insert") == 0) {
AVLTree_insert(tree, arg);
}
if (parsed >= 1 && strcmp(cmd, "preorder") == 0) {
int vals[10000];
int count = 0;
preorderValues(tree->root, vals, &count);
for (int i = 0; i < count; i++) {
if (i > 0) {
printf(" ");
}
printf("%d", vals[i]);
}
printf("\n");
}
if (parsed >= 1 && strcmp(cmd, "height") == 0) {
printf("%d\n", AVLTree_getHeight(tree, tree->root));
}
}
return 0;
}
AVL 树：数据结构系列 #10中的所有课
自己练习： C 在线编译器