数据结构中常见的树

发布时间：2026/7/13 8:17:49

数据结构中常见的树

1. BST（二叉搜索树）

它是什么：一种有顺序的二叉树。它规定：左边的孩子必须比父节点小，右边的孩子必须比父节点大（左<根<右）。核心特征：它就是为了“快速查找”而设计的，理想情况下找东西像二分查找一样快。致命弱点：如果插入顺序是1,2,3,4，它就会变成一条“瘸腿”的链表，失去快速查找的优势。

简单实现：

#include <stdio.h> #include <stdlib.h> // 节点结构 typedef struct BSTNode { int key; struct BSTNode *left, *right; } BSTNode; // 创建新节点 BSTNode* bst_create_node(int key) { BSTNode *node = (BSTNode*)malloc(sizeof(BSTNode)); node->key = key; node->left = node->right = NULL; return node; } // 插入（递归） BSTNode* bst_insert(BSTNode *root, int key) { if (root == NULL) return bst_create_node(key); if (key < root->key) root->left = bst_insert(root->left, key); else if (key > root->key) root->right = bst_insert(root->right, key); // 相等则忽略 return root; } // 查找 BSTNode* bst_search(BSTNode *root, int key) { if (root == NULL || root->key == key) return root; if (key < root->key) return bst_search(root->left, key); return bst_search(root->right, key); } // 中序遍历（有序输出） void bst_inorder(BSTNode *root) { if (root) { bst_inorder(root->left); printf("%d ", root->key); bst_inorder(root->right); } }

2. AVL 树（严格平衡二叉搜索树）

它是什么：一种极度自律的 BST。它在 BST 的基础上加了一条死规矩：任意节点的左右子树高度差不能超过 1。核心特征：为了守住这个规矩，它在插入或删除数据时，会不停地“旋转”调整自己，确保永远不瘸腿。代价：因为管得太严，插入删除时旋转操作很多，比较耗费性能。

#include <stdio.h> #include <stdlib.h> // AVL节点 typedef struct AVLNode { int key, height; struct AVLNode *left, *right; } AVLNode; // 获取高度 int avl_height(AVLNode *node) { return node ? node->height : 0; } // 更新节点高度 void avl_update_height(AVLNode *node) { int hL = avl_height(node->left); int hR = avl_height(node->right); node->height = (hL > hR ? hL : hR) + 1; } // 平衡因子 int avl_balance_factor(AVLNode *node) { return avl_height(node->left) - avl_height(node->right); } // 右旋 AVLNode* avl_rotate_right(AVLNode *y) { AVLNode *x = y->left; AVLNode *T2 = x->right; x->right = y; y->left = T2; avl_update_height(y); avl_update_height(x); return x; } // 左旋 AVLNode* avl_rotate_left(AVLNode *x) { AVLNode *y = x->right; AVLNode *T2 = y->left; y->left = x; x->right = T2; avl_update_height(x); avl_update_height(y); return y; } // 插入（带平衡调整） AVLNode* avl_insert(AVLNode *root, int key) { if (root == NULL) { AVLNode *node = (AVLNode*)malloc(sizeof(AVLNode)); node->key = key; node->height = 1; node->left = node->right = NULL; return node; } if (key < root->key) root->left = avl_insert(root->left, key); else if (key > root->key) root->right = avl_insert(root->right, key); else return root; // 重复 avl_update_height(root); int balance = avl_balance_factor(root); // LL if (balance > 1 && key < root->left->key) return avl_rotate_right(root); // RR if (balance < -1 && key > root->right->key) return avl_rotate_left(root); // LR if (balance > 1 && key > root->left->key) { root->left = avl_rotate_left(root->left); return avl_rotate_right(root); } // RL if (balance < -1 && key < root->right->key) { root->right = avl_rotate_right(root->right); return avl_rotate_left(root); } return root; } // 查找同BST，略

3. 红黑树（近似平衡二叉搜索树）

