深入解析AVL树:高效实现二叉平衡搜索树(2)

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 深入解析AVL树:高效实现二叉平衡搜索树

深入解析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;
}

推荐学习 https://xxetb.xetslk.com/s/p5Ibb

目录
相关文章
|
3月前
|
存储 缓存 自然语言处理
深度解析ElasticSearch:构建高效搜索与分析的基石
【9月更文挑战第8天】在数据爆炸的时代,如何快速、准确地从海量数据中检索出有价值的信息成为了企业面临的重要挑战。ElasticSearch,作为一款基于Lucene的开源分布式搜索和分析引擎,凭借其强大的实时搜索、分析和扩展能力,成为了众多企业的首选。本文将深入解析ElasticSearch的核心原理、架构设计及优化实践,帮助读者全面理解这一强大的工具。
209 7
|
5月前
|
存储 弹性计算 应用服务中间件
阿里云经济型e与通用算力型u1实例长效特价云服务器解析,性能与性价比的完美平衡
阿里云目前有两款深受个人和普通企业用户喜欢的特价云服务器,ECS 经济型e实例2核2G,3M固定带宽,40G ESSD Entry云盘,仅需99元1年。ECS u1实例2核4G,5M固定带宽,80G ESSD Entry盘,仅需199元1年。新老同享,活动期间新购、续费同价。很多用户关心这两款云服务器性能怎么样?本文将对阿里云2024年推出的特价云服务器进行深度解析,从性能、价格、适用场景等多个维度进行详细探讨,以供选择参考。
阿里云经济型e与通用算力型u1实例长效特价云服务器解析,性能与性价比的完美平衡
|
5月前
|
算法 C++
【C++高阶】高效搜索的秘密:深入解析搜索二叉树
【C++高阶】高效搜索的秘密:深入解析搜索二叉树
42 2
|
5月前
|
人工智能 自然语言处理 搜索推荐
阿里云搜索开发工作台:快速搭建AI语义搜索与RAG链路的深度解析
阿里云搜索开发工作台凭借其丰富的组件化服务和强大的模型能力,为企业快速搭建AI语义搜索及RAG链路提供了有力支持。通过该平台,企业可以灵活调用各种服务,实现高效的数据处理、查询分析、索引构建和文本生成等操作,从而大幅提升信息获取与处理能力。随着AI技术的不断发展,阿里云搜索开发工作台将继续优化和完善其服务,为企业数字化转型和智能化升级注入更强动力。
168 0
|
6月前
|
存储
深入解析AVL树:高效实现二叉平衡搜索树
深入解析AVL树:高效实现二叉平衡搜索树
27 1
|
6月前
|
存储 安全 Java
深入解析Java HashMap的高性能扩容机制与树化优化
深入解析Java HashMap的高性能扩容机制与树化优化
152 1
|
6月前
|
传感器 存储 SQL
ClickHouse(15)ClickHouse合并树MergeTree家族表引擎之GraphiteMergeTree详细解析
GraphiteMergeTree是ClickHouse用于优化Graphite数据存储和汇总的表引擎,适合需要瘦身和高效查询Graphite数据的开发者。它基于MergeTree,减少存储空间并提升查询效率。创建表时需包括Path、Time、Value和Version列。配置涉及pattern、regexp、function和retention,用于指定聚合函数和数据保留规则。文章还提供了建表语句示例和相关资源链接。
92 1
|
5月前
|
JavaScript
js 解析和操作树 —— 获取树的深度、提取并统计树的所有的节点和叶子节点、添加节点、修改节点、删除节点
js 解析和操作树 —— 获取树的深度、提取并统计树的所有的节点和叶子节点、添加节点、修改节点、删除节点
132 0
|
16天前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
45 2
|
2月前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
70 0

推荐镜像

更多