深入解析AVL树：高效实现二叉平衡搜索树（1）https://developer.aliyun.com/article/1541698
4.右左双旋
先介绍右旋的实现
void right_rotate(node *up) { node *root = up->parent; node *down = up->right; if (down->left) { // 右旋时处理子节点的左子节点 up->right = down->left; down->left->parent = up; } // 调换上下位置 down->left = up; down->parent = root; up->parent = down; // height up->height = update_height(up); down->height = update_height(down); }
左旋和右旋的区别就在于，把上述代码的left和right字段调换位置
而左右和右左双旋就是进行两次旋转
因此，所有的旋转操作，只看这一段代码就够了，根据图示很好理解
修正代码：
void insert_fix(node *n) { while (n != tree->root) { update_height(n); int balance = get_balance(n); if (balance > 1) { if (get_balance(n->left) < 0) { // 考虑需要左右双旋的情况 left_rotate(n->left); } right_rotate(n); } else if (balance < -1) { if (get_balance(n->right) > 0) { // 考虑右左双旋 right_rotate(n->right); } left_rotate(n); } n = n->parent; } }
delete和insert的修正代码相同
修正逻辑如下：
1.从叶子节点开始判断平衡条件
2.对于不平衡的节点，根据get_balance的值判断需要左旋还是右旋
3.判断不平衡节点的子节点是否平衡，因为上一次旋转操作可能会造成其兄弟节点不平衡
完整代码
#include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #define MAX(a,b) (a > b) ? (a) : (b) // 节点 typedef struct node { int key; int height; struct node *parent; struct node *left; struct node *right; } node; struct tree{ node *root; node *min; node *max; }; struct tree *tree; // 创建新节点 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; } #if 0 // 节点高度，递归 int height(node *n) { if (n == NULL) return 0; if (n->left == NULL && n->right == NULL) { return 1; } else { n->height = MAX(height(n->left), height(n->right)) + 1; } return n->height; } #endif // 节点高度 int height(node *n) { return n ? n->height : 0; } // 更新节点高度 int update_height(node *n) { 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; } // 左旋 void left_rotate(node *up) { node *root = up->parent; node *down = up->left; // left child if (down->right) { // down's right will be up's left up->left = down->right; down->right->parent = up; } down->right = up; down->parent = root; up->parent = down; // height up->height = update_height(up); down->height = update_height(down); } // 右旋 void right_rotate(node *up) { node *root = up->parent; node *down = up->right; if (down->left) { up->right = down->left; down->left->parent = up; } down->left = up; down->parent = root; up->parent = down; // height up->height = update_height(up); down->height = update_height(down); } #if 0 int get_balance(node *n) { return n ? update_height(n->left) - update_height(n->right) : 0; } #endif int get_balance(node *n) { // 左右子节点高度差 if (n == NULL) return 0; if (n->left == NULL && n->right == NULL) { return 0; } else if (n->left == NULL) { return update_height(n->right); } else if (n->right == NULL) { return update_height(n->left); }else { return update_height(n->left) - update_height(n->right); } } void insert_fix(node *n) { while (n != tree->root) { update_height(n); int balance = get_balance(n); if (balance > 1) { if (get_balance(n->left) < 0) { // 考虑需要右左双旋的情况 right_rotate(n->left); } left_rotate(n); } else if (balance < -1) { if (get_balance(n->right) > 0) { // 考虑左右双旋 left_rotate(n->right); } right_rotate(n); } n = n->parent; } } void delete_fix(node *n) { while (n->parent != NULL) { // 根节点也要修正 update_height(n); int balance = get_balance(n); if (balance > 1) { if (get_balance(n->left) < 0) { // 考虑需要右左双旋的情况 right_rotate(n->left); } left_rotate(n); } else if (balance < -1) { if (get_balance(n->right) > 0) { // 考虑左右双旋 left_rotate(n->right); } right_rotate(n); } n = n->parent; } } 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); } 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; // 删除后，返回根节点 } 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; } int main() { tree = (struct tree *)malloc(sizeof(struct tree)); memset(tree, 0, sizeof(*tree)); // 测试代码 int keys[] = {20, 4, 26, 3, 9, 15, 30}; for (int i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) { node *n = create_node(keys[i]); insert(tree->root, n); } printf("Root: %d\n", tree->root->key); printf("Min: %d\n", tree->min->key); printf("Max: %d\n", tree->max->key); // 删除节点 delete(tree->root, search_node(9)); printf("Root after deletion: %d\n", tree->root->key); printf("Min after deletion: %d\n", tree->min->key); printf("Max after deletion: %d\n", tree->max->key); // 清理树 while (tree->root != NULL) { tree->root = delete(tree->root, tree->root); } free(tree); return 0; }