它是什么：一种“佛系”平衡的 BST。它不要求高度差绝对为 1，而是给节点涂上“红色”或“黑色”，通过几条简单的颜色规则（比如不能有两个红节点相连），来保证最长路径不超过最短路径的 2 倍。核心特征：它也是平衡的，但不像 AVL 那么严格。因此它查找稍慢一点点（因为没那么平整），但插入和删除快得多。所以它成了工程界（如 C++ 的std::map）最常用的平衡树。

#include <stdio.h> #include <stdlib.h> // 颜色定义 typedef enum { RED, BLACK } Color; // 节点结构 typedef struct RBNode { int key; Color color; struct RBNode *left, *right, *parent; } RBNode; // 创建红色节点（新插入默认红色） RBNode* rb_create_node(int key) { RBNode *node = (RBNode*)malloc(sizeof(RBNode)); node->key = key; node->color = RED; node->left = node->right = node->parent = NULL; return node; } // 左旋 void rb_rotate_left(RBNode **root, RBNode *x) { RBNode *y = x->right; x->right = y->left; if (y->left) y->left->parent = x; y->parent = x->parent; if (x->parent == NULL) *root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->left = x; x->parent = y; } // 右旋 void rb_rotate_right(RBNode **root, RBNode *y) { RBNode *x = y->left; y->left = x->right; if (x->right) x->right->parent = y; x->parent = y->parent; if (y->parent == NULL) *root = x; else if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; x->right = y; y->parent = x; } // 插入修复 void rb_insert_fixup(RBNode **root, RBNode *z) { while (z->parent && z->parent->color == RED) { if (z->parent == z->parent->parent->left) { RBNode *y = z->parent->parent->right; // 叔叔 if (y && y->color == RED) { // 情况1：叔叔为红 -> 变色 z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->right) { // 情况2：z是右孩子 -> 左旋 z = z->parent; rb_rotate_left(root, z); } // 情况3：z是左孩子 -> 右旋+变色 z->parent->color = BLACK; z->parent->parent->color = RED; rb_rotate_right(root, z->parent->parent); } } else { // 对称情况，父节点是右孩子 RBNode *y = z->parent->parent->left; if (y && y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->left) { z = z->parent; rb_rotate_right(root, z); } z->parent->color = BLACK; z->parent->parent->color = RED; rb_rotate_left(root, z->parent->parent); } } } (*root)->color = BLACK; } // 插入 void rb_insert(RBNode **root, int key) { RBNode *z = rb_create_node(key); RBNode *y = NULL; RBNode *x = *root; while (x) { y = x; if (z->key < x->key) x = x->left; else if (z->key > x->key) x = x->right; else { free(z); return; } // 重复 } z->parent = y; if (y == NULL) *root = z; else if (z->key < y->key) y->left = z; else y->right = z; rb_insert_fixup(root, z); } // 查找（同BST，但可增加parent遍历，此处略）

4. B- 树（B 树，多路平衡搜索树）

注意：中间的-是连接符，念“B 树”，不是“B减树”！它是什么：一棵“胖墩墩”的多叉树。它不再是“二叉树”（一个节点只有俩孩子），而是一个节点可以拥有几十上百个孩子。核心特征：它把数据（Key 和真实记录）分散存放在所有节点（根、枝、叶）中。它长得非常矮，专门用来解决磁盘读写慢的问题（树越矮，查磁盘次数越少）。

