概述：本文介绍AVL树的实现，从零构建一颗AVL树，以及对应的插入、删除、旋转操作
什么是AVL树？
AVL树是带有平衡条件的二叉查找树，二叉查找树又区别于二叉树：保证有序
这个平衡条件是每个节点的左右子树高度差不超过 1
一、AVL树节点设计：
typedef struct node { int key; // 节点存储的数据 int height; // 节点在树中的高度 struct node *parent; // 指向其父节点的指针 struct node *left; // 指向其左子节点 struct node *right; // 指向其右子节点 } node;
这就是构建一颗AVL树的最小单位：节点
其中key是node可以存储的数据，height则用来保存节点的高度信息，其余的三个指针用来构建AVL树
此外，为了提高效率，我们维护一个结构体对象，用来指示整棵树的基本信息
struct tree{ node *root; // 整棵树的根节点 node *min; // 整棵搜索树中的最小节点 node *max; // 整颗搜索树中的最大节点 };
需要注意的是，每对AVL树做一次修改，都有可能改变这些指针，因此在后续的insert、delete等操作的设计时，需要考虑到这一点
二、初始化和辅助函数
对于每一个节点，它的声明周期从分配空间并初始化开始：
// 创建新节点 node* create_node(int k) { // 申请空间 node* node = (struct node *)malloc(sizeof(struct node)); if (!node) return NULL; node->key = k; node->parent = NULL; node->left = NULL; node->right = NULL; node->height = 1; // 默认最小高度为 1 return node; }
可以看到，创建一个节点只需要指定其key值，因为在创建之初，只有这一个属性是确定的
三个指针都应该被初始化为NULL，避免内存访问错误。
获取节点的高度：
// 节点高度 int height(node *n) { // 获取当前height return n ? n->height : 0; } // 更新节点高度 int update_height(node *n) { // 递归，一个节点的高度是其左右子节点的高度中最大值 + 1 if (n != NULL) { n->height = MAX(height(n->left), height(n->right)) + 1; } return n->height; }
找到最小节点、最大节点、根节点
node * find_min(node *root) { if (root == NULL) return root; node *cur = root; while (!(cur->left == NULL && cur->right == NULL)) { // 最小节点在左子树上 cur = cur->left; } return cur; } node * find_max(node *root) { if (root == NULL) return root; node *cur = root; while (!(cur->left == NULL && cur->right == NULL)) { // 最大节点在右子树上 cur = cur->right; } return cur; } node * find_root(node *n) { node *cur = n; while (cur->parent != NULL) { cur = cur->parent; } return cur; }
其中根节点的查找很简单，给定任意一个节点就能找到整棵树的根节点
计算一个节点的左右子树高度差（用于判断平衡条件）
int get_balance(node *n) { return n ? update_height(n->left) - update_height(n->right) : 0; }
高度差的计算默认使用 左子树高度 - 右子树高度
根据key查找一个节点：
node * search_node(int key) { node * temp = tree->root; while (!(temp->left == NULL && temp->right == NULL)) { if (key < temp->key) temp = temp->left; else if (key > temp->key) temp = temp->right; else return temp; } return NULL; }
三、插入、删除、旋转
1.插入一个节点
插入一个节点有以下几种情况：
a. 根节点为空，则待插入节点为根节点
b. 根节点不为空，则待插入节点将作为叶子节点
void insert(node *root, node *node) { if (node == NULL) return; // 根节点为空的情况 if (root == NULL) { root = node; tree->root = node; // 更新全局 root tree->min = node; tree->max = node; return; } // 根节点不为空 struct node *cur = root; int k = node->key; // 遍历找到待插入节点的父节点 while (!(cur->left == NULL && cur->right == NULL)) { if (k <= cur->key) { cur = cur->left; } else { cur = cur->right; } } // 插入到父节点下 if (k <= cur->key) { cur->left = node; node->parent = cur; } else { cur->right = node; node->parent = cur; } insert_fix(node); tree->min = find_min(tree->root); tree->max = find_max(tree->root); }
其中的insert_fix()函数是用来修正插入后造成的树不平衡问题，接下来会介绍
2.删除一个节点
删除一个节点比较复杂，可能有以下几种情况：
1.待删除节点是叶子节点，直接删除
2.待删除节点有一个子节点
3.待删除节点有左右两个子节点
注意第三种情况：
使用待删除节点的右子树的最小值或左子树的最大值来替换的原因是，右子树的最小节点一定是叶子节点，且大于待删除节点的右子节点，这个叶子节点在被替换到待删除节点的位置后，它的删除操作很简单
node* delete(node *root, node* n) { if (n == NULL) return NULL; node *temp; if (root == NULL) printf("target is not found\n"); else { if (n->key < root->key) root->left = delete(root->left, n); // 在左子树递归查找删除 else if (n->key > root->key) root->right = delete(root->right, n); // 在右子树递归查找删除 else { // 删除当前根节点 if (root->left && root->right) { // 被删除节点有左右两个子节点 temp = find_min(root->right); // 用右子树的最小节点替换被删除节点 root->key = temp->key; // 替换被删除节点 root->right = delete(root->right, temp); // 删除用作替换的节点 } else { // 被删除节点只有一个或无子节点 temp = root; if (root->left == NULL) root = root->right; else root = root->left; free (temp); // 被删除的节点 } } } update_height(root); delete_fix(find_min(tree->root)); delete_fix(find_max(tree->root)); tree->root = find_root(tree->root); update_height(tree->root); tree->min = find_min(tree->root); tree->max = find_max(tree->root); return root; // 删除后，返回根节点 }
左右单旋转、左右双旋转
1.右单旋
2.左单旋
3.左右双旋
深入解析AVL树：高效实现二叉平衡搜索树（2）
