平衡二叉树的应用举例

AVL 是一种自平衡二叉搜索树，其中任何节点的左右子树的高度之差不能超过 1。

AVL树的特点：

1、它遵循二叉搜索树的一般属性。

2、树的每个子树都是平衡的，即左右子树的高度之差最多为1。

3、当插入新节点时，树会自我平衡。因此，插入操作非常耗时。

AVL Tree的应用：

1、大多数内存中集和字典都使用 AVL 树进行存储。

2、数据库应用程序（插入和删除不太常见，但需要频繁的数据查找）也经常使用 AVL 树。

3、除了数据库应用程序之外，它还用于其他需要更好搜索的应用程序。

4、有序关联容器（集合、多集、映射和多映射）的大多数 STL 实现都使用红黑树而不是 AVL树。

#include <stdio.h>
#include <stdlib.h>

struct AVLnode
{
    int key;
    struct AVLnode *left;
    struct AVLnode *right;
    int height;
};
typedef struct AVLnode avlNode;

int max(int a, int b) { return (a > b) ? a : b; }

avlNode *newNode(int key)
{
    avlNode *node = (avlNode *)malloc(sizeof(avlNode));

    if (node == NULL)
        printf("!! Out of Space !!\n");
    else
    {
        node->key = key;
        node->left = NULL;
        node->right = NULL;
        node->height = 0;
    }

    return node;
}

int nodeHeight(avlNode *node)
{
    if (node == NULL)
        return -1;
    else
        return (node->height);
}

int heightDiff(avlNode *node)
{
    if (node == NULL)
        return 0;
    else
        return (nodeHeight(node->left) - nodeHeight(node->right));
}

/* 返回左子树中最小值的节点*/
avlNode *minNode(avlNode *node)
{
    avlNode *temp = node;

    while (temp->left != NULL) temp = temp->left;

    return temp;
}

void printAVL(avlNode *node, int level)
{
    int i;
    if (node != NULL)
    {
        printAVL(node->right, level + 1);
        printf("\n\n");

        for (i = 0; i < level; i++) printf("\t");

        printf("%d", node->key);

        printAVL(node->left, level + 1);
    }
}

avlNode *rightRotate(avlNode *z)
{
    avlNode *y = z->left;
    avlNode *T3 = y->right;

    y->right = z;
    z->left = T3;

    z->height = (max(nodeHeight(z->left), nodeHeight(z->right)) + 1);
    y->height = (max(nodeHeight(y->left), nodeHeight(y->right)) + 1);

    return y;
}

avlNode *leftRotate(avlNode *z)
{
    avlNode *y = z->right;
    avlNode *T3 = y->left;

    y->left = z;
    z->right = T3;

    z->height = (max(nodeHeight(z->left), nodeHeight(z->right)) + 1);
    y->height = (max(nodeHeight(y->left), nodeHeight(y->right)) + 1);

    return y;
}

avlNode *LeftRightRotate(avlNode *z)
{
    z->left = leftRotate(z->left);

    return (rightRotate(z));
}

avlNode *RightLeftRotate(avlNode *z)
{
    z->right = rightRotate(z->right);

    return (leftRotate(z));
}

avlNode *insert(avlNode *node, int key)
{
    if (node == NULL)
        return (newNode(key));

    /*二叉搜索树插入*/

    if (key < node->key)
        node->left =
            insert(node->left, key); /*递归插入左子树*/
    else if (key > node->key)
        node->right =
            insert(node->right, key); /*递归插入右子树*/

    /*计算节点高度*/
    node->height = (max(nodeHeight(node->left), nodeHeight(node->right)) + 1);

    /*检查平衡性*/
    int balance = heightDiff(node);

    /*左左*/
    if (balance > 1 && key < (node->left->key))
        return rightRotate(node);

    /*右右*/
    if (balance < -1 && key > (node->right->key))
        return leftRotate(node);

    /*左右*/
    if (balance > 1 && key > (node->left->key))
    {
        node = LeftRightRotate(node);
    }

    /*右左*/
    if (balance < -1 && key < (node->right->key))
    {
        node = RightLeftRotate(node);
    }

    return node;
}