#include <stdio.h> #include <stdlib.h> #define M 4 // 阶数（每节点最多M-1个关键字，M个孩子） #define MIN_KEY (M/2 - 1) // 最小关键字个数（除根外） // B树节点 typedef struct BNode { int n; // 当前关键字个数 int keys[M-1]; // 关键字数组 struct BNode *child[M]; // 孩子指针数组（M个） int is_leaf; } BNode; // 创建节点 BNode* b_create_node(int leaf) { BNode *node = (BNode*)malloc(sizeof(BNode)); node->n = 0; node->is_leaf = leaf; for (int i = 0; i < M; i++) node->child[i] = NULL; return node; } // 分裂根/节点 void b_split_child(BNode *parent, int idx) { BNode *y = parent->child[idx]; BNode *z = b_create_node(y->is_leaf); z->n = MIN_KEY; // 拷贝后半部分关键字到z for (int j = 0; j < MIN_KEY; j++) z->keys[j] = y->keys[j + MIN_KEY + 1]; // 如果不是叶子，拷贝孩子 if (!y->is_leaf) { for (int j = 0; j <= MIN_KEY; j++) z->child[j] = y->child[j + MIN_KEY + 1]; } y->n = MIN_KEY; // 调整y // 在parent中插入新的key（y->keys[MIN_KEY]）和z for (int j = parent->n; j > idx; j--) { parent->child[j+1] = parent->child[j]; parent->keys[j] = parent->keys[j-1]; } parent->child[idx+1] = z; parent->keys[idx] = y->keys[MIN_KEY]; parent->n++; } // 向非满节点插入 void b_insert_nonfull(BNode *node, int key) { int i = node->n - 1; if (node->is_leaf) { // 找到位置并插入 while (i >= 0 && key < node->keys[i]) { node->keys[i+1] = node->keys[i]; i--; } node->keys[i+1] = key; node->n++; } else { // 找到孩子位置 while (i >= 0 && key < node->keys[i]) i--; i++; if (node->child[i]->n == M-1) { b_split_child(node, i); if (key > node->keys[i]) i++; } b_insert_nonfull(node->child[i], key); } } // 插入入口 BNode* b_insert(BNode *root, int key) { if (root == NULL) { root = b_create_node(1); root->keys[0] = key; root->n = 1; return root; } if (root->n == M-1) { BNode *new_root = b_create_node(0); new_root->child[0] = root; b_split_child(new_root, 0); int i = (key > new_root->keys[0]) ? 1 : 0; b_insert_nonfull(new_root->child[i], key); return new_root; } else { b_insert_nonfull(root, key); return root; } } // 查找（返回是否找到） int b_search(BNode *root, int key) { if (root == NULL) return 0; int i = 0; while (i < root->n && key > root->keys[i]) i++; if (i < root->n && key == root->keys[i]) return 1; if (root->is_leaf) return 0; return b_search(root->child[i], key); }

5. B+ 树（B 树升级版）

它是什么：B 树的魔改版。它规定：所有的真实数据都只放在最底层的叶子节点上，上层的内部节点只当作“路牌”（只存索引，不存数据）。核心特征：所有的叶子节点（数据页）还通过链表串在一起。它也是多叉树，比 B 树更矮、更胖。它是谁：这就是MySQL 数据库索引的底层真身。

