当前位置: 首页 > news >正文

数据结构与算法复习AVL树插入过程

环境

$ cat /proc/version
Linux version 6.8.0-45-generic (buildd@lcy02-amd64-115) (x86_64-linux-gnu-gcc-13 (Ubuntu 13.2.0-23ubuntu4) 13.2.0, GNU ld (GNU Binutils for Ubuntu) 2.42) #45-Ubuntu SMP PREEMPT_DYNAMIC Fri Aug 30 12:02:04 UTC 2024
 

#include <stdio.h>
#include <stdlib.h>struct node
{int key;int height;struct node *left;struct node *right;
};int height(struct node *node)
{if(node == NULL){return 0;}return node->height;
}int max(int a, int b)
{return a > b ? a : b;
}
struct node *leftRotate(struct node *node)
{
/*1\3/23/1\2
*/struct node *root = node->right;node->right = root->left;root->left = node;node->height = max(height(node->left), height(node->right));root->height = max(height(root->left), height(root->right));return root;
}
struct node *rightRotate(struct node *node)
{struct node *root = node->left;node->left = root->right;root->right = node;node->height = max(height(node->left), height(node->right));root->height = max(height(root->left), height(root->right));return root;
}
struct node *insertNode(struct node *root, int key)
{
#if 0if(root == NULL){root = malloc(sizeof(*root));root->key = key;root->height = 1;root->left = NULL;root->right = NULL;return root;}if(key < root->key){root->left = insertNode(root->left, key);}else if(key > root->key){root->right = insertNode(root->right, key);}else{return root;}
#elsestruct node **tmp = &root;while(1){if((*tmp) == NULL){(*tmp) = malloc(sizeof(*root));(*tmp)->key = key;(*tmp)->height = 1;(*tmp)->left = NULL;(*tmp)->right = NULL;break;}else if(key < (*tmp)->key){tmp = &(*tmp)->left;}else if(key > (*tmp)->key){tmp = &(*tmp)->right;}else{return root;}}
#endifroot->height = max(height(root->left), height(root->right));int bf = height(root->left) - height(root->right);
/*3/2/1
*/if(bf > 1 && key < root->left->key){return rightRotate(root);}else if(bf < -1 && key > root->right->key){return leftRotate(root);}
/*3/1\2
*/else if(bf > 1 && key > root->left->key){root->left = leftRotate(root->left);return rightRotate(root);}else if(bf < -1 && key < root->right->key){root->right = rightRotate(root->right);return leftRotate(root);}else{}return root;
}void inOrder(struct node *node)
{if(node == NULL){return;}inOrder(node->left);printf("%d ", node->key);inOrder(node->right);
}
int main(int argc, char *argv[])
{struct node *root = NULL;root = insertNode(root, 0);root = insertNode(root, 1);
/*0\1
*/root = insertNode(root, 3);
/*0       0             1\       \           / \1       1         0   3\3
*/root = insertNode(root, 9);
/*0       0             1         1\       \           / \       / \1       1         0   3     0   3\                       \3                       9
*/root = insertNode(root, 2);
/*0       0             1         1             1\       \           / \       / \           / \1       1         0   3     0   3         0   3\                       \           / \3                       9         2   9
*/root = insertNode(root, 8);
/*0       0             1         1             1             1                  1                       3\       \           / \       / \           / \           / \                / \                     / \1       1         0   3     0   3         0   3         0   3              0   3                   1   8\                       \           / \           / \                / \                 / \   \3                       9         2   9         2   9              2   8               0   2   9/                    \8                      9
*/inOrder(root);printf("\n");return 0;
}

<完>

http://www.lryc.cn/news/501747.html

相关文章:

  • 小迪笔记第 五十天 文件包含漏洞 远程包含 本地包含 ctf练习题实战
  • 单片机:实现点阵汉字平滑滚动显示(附带源码)
  • C# 实现 10 位纯数字随机数
  • 分布式全文检索引擎ElasticSearch-基本概念介绍
  • 电子应用设计方案-49:智能拖把系统方案设计
  • 汽车免拆诊断案例 | 2014款保时捷卡宴车发动机偶尔无法起动
  • 电脑怎么设置通电自动开机(工控机)
  • MaxKB进阶:豆包大模型驱动的智能日报小助手
  • Python爬虫之使用xpath进行HTML Document文档的解析
  • 调度系统:使用 Airflow 对 Couchbase 执行 SQL 调度时的潜在问题
  • 【数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
  • 简单网页制作提升用户体验和客户转化
  • 数据类型(使用与定义)
  • VMware:CentOS 7.* 连不上网络
  • 日志分析详解
  • 【JavaWeb后端学习笔记】Maven项目管理
  • Docker--Docker Container(容器) 之 操作实例
  • Android前端签到web迁移到rust的axum的过程-签到的重构
  • 用户认证系统登录界面
  • Redis从入门到进阶(总结)
  • 【D3.js in Action 3 精译_044】5.1 饼图和环形图的创建(四):数据标签的添加
  • Linux的基本功能和命令
  • 【Spark】Spark的两种核心Shuffle工作原理详解
  • TCP 的文化内涵
  • ASP.NET |日常开发中读写XML详解
  • Less和SCSS,哪个更好用?
  • 第一个C++程序--(蓝桥杯备考版)
  • NanoLog起步笔记-7-log解压过程初探
  • 【MySQL 进阶之路】基础语法及优化技巧
  • 微信小程序做电子签名功能