avlNode *delete (avlNode *node, int queryNum)
{
    if (node == NULL)
        return node;

    if (queryNum < node->key)
        node->left =
            delete (node->left, queryNum); /*Recursive deletion in L subtree*/
    else if (queryNum > node->key)
        node->right =
            delete (node->right, queryNum); /*Recursive deletion in R subtree*/
    else
    {
        /*单节点或者没有子节点*/
        if ((node->left == NULL) || (node->right == NULL))
        {
            avlNode *temp = node->left ? node->left : node->right;

            /*没有子节点*/
            if (temp == NULL)
            {
                temp = node;
                node = NULL;
            }
            else /*单节点*/
                *node = *temp;

            free(temp);
        }
        else
        {
            /*两个孩子节点*/

            /*获取右子树最小值的节点*/
            avlNode *temp = minNode(node->right);
            node->key = temp->key; /*拷贝到根节点*/
            node->right =
                delete (node->right,
                        temp->key); /*删除右子树最小值的节点*/
        }
    }

    /*单节点*/
    if (node == NULL)
        return node;

    /*更新高度*/
    node->height = (max(nodeHeight(node->left), nodeHeight(node->right)) + 1);

    int balance = heightDiff(node);

    /*左左*/
    if ((balance > 1) && (heightDiff(node->left) >= 0))
        return rightRotate(node);

    /*左右*/
    if ((balance > 1) && (heightDiff(node->left) < 0))
    {
        node = LeftRightRotate(node);
    }

    /*右右*/
    if ((balance < -1) && (heightDiff(node->right) >= 0))
        return leftRotate(node);

    /*右左*/
    if ((balance < -1) && (heightDiff(node->right) < 0))
    {
        node = RightLeftRotate(node);
    }

    return node;
}

avlNode *findNode(avlNode *node, int queryNum)
{
    if (node != NULL)
    {
        if (queryNum < node->key)
            node = findNode(node->left, queryNum);
        else if (queryNum > node->key)
            node = findNode(node->right, queryNum);
    }

    return node;
}

void printPreOrder(avlNode *node)
{
    if (node == NULL)
        return;

    printf("  %d  ", (node->key));
    printPreOrder(node->left);
    printPreOrder(node->right);
}

void printInOrder(avlNode *node)
{
    if (node == NULL)
        return;
    printInOrder(node->left);
    printf("  %d  ", (node->key));
    printInOrder(node->right);
}

void printPostOrder(avlNode *node)
{
    if (node == NULL)
        return;
    printPostOrder(node->left);
    printPostOrder(node->right);
    printf("  %d  ", (node->key));
}