#include <stdio.h> #include <stdlib.h> #define M 4 // 阶数（内部节点最多M-1个索引，叶子最多M-1个数据） #define MIN_KEY (M/2 - 1) // 前置声明 struct BPlusNode; // 叶子节点 typedef struct BPlusLeaf { int n; int keys[M-1]; // 存储数据键值 struct BPlusLeaf *next; // 叶子链表指针 // 实际数据可放在这里或额外指针，此处仅存储键 } BPlusLeaf; // 内部节点 typedef struct BPlusInternal { int n; int keys[M-1]; // 索引键 struct BPlusNode *child[M]; // 孩子指针 } BPlusInternal; // 联合节点（简化，使用void*或分别处理，这里用统一结构但区分类型） typedef struct BPlusNode { int is_leaf; union { BPlusLeaf leaf; BPlusInternal internal; } u; } BPlusNode; // 创建叶子节点 BPlusNode* bp_create_leaf() { BPlusNode *node = (BPlusNode*)malloc(sizeof(BPlusNode)); node->is_leaf = 1; node->u.leaf.n = 0; node->u.leaf.next = NULL; return node; } // 创建内部节点 BPlusNode* bp_create_internal() { BPlusNode *node = (BPlusNode*)malloc(sizeof(BPlusNode)); node->is_leaf = 0; node->u.internal.n = 0; for (int i = 0; i < M; i++) node->u.internal.child[i] = NULL; return node; } // 插入辅助：分裂叶子 void bp_split_leaf(BPlusNode *leaf, int key, int *mid_key, BPlusNode **new_leaf) { // 将原叶子中的keys和插入的key合并排序，再分成两半 int temp[M]; // 临时存储 int i, j; for (i = 0; i < leaf->u.leaf.n; i++) temp[i] = leaf->u.leaf.keys[i]; // 插入key（简单插入排序） i = leaf->u.leaf.n - 1; while (i >= 0 && key < temp[i]) { temp[i+1] = temp[i]; i--; } temp[i+1] = key; // 分裂 int split = (M-1 + 1) / 2; // 新叶子拿后半部分，旧叶子保留前半部分 *new_leaf = bp_create_leaf(); (*new_leaf)->u.leaf.n = (M-1 + 1) - split; for (i = 0; i < (*new_leaf)->u.leaf.n; i++) (*new_leaf)->u.leaf.keys[i] = temp[split + i]; leaf->u.leaf.n = split; for (i = 0; i < leaf->u.leaf.n; i++) leaf->u.leaf.keys[i] = temp[i]; // 维护叶子链表 (*new_leaf)->u.leaf.next = leaf->u.leaf.next; leaf->u.leaf.next = *new_leaf; // 上升的键为新叶子的第一个键 *mid_key = (*new_leaf)->u.leaf.keys[0]; } // 插入辅助：分裂内部节点 void bp_split_internal(BPlusNode *internal, int *mid_key, BPlusNode **new_internal) { // 类似B树分裂，但不复制第一个键（上升） // 简化实现：略去具体代码，原理同B树分裂但将中间键上升到父节点 // 实际需要将internal->keys[MIN_KEY]上升，右半部分创建新节点 // 这里仅示意 // ... } // 简化插入：仅展示叶子插入和内部节点分裂框架，完整实现较复杂，此处给出核心思路 // 实际B+树插入需要递归处理内部节点的分裂，此处省略

相关新闻

URP中GPU驱动超大规模动态草地渲染：Compute Shader与Instancing实战

URP中GPU驱动超大规模动态草地渲染：Compute Shader与Instancing实战

1. 项目概述&#xff1a;为什么我们需要“超大规模动态草地”&#xff1f;在开发开放世界、大型RPG或者任何需要丰富自然环境的游戏时&#xff0c;草地渲染一直是个让人又爱又恨的难题。爱的是它能为场景注入生机&#xff0c;恨的是它动辄就能让帧率“雪崩”。传统的做法&#…

2026/7/13 8:17:40
Navicat 外键设置 5 大常见错误排查：从 ERROR 1822 到 SET NULL 失败

Navicat 外键设置 5 大常见错误排查：从 ERROR 1822 到 SET NULL 失败

Navicat 外键设置 5 大常见错误排查&#xff1a;从 ERROR 1822 到 SET NULL 失败数据库设计中&#xff0c;外键约束是确保数据完整性的重要机制。作为一款广受欢迎的数据库管理工具&#xff0c;Navicat 提供了直观的界面来设置外键关系。但在实际操作中&#xff0c;开发者经常会…

2026/7/13 8:17:40
C++代码评审清单：规避系统级缺陷的实战指南

C++代码评审清单：规避系统级缺陷的实战指南

1. 项目概述&#xff1a;为什么我们需要一份C专属的评审清单&#xff1f;如果你写过几年C&#xff0c;尤其是在大型系统、游戏引擎、高频交易或者嵌入式领域摸爬滚打过&#xff0c;大概率经历过这样的深夜&#xff1a;系统在线上毫无征兆地崩溃&#xff0c;核心转储文件&#x…

2026/7/13 8:17:40

最新新闻

Java 观察者模式 3 种实现对比：原生接口 vs 自定义 vs Spring 事件机制

Java 观察者模式 3 种实现对比：原生接口 vs 自定义 vs Spring 事件机制

Java 观察者模式 3 种实现对比&#xff1a;原生接口 vs 自定义 vs Spring 事件机制在软件开发中&#xff0c;对象间的状态同步是个永恒话题。想象这样一个场景&#xff1a;当电商平台的商品价格变动时&#xff0c;需要实时通知库存系统、促销系统和用户终端。如果采用硬编码方式…

