目录按结构特征分类普通二叉树满二叉树Full Binary Tree完美二叉树Perfect Binary Tree完全二叉树Complete Binary Tree斜二叉树Skewed Binary Tree退化二叉树Degenerate Tree按节点值规律分类二叉搜索树BST平衡二叉树AVL树红黑树Red-Black Tree二叉堆Heap哈夫曼树最优二叉树特殊用途二叉树线索二叉树Threaded Binary Tree伸展树Splay TreeTreap树堆线段树Segment Tree树状数组Fenwick Tree / BIT多叉树非严格二叉树但常一起考B树B-TreeB树B TreeTrie字典树/前缀树速查对比表软考真题题目官方解析按结构特征分类普通二叉树无任何特殊约束每个节点最多2个孩子。1 / \ 2 3 / \ 4 5满二叉树Full Binary Tree每个节点要么0个孩子要么2个孩子不存在度为1的节点。1 / \ 2 3 / \ / \ 4 5 6 7完美二叉树Perfect Binary Tree所有内部节点都有2个孩子且所有叶子在同一层。深度为k时节点数 2^k - 1。1 / \ 2 3 / \ / \ 4 5 6 7 完美二叉树同时满足满二叉树和完全二叉树的定义是最饱满的形态。完全二叉树Complete Binary Tree除最后一层外全满最后一层节点从左到右连续排列。1 / \ 2 3 / \ / 4 5 6堆Heap的底层结构就是完全二叉树可以用数组高效存储。斜二叉树Skewed Binary Tree所有节点只有左孩子左斜或只有右孩子右斜退化成链表性能 O(n)。左斜树 右斜树 1 1 / \ 2 2 / \ 3 3退化二叉树Degenerate Tree每个内部节点只有一个孩子不区分左右性能等同于链表。1 \ 2 / 3 \ 4按节点值规律分类二叉搜索树BST左子树所有值 根 右子树所有值中序遍历得到有序序列。8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13⚠️ 极端情况下会退化成链表如按顺序插入1,2,3,4,5查找变成 O(n)。平衡二叉树AVL树在BST基础上任意节点左右子树高度差 ≤ 1通过旋转维持平衡。8 / \ 4 12 / \ / \ 2 6 10 14查找、插入、删除稳定 O(log n)但旋转维护成本较高适合读多写少场景。红黑树Red-Black Tree自平衡BST通过红/黑着色 旋转规则维持近似平衡平衡条件比AVL宽松。8(B) / \ 4(R) 12(R) / \ / \ 2(B) 6(B) 10(B) 14(B)五条核心规则根节点是黑色红色节点的子节点必须是黑色不能有相邻红节点从任一节点到其所有后代叶子的路径上黑色节点数相同叶子节点NIL是黑色新插入节点默认为红色工程中最常用Java的HashMap/TreeMap、C的map、Linux内核进程调度都用它。相比AVL树插入/删除时旋转次数更少。二叉堆Heap完全二叉树 堆序性分大顶堆和小顶堆。大顶堆父 ≥ 子 小顶堆父 ≤ 子 9 1 / \ / \ 7 8 3 2 / \ / / \ / 4 5 6 4 5 6优先队列、堆排序的底层结构。哈夫曼树最优二叉树带权路径长度WPL最短的二叉树权值越大离根越近。100 / \ 40 60 / \ 25 35数据压缩ZIP、JPEG的核心算法。特殊用途二叉树线索二叉树Threaded Binary Tree利用叶子节点的空指针存储前驱/后继信息省去递归或栈的开销。普通二叉树 中序线索二叉树 A A / \ / \ B C B → C / ↑ ↓ D D ← (null)空指针被线索化遍历时无需额外空间。伸展树Splay Tree每次访问的节点通过旋转被提升到根位置最近访问的节点下次查找最快。访问节点3后3被旋转到根 3 / \ 1 5 \ \ 2 7适合有局部性特征的访问模式如缓存。Treap树堆BST Heap 的混合体key满足BST性质priority满足堆性质。key: BST序 priority: 大顶堆 5(10) / \ 3(7) 8(5) / \ 1(3) 4(2)通过随机priority实现期望平衡实现简单无需复杂旋转规则。线段树Segment Tree每个节点代表一个区间用于高效处理区间查询如区间求和、区间最值。数组: [1, 3, 5, 7] [0,3] sum16 / \ [0,1] sum4 [2,3] sum12 / \ / \ [0,0] [1,1] [2,2] [3,3] 1 3 5 7竞赛和工程中处理区间问题的利器查询和更新均为 O(log n)。树状数组Fenwick Tree / BIT用数组模拟树结构高效计算前缀和与单点更新。逻辑结构节点i管理区间长度 lowbit(i) 8 / 4 / \ 2 6 / \ / \ 1 3 5 7代码极短核心操作仅几行适合前缀和/区间和问题。多叉树非严格二叉树但常一起考B树B-Tree每个节点可以有多个key和多个孩子专为磁盘存储设计树很矮。[17 | 35] / | \ [5|13] [21|29] [40|50]数据库索引、文件系统的底层结构。B树B TreeB树的变体所有数据只存在叶子节点叶子之间用链表相连。[17 | 35] ← 内部节点只存索引 / | \ [5|13] [21|29] [40|50] ← 叶子节点存实际数据 ↓ ↓ ↓ → → → → → → → → → → → ← 叶子链表方便范围查询MySQL InnoDB索引就是B树范围查询效率极高。Trie字典树/前缀树每个节点代表一个字符路径表示一个字符串。root / | \ a b c / | \ p a a / \ | | p e t t | | l | (cat, bat, apple, app)自动补全、拼写检查、IP路由。速查对比表类型核心特征查找典型应用满二叉树每层全满—理论基准完全二叉树最后一层靠左—堆斜二叉树退化成链表O(n)反面教材BST左根右O(log n)~O(n)基础搜索AVL树高度差≤1O(log n)读多写少红黑树着色近似平衡O(log n)Java/C标准库哈夫曼树WPL最短—数据压缩堆完全二叉树堆序O(1)取极值优先队列线段树区间信息聚合O(log n)区间查询B树多路叶子链表O(log n)数据库索引Trie字符路径O(字符串长度)自动补全软考真题题目解析画图以后如下官方解析以上就是本篇文章的全部内容喜欢的话可以留个免费的关注呦~~~ 二叉树家族
目录按结构特征分类普通二叉树满二叉树Full Binary Tree完美二叉树Perfect Binary Tree完全二叉树Complete Binary Tree斜二叉树Skewed Binary Tree退化二叉树Degenerate Tree按节点值规律分类二叉搜索树BST平衡二叉树AVL树红黑树Red-Black Tree二叉堆Heap哈夫曼树最优二叉树特殊用途二叉树线索二叉树Threaded Binary Tree伸展树Splay TreeTreap树堆线段树Segment Tree树状数组Fenwick Tree / BIT多叉树非严格二叉树但常一起考B树B-TreeB树B TreeTrie字典树/前缀树速查对比表软考真题题目官方解析按结构特征分类普通二叉树无任何特殊约束每个节点最多2个孩子。1 / \ 2 3 / \ 4 5满二叉树Full Binary Tree每个节点要么0个孩子要么2个孩子不存在度为1的节点。1 / \ 2 3 / \ / \ 4 5 6 7完美二叉树Perfect Binary Tree所有内部节点都有2个孩子且所有叶子在同一层。深度为k时节点数 2^k - 1。1 / \ 2 3 / \ / \ 4 5 6 7 完美二叉树同时满足满二叉树和完全二叉树的定义是最饱满的形态。完全二叉树Complete Binary Tree除最后一层外全满最后一层节点从左到右连续排列。1 / \ 2 3 / \ / 4 5 6堆Heap的底层结构就是完全二叉树可以用数组高效存储。斜二叉树Skewed Binary Tree所有节点只有左孩子左斜或只有右孩子右斜退化成链表性能 O(n)。左斜树 右斜树 1 1 / \ 2 2 / \ 3 3退化二叉树Degenerate Tree每个内部节点只有一个孩子不区分左右性能等同于链表。1 \ 2 / 3 \ 4按节点值规律分类二叉搜索树BST左子树所有值 根 右子树所有值中序遍历得到有序序列。8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13⚠️ 极端情况下会退化成链表如按顺序插入1,2,3,4,5查找变成 O(n)。平衡二叉树AVL树在BST基础上任意节点左右子树高度差 ≤ 1通过旋转维持平衡。8 / \ 4 12 / \ / \ 2 6 10 14查找、插入、删除稳定 O(log n)但旋转维护成本较高适合读多写少场景。红黑树Red-Black Tree自平衡BST通过红/黑着色 旋转规则维持近似平衡平衡条件比AVL宽松。8(B) / \ 4(R) 12(R) / \ / \ 2(B) 6(B) 10(B) 14(B)五条核心规则根节点是黑色红色节点的子节点必须是黑色不能有相邻红节点从任一节点到其所有后代叶子的路径上黑色节点数相同叶子节点NIL是黑色新插入节点默认为红色工程中最常用Java的HashMap/TreeMap、C的map、Linux内核进程调度都用它。相比AVL树插入/删除时旋转次数更少。二叉堆Heap完全二叉树 堆序性分大顶堆和小顶堆。大顶堆父 ≥ 子 小顶堆父 ≤ 子 9 1 / \ / \ 7 8 3 2 / \ / / \ / 4 5 6 4 5 6优先队列、堆排序的底层结构。哈夫曼树最优二叉树带权路径长度WPL最短的二叉树权值越大离根越近。100 / \ 40 60 / \ 25 35数据压缩ZIP、JPEG的核心算法。特殊用途二叉树线索二叉树Threaded Binary Tree利用叶子节点的空指针存储前驱/后继信息省去递归或栈的开销。普通二叉树 中序线索二叉树 A A / \ / \ B C B → C / ↑ ↓ D D ← (null)空指针被线索化遍历时无需额外空间。伸展树Splay Tree每次访问的节点通过旋转被提升到根位置最近访问的节点下次查找最快。访问节点3后3被旋转到根 3 / \ 1 5 \ \ 2 7适合有局部性特征的访问模式如缓存。Treap树堆BST Heap 的混合体key满足BST性质priority满足堆性质。key: BST序 priority: 大顶堆 5(10) / \ 3(7) 8(5) / \ 1(3) 4(2)通过随机priority实现期望平衡实现简单无需复杂旋转规则。线段树Segment Tree每个节点代表一个区间用于高效处理区间查询如区间求和、区间最值。数组: [1, 3, 5, 7] [0,3] sum16 / \ [0,1] sum4 [2,3] sum12 / \ / \ [0,0] [1,1] [2,2] [3,3] 1 3 5 7竞赛和工程中处理区间问题的利器查询和更新均为 O(log n)。树状数组Fenwick Tree / BIT用数组模拟树结构高效计算前缀和与单点更新。逻辑结构节点i管理区间长度 lowbit(i) 8 / 4 / \ 2 6 / \ / \ 1 3 5 7代码极短核心操作仅几行适合前缀和/区间和问题。多叉树非严格二叉树但常一起考B树B-Tree每个节点可以有多个key和多个孩子专为磁盘存储设计树很矮。[17 | 35] / | \ [5|13] [21|29] [40|50]数据库索引、文件系统的底层结构。B树B TreeB树的变体所有数据只存在叶子节点叶子之间用链表相连。[17 | 35] ← 内部节点只存索引 / | \ [5|13] [21|29] [40|50] ← 叶子节点存实际数据 ↓ ↓ ↓ → → → → → → → → → → → ← 叶子链表方便范围查询MySQL InnoDB索引就是B树范围查询效率极高。Trie字典树/前缀树每个节点代表一个字符路径表示一个字符串。root / | \ a b c / | \ p a a / \ | | p e t t | | l | (cat, bat, apple, app)自动补全、拼写检查、IP路由。速查对比表类型核心特征查找典型应用满二叉树每层全满—理论基准完全二叉树最后一层靠左—堆斜二叉树退化成链表O(n)反面教材BST左根右O(log n)~O(n)基础搜索AVL树高度差≤1O(log n)读多写少红黑树着色近似平衡O(log n)Java/C标准库哈夫曼树WPL最短—数据压缩堆完全二叉树堆序O(1)取极值优先队列线段树区间信息聚合O(log n)区间查询B树多路叶子链表O(log n)数据库索引Trie字符路径O(字符串长度)自动补全软考真题题目解析画图以后如下官方解析以上就是本篇文章的全部内容喜欢的话可以留个免费的关注呦~~~