int main()
{
    int choice;
    int flag = 1;
    int insertNum;
    int queryNum;

    avlNode *root = NULL;
    avlNode *tempNode;

    while (flag == 1)
    {
        printf("\n\nEnter the Step to Run : \n");

        printf("\t1: Insert a node into AVL tree\n");
        printf("\t2: Delete a node in AVL tree\n");
        printf("\t3: Search a node into AVL tree\n");
        printf("\t4: printPreOrder (Ro L R) Tree\n");
        printf("\t5: printInOrder (L Ro R) Tree\n");
        printf("\t6: printPostOrder (L R Ro) Tree\n");
        printf("\t7: printAVL Tree\n");

        printf("\t0: EXIT\n");
        scanf("%d", &choice);

        switch (choice)
        {
        case 0:
        {
            flag = 0;
            printf("\n\t\tExiting, Thank You !!\n");
            break;
        }

        case 1:
        {
            printf("\n\tEnter the Number to insert: ");
            scanf("%d", &insertNum);

            tempNode = findNode(root, insertNum);

            if (tempNode != NULL)
                printf("\n\t %d Already exists in the tree\n", insertNum);
            else
            {
                printf("\n\tPrinting AVL Tree\n");
                printAVL(root, 1);
                printf("\n");

                root = insert(root, insertNum);
                printf("\n\tPrinting AVL Tree\n");
                printAVL(root, 1);
                printf("\n");
            }

            break;
        }

        case 2:
        {
            printf("\n\tEnter the Number to Delete: ");
            scanf("%d", &queryNum);

            tempNode = findNode(root, queryNum);

            if (tempNode == NULL)
                printf("\n\t %d Does not exist in the tree\n", queryNum);
            else
            {
                printf("\n\tPrinting AVL Tree\n");
                printAVL(root, 1);
                printf("\n");
                root = delete (root, queryNum);

                printf("\n\tPrinting AVL Tree\n");
                printAVL(root, 1);
                printf("\n");
            }

            break;
        }

        case 3:
        {
            printf("\n\tEnter the Number to Search: ");
            scanf("%d", &queryNum);

            tempNode = findNode(root, queryNum);

            if (tempNode == NULL)
                printf("\n\t %d : Not Found\n", queryNum);
            else
            {
                printf("\n\t %d : Found at height %d \n", queryNum,
                       tempNode->height);

                printf("\n\tPrinting AVL Tree\n");
                printAVL(root, 1);
                printf("\n");
            }

            break;
        }

        case 4:
        {
            printf("\nPrinting Tree preOrder\n");
            printPreOrder(root);

            break;
        }

        case 5:
        {
            printf("\nPrinting Tree inOrder\n");
            printInOrder(root);

            break;
        }

        case 6:
        {
            printf("\nPrinting Tree PostOrder\n");
            printPostOrder(root);

            break;
        }

        case 7:
        {
            printf("\nPrinting AVL Tree\n");
            printAVL(root, 1);

            break;
        }

        default:
        {
            flag = 0;
            printf("\n\t\tExiting, Thank You !!\n");
            break;
        }
        }
    }

    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/665859.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

第N3周：Pytorch文本分类入门

第N3周：Pytorch文本分类入门

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制 目录 本周任务: 文本分类流程图&#xff1a; 需要的环境&#xff1a; 数据集&#xff1a; TextClassificationModel模型介绍&#xff1a…
阅读更多...
Java基础语法——字符串（String/StringBuilder/Stringjoiner）

Java基础语法——字符串（String/StringBuilder/Stringjoiner）

String Java的String类是不可变的&#xff0c;意味着一旦创建&#xff0c;其值就不能被改变。String类提供了丰富的API来操作字符串。 以下是一些常用的方法&#xff1a; 构造方法&#xff1a; 有以下几种常见的&#xff1a; public class stringlearn {public static void…
阅读更多...
民国漫画杂志《时代漫画》第34期.PDF

民国漫画杂志《时代漫画》第34期.PDF

时代漫画34.PDF: https://url03.ctfile.com/f/1779803-1248636026-7e46c5?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了&#xff0c;截止1937年6月战争来临被迫停刊共发行了39期。 ps: 资源来源网络!
阅读更多...
flume-ng-sql | 支持JDK8+ | 支持Flume 1.11.0 | 使用 Kotlin 编写

flume-ng-sql | 支持JDK8+ | 支持Flume 1.11.0 | 使用 Kotlin 编写

文章目录 简介用法 简介 flume-ng-sql-source 作者已经停止维护了&#xff0c;并且已经不支持新版Flume&#xff0c;我们决定开启这一项目 flume-ng-sql。 用法 像 flume-ng-sql-source 一样将 flume-ng-sql 发行的 Jar 包导入lib下&#xff0c;必要时需要添加自己 MySQL 版本…
阅读更多...
IMU状态预积分代码实现 —— IMU状态预积分类

IMU状态预积分代码实现 —— IMU状态预积分类

IMU状态预积分代码实现 —— IMU状态预积分类 实现IMU状态预积分类 实现IMU状态预积分类 首先&#xff0c;实现预积分自身的结构。一个预积分类应该存储一下数据&#xff1a; 预积分的观测量 △ R ~ i j , △ v ~ i j , △ p ~ i j \bigtriangleup \tilde{R} _{ij},\bigtrian…
阅读更多...
【Python爬虫--scrapy+selenium框架】超详细的Python爬虫scrapy+selenium框架学习笔记（保姆级别的，非常详细）

【Python爬虫--scrapy+selenium框架】超详细的Python爬虫scrapy+selenium框架学习笔记（保姆级别的，非常详细）

六&#xff0c;selenium 想要下载PDF或者md格式的笔记请点击以下链接获取 python爬虫学习笔记点击我获取 Scrapyselenium详细学习笔记点我获取 Python超详细的学习笔记共21万字点我获取 1&#xff0c;下载配置 ## 安装&#xff1a; pip install selenium## 它与其他库不同…
阅读更多...
【C++】C++11新特性：列表初始化、声明、新容器、右值引用、万能引用和完美转发

【C++】C++11新特性：列表初始化、声明、新容器、右值引用、万能引用和完美转发

目录 一、列表初始化 1.1 { } 初始化 1.2 std::initializer_list 二、声明 2.1 auto 2.2 decltype 2.3 nullptr 三、新容器 四、右值引用和移动语义 4.1 左值和左值引用 4.2 右值和右值引用 4.3 左值引用与右值引用比较 4.4 右值引用使用场景和意义&#xff1a;移…
阅读更多...
AI能否代替ACE

AI能否代替ACE

什么是ACE ? 申请ACE需要以下条件: 1.发表与oracle相关的技术博客 2.参与Oracle相关的技术大会 3.对Oracle社区做出贡献。 这正好是AI应用的场景吗? 在一个群里有个群友质疑AI落地,以及应用领域? Kelvin:我一直在迷茫&#xff0c;学不好。这么多有趣AI 问题&…
阅读更多...
冯喜运：5.31晚间黄金原油行情分析及尾盘操作策略

冯喜运：5.31晚间黄金原油行情分析及尾盘操作策略

【黄金消息面分析】&#xff1a;周五&#xff08;5月31日&#xff09;&#xff0c;最新发布的数据显示&#xff0c;美国4月核心PCE物价指数月率录得0.2%&#xff0c;低于预期(0.3%)&#xff0c;经济学家认为&#xff0c;核心指数比整体指数更能反映通胀。除此之外&#xff0c;美…
阅读更多...
[openwrt-21.02]openwrt-21.02 make menuconfig不显示luci-app-firewall问题分析及解决方案

[openwrt-21.02]openwrt-21.02 make menuconfig不显示luci-app-firewall问题分析及解决方案

问题描述 make menuconfig在 在applications界面没有luci-app-firewall 问题分析 首先重新执行 ./scripts/feeds update -a ./scripts/feeds install -a 然后再次执行make menuconfig&#xff0c;依然不显示&#xff0c;所以不是feeds安装的问题 最后看到log有个openmptc…
阅读更多...
P3881

P3881

最小值最大 二分&#xff1a;枚举两个牛之间的最小距离&#xff0c;左端点是1&#xff0c;右端点是篱笆总长度。 Check数组&#xff1a; 如果两头牛之间距离是Mid不合法&#xff0c;则返回0&#xff08;false&#xff09;&#xff1b; 如果两头牛之间距离是Mid合法&#xf…
阅读更多...
Beamer中二阶导、一阶导数的显示问题

Beamer中二阶导、一阶导数的显示问题

Beamer中二阶导、一阶导数的显示问题 在beamer中表示 f ′ f f′和 f ′ ′ f f′′时发现导数符号距离 f f f很近 \documentclass{beamer} \usepackage{amsmath,amssymb}\begin{document} \begin{frame}\frametitle{Derivative}Derivative:\[f^{\prime}(x) \quad f \quad…
阅读更多...
基于安卓的虫害识别软件设计--（1）模型训练与可视化

基于安卓的虫害识别软件设计--（1）模型训练与可视化

引言 简介&#xff1a;使用pytorch框架&#xff0c;从模型训练、模型部署完整地实现了一个基础的图像识别项目计算资源&#xff1a;使用的是Kaggle&#xff08;每周免费30h的GPU&#xff09; 1.创建名为“utils_1”的模块 模块中包含&#xff1a;训练和验证的加载器函数、训练…
阅读更多...
C++ 特殊运算符

C++ 特殊运算符

一 赋值运算符 二 等号作用 三 优先级和结合顺序 四 左值和右值 五 字节数运算符 条件运算符 使用条件运算符注意 逗号运算符 优先级和结合顺序 总结
阅读更多...
【C++】问题及补充（2）

【C++】问题及补充（2）

string s2“hello word”;是怎么进行隐式类型转换的 在这里&#xff0c;"hello world"是一个C字符串常量&#xff0c;而s2是一个std::string类型的变量。当你将C字符串常量赋值给一个std::string类型的变量时&#xff0c;会发生隐式类型转换。编译器会将C字符串常量转…
阅读更多...
Vue常用自定义指令、纪录篇

Vue常用自定义指令、纪录篇

文章目录 一、元素尺寸发生变化时二、点击元素外自定义指令三、元素拖拽自定义指令四、防抖自定义指令五、节流自定义指令六、权限判断自定义指令 一、元素尺寸发生变化时 使用场景&#xff1a; 当元素的尺寸发生变化时需要去适配一些元素时。 或者在元素尺寸发生变化时要去适配…
阅读更多...
下载安装nvm，使用nvm管理node.js版本

下载安装nvm，使用nvm管理node.js版本

目录 一、下载安装nvm&#xff08;windows&#xff09; 二、使用nvm管理node.js版本 &#xff08;1&#xff09;nvm命令行 &#xff08;2&#xff09; 使用nvm管理node.js版本 ①查看nvm版本 ②显示活动的node.js版本 ③列出可供下载的node.js版本 ④安装node.js指定版本 ⑤列出…
阅读更多...
19.Redis之集群

19.Redis之集群

1.集群的基本介绍 集群 这个词.广义的集群,只要你是多个机器,构成了分布式系统, 都可以称为是一个"集群"前面主从结构,哨兵模式,也可以称为是"广义的集群”狭义的集群,redis 提供的集群模式, 这个集群模式之下,主要是要解决,存储空间不足的问题(拓展存储空间) …
阅读更多...
原生小程序一键获取手机号

原生小程序一键获取手机号

1.效果图 2.代码index.wxml <!-- 获取手机号 利用手机号快速填写的功能&#xff0c;将button组件 open-type 的值设置为 getPhoneNumber--><button open-type"getPhoneNumber" bindgetphonenumber"getPhoneNumber">获取手机号</button> …
阅读更多...
【再探】设计模式—访问者模式、策略模式及状态模式

【再探】设计模式—访问者模式、策略模式及状态模式

访问者模式是用于访问复杂数据结构的元素&#xff0c;对不同的元素执行不同的操作。策略模式是对于具有多种实现的算法&#xff0c;在运行过程中可动态选择使用哪种具体的实现。状态模式是用于具有不同状态的对象&#xff0c;状态之间可以转换&#xff0c;且不同状态下对象的行…
阅读更多...
最新文章

Copyright @ 2022~2023