2026/7/13 11:38:30
DLSS Swapper终极指南：一键智能管理DLSS版本，免费提升游戏性能

DLSS Swapper终极指南：一键智能管理DLSS版本，免费提升游戏性能

DLSS Swapper终极指南&#xff1a;一键智能管理DLSS版本&#xff0c;免费提升游戏性能 【免费下载链接】dlss-swapper 项目地址: https://gitcode.com/GitHub_Trending/dl/dlss-swapper 还在为游戏帧率不稳定而烦恼吗&#xff1f;想轻松升级DLSS版本却不知如何操作&…

2026/7/13 11:38:30
从算法复杂度到人生选择：收敛速度和全局最优的矛盾

从算法复杂度到人生选择：收敛速度和全局最优的矛盾

从算法复杂度到人生选择&#xff1a;收敛速度和全局最优的矛盾 一、梯度下降算法里藏着的人生隐喻 梯度下降是深度学习中最基础的优化算法。它的核心思想很简单&#xff1a;每一步朝着当前梯度的负方向走一步。沿局部下降最快的方向前进&#xff0c;期望最终到达全局最低点。 但…

2026/7/13 11:38:30
网盘直链下载助手：告别下载限速，9大网盘一键获取真实链接

网盘直链下载助手：告别下载限速，9大网盘一键获取真实链接

网盘直链下载助手&#xff1a;告别下载限速&#xff0c;9大网盘一键获取真实链接 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 &#xff0c;支持 百度网盘 / 阿里云盘 / 中国移…

2026/7/13 11:38:30
ROS C++消息生成：从.msg定义到可发布订阅的完整流程

ROS C++消息生成：从.msg定义到可发布订阅的完整流程

1. 项目概述&#xff1a;为什么“消息生成”是ROS开发绕不开的第一道门槛刚接触ROS的人&#xff0c;常以为装完系统、跑通小乌龟就等于入门了。我带过十几期线下ROS实训班&#xff0c;几乎每届都有学员卡在“写完代码编译报错&#xff0c;提示找不到头文件”&#xff0c;或者“…

2026/7/13 11:38:30
2026 年 7 月乌鲁木齐黄金回收设备、报价、服务全维度测评｜六片区持证实体门店标准化交易深度指南 - 不晚生活号

2026 年 7 月乌鲁木齐黄金回收设备、报价、服务全维度测评｜六片区持证实体门店标准化交易深度指南 - 不晚生活号

2026 年 7 月国内贵金属行情持续高位运行，上海黄金交易所 AU9999 基准金价稳定 902 元 / 克，乌鲁木齐合规线下实体门店足金 999 统一回收定价 893 元 / 克。结合乌鲁木齐市场监管局上半年贵金属消费投诉统计，全市黄…

2026/7/13 11:37:54

日新闻

AI推荐结果怎么优化：适合深圳少儿素质培训机构的GEO服务商哪家好？全程零代码SAAS操作

AI推荐结果怎么优化：适合深圳少儿素质培训机构的GEO服务商哪家好？全程零代码SAAS操作

这两年&#xff0c;越来越多深圳地区的少儿素质培训机构开始关注 GEO。 原因很简单。过去家长找培训机构、找兴趣班、找素质教育课程&#xff0c;主要靠搜索引擎、短视频平台、社交平台种草和熟人推荐&#xff1b;现在越来越多深圳本地家长&#xff0c;已经开始直接在 AI 里提…

2026/7/13 0:00:25
开源本地智能体 OpenClaw 2.7.9 保姆级部署手册，零代码操控电脑重复工作

开源本地智能体 OpenClaw 2.7.9 保姆级部署手册，零代码操控电脑重复工作

&#x1f4d6;前言 OpenClaw&#xff0c;在开发者社区中常被亲切地称为"小龙虾"&#xff0c;是当前备受关注的开源 AI 智能体项目&#xff0c;其在 GitHub 平台上已累计获得超过 28 万星标。与常规的对话型 AI 工具不同&#xff0c;OpenClaw 能够理解自然语言指令&a…

2026/7/13 0:00:25
广氟 PTFE 高速线缆膜 —— 高端线缆绝缘材料新选择

