左偏树与右偏树：原理、实现与应用
1. 引言
在计算机科学的数据结构领域，堆（Heap）是一种非常重要的抽象数据类型，常用于实现优先队列。除了常见的二叉堆、斐波那契堆等，还存在一些特殊的可合并堆结构，其中左偏树（Leftist Tree）和右偏树（Rightist Tree）就是两种基于二叉树形态、支持高效合并操作的堆实现。本文将深入探讨这两种数据结构的定义、性质、核心操作及其应用场景。
2. 基本概念与定义
2.1 左偏树（Leftist Tree）
左偏树是一种可合并的二叉堆，它满足堆性质（通常是最小堆或最大堆）和左偏性质。左偏性质是指：对于树中的任意节点，其左子节点的零路径长（Null Path Length, NPL）不小于右子节点的零路径长。
零路径长（NPL）定义为：从节点X出发到一个没有两个子节点的节点的最短路径长度。空节点的NPL定义为-1。
2.2 右偏树（Rightist Tree）
右偏树与左偏树对称，它同样满足堆性质，但遵循右偏性质：对于树中的任意节点，其右子节点的NPL不小于左子节点的NPL。右偏树在实际应用中较少见，但其原理与左偏树完全对称。
3. 核心性质与优势
3.1 左偏性质带来的优势
左偏树的核心优势在于其右路径长度（从根节点一直向右走的路径）为 O(log n)。这一性质保证了合并、插入、删除最小（或最大）值等操作的时间复杂度都能保持在O(log n)。
- 高效合并：合并两个左偏树时，算法主要沿着右路径进行递归，由于右路径短，合并效率高。
- 简单实现：相比斐波那契堆等复杂结构，左偏树的实现更为简洁。
3.2 与普通二叉堆的对比
| 特性 | 普通二叉堆（数组实现） | 左偏树/右偏树 |
|---|---|---|
| 合并操作 | O(n)，需要重建堆 | O(log n)，支持高效合并 |
| 结构 | 完全二叉树，用数组存储 | 二叉树，用指针连接 |
| 插入/删除 | O(log n) | O(log n)（通过合并实现） |
| 空间开销 | 较低（无指针） | 较高（需要存储指针和NPL） |
4. 关键操作与实现
4.1 节点结构
以最小左偏树为例，节点通常包含以下字段：
struct LeftistNode { int key; // 键值 int npl; // 零路径长 LeftistNode* left; LeftistNode* right; // 构造函数等... };4.2 合并（Merge）操作
合并是左偏树的核心操作，插入和删除操作都基于合并实现。
LeftistNode* merge(LeftistNode* a, LeftistNode* b) { if (a == nullptr) return b; if (b == nullptr) return a; // 保证 a 是根值较小的树 if (a->key > b->key) swap(a, b); // 递归合并 a的右子树 与 b a->right = merge(a->right, b); // 维护左偏性质：确保左子树的NPL >= 右子树的NPL if (a->left == nullptr || (a->left != nullptr && a->left->npl < a->right->npl)) { swap(a->left, a->right); } // 更新当前节点的NPL a->npl = (a->right == nullptr) ? 0 : (a->right->npl + 1); return a; }4.3 插入与删除
- 插入：将新节点视为只有一个节点的左偏树，与原有树合并。
- 删除最小值：删除根节点，然后合并其左右子树。
5. 应用场景
- 优先队列的合并：当需要频繁合并多个优先队列时（如某些图算法、离散事件模拟），左偏树比普通二叉堆更高效。
- 可合并堆的实现：作为更复杂可合并堆（如斜堆、二项堆）的基础或变体。
- 算法竞赛：因其实现相对简单且合并高效，左偏树是算法竞赛中处理可合并堆的常见选择。
6. 总结
左偏树和右偏树通过引入“零路径长”和“偏序”性质，在保持堆性质的同时，赋予了二叉树可高效合并的能力。左偏树因其右路径短的特性，保证了核心操作在对数时间复杂度内完成。虽然其在通用场景下的性能可能不如斐波那契堆，但其实现简单、易于理解，在需要可合并优先队列的特定场景下，是一个优雅而实用的选择。理解左偏树也有助于深入掌握其他更复杂的堆结构。