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) { // 情况2z是右孩子 - 左旋 z z-parent; rb_rotate_left(root, z); } // 情况3z是左孩子 - 右旋变色 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中插入新的keyy-keys[MIN_KEY]和z for (int j parent-n; j idx; j--) { parent-child[j1] parent-child[j]; parent-keys[j] parent-keys[j-1]; } parent-child[idx1] 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[i1] node-keys[i]; i--; } node-keys[i1] 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[i1] temp[i]; i--; } temp[i1] 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树插入需要递归处理内部节点的分裂此处省略