广氟 PTFE 高速线缆膜 —— 高端线缆绝缘材料新选择

PTFE高速线缆膜的基本概念与特点 PTFE 高速线缆膜是以聚四氟乙烯树脂为原料&#xff0c;经膨化双向拉伸制成的多孔绝缘薄膜&#xff0c;作为高速高频通信线缆的核心介质材料&#xff0c;内部形成均匀连通的微孔结构&#xff0c;兼具极低介电常数与介电损耗&#xff0c;能有效降…

2026/7/13 0:00:25

周新闻

PlantUML 实战：5分钟将 UML 2.5 序列图转换为可执行代码草图

PlantUML 实战：5分钟将 UML 2.5 序列图转换为可执行代码草图

PlantUML 实战&#xff1a;5分钟将 UML 2.5 序列图转换为可执行代码草图 在软件开发过程中&#xff0c;清晰的系统设计往往比编码本身更为关键。传统拖拽式UML工具虽然直观&#xff0c;却常常成为效率杀手——频繁的鼠标操作打断设计思路&#xff0c;版本控制困难&#xff0c;…

2026/7/13 1:29:08
【RT-DETR涨点改进】29 动态Batch推理：让RT-DETR在低延迟下吃满GPU算力

【RT-DETR涨点改进】29 动态Batch推理：让RT-DETR在低延迟下吃满GPU算力

29 动态Batch推理：让RT-DETR在低延迟下吃满GPU算力 开篇故事 上个月帮一家安防厂商做项目优化，他们用RT-DETR做实时人流统计，部署在NVIDIA A10上。客户反馈说：“GPU利用率才30%，但延迟已经飙到40ms了，加人流量就丢帧。” 我远程一看，好家伙——生产环境里每个请求单独…

2026/7/13 1:29:10
Postman 环境变量实战：3种动态设置方法与CI/CD集成避坑指南

Postman 环境变量实战：3种动态设置方法与CI/CD集成避坑指南

Postman 环境变量高阶实战&#xff1a;动态管理与 CI/CD 深度集成在接口自动化测试领域&#xff0c;环境变量的灵活运用往往成为区分初级与高级测试工程师的关键能力。本文将深入探讨 Postman 环境变量的三种动态设置模式&#xff0c;并分享 Newman 在 CI/CD 流水线中的实战避坑…

2026/7/13 1:29:08

月新闻

[C++]内存管理：串顺序存储的内存回收

[C++]内存管理：串顺序存储的内存回收

在串&#xff08;字符串&#xff09;的顺序存储中&#xff0c;内存回收的方式取决于字符串的存储方式以及所使用的编程语言和相关库。以下以 C 为例进行说明&#xff0c;因为 C 对内存管理有较为直接的控制。 1. 基于 char 数组的串顺序存储 如果使用普通的 char 数组来存储字…

2026/7/12 14:27:04
移动端游戏功耗测试实战：电流、功率、亮度和场景对比

移动端游戏功耗测试实战：电流、功率、亮度和场景对比

移动端游戏功耗测试：先控制变量，再比较优化是否真的省电 摘要：功耗测试最容易犯的错误，是拿两次不同温度、不同亮度、不同场景的平均功率直接比较。本文给出一套可复现的游戏功耗测试方法，覆盖引擎特性验证、版本回归和黑盒体验测试，并说明如何把功耗与帧率、温控、CPU/G…

2026/7/12 18:30:40
足球口袋教练 HarmonyOS 离线应用实战（03/20）：ArkUI 首页仪表盘搭建

足球口袋教练 HarmonyOS 离线应用实战（03/20）：ArkUI 首页仪表盘搭建

本文是“足球口袋教练 HarmonyOS 离线应用实战”系列第 3 篇。示例项目是一个 HarmonyOS / ArkTS / ArkUI 编写的离线足球训练助手&#xff0c;围绕真实页面、真实截图和可复现操作展开。 本篇要解决的问题 训练 App 的首页不能只展示欢迎语&#xff0c;它要解决“我现在该点哪…

2026/7/12 23:03:24