一、为什么要用 C++ 手写数据结构
很多开发者在刷题、面试或做底层系统开发时都会遇到一个共同问题：标准库容器用起来很顺手，但一旦被问到「底层是怎么实现的」，比如std::map为什么查找是 O(log n)、std::list和std::vector的插入删除差异在哪里，就容易卡壳。手写数据结构不是为了重复造轮子，而是为了建立对内存布局、指针关系和复杂度分析的直观理解。
本文以 C++ 为载体，从最基础的链表出发，逐步过渡到栈和队列、二叉搜索树、AVL 树，最后实现经典的红黑树。每一部分都配有可运行的源码和结构图说明，帮助你把抽象概念落到代码层面。
建议读者具备 C++ 的指针、引用、类和模板基础。文中代码使用 C++11 及以上标准，可用
g++ -std=c++17编译。
二、链表：指针与节点关系的起点
链表是最适合入门指针操作的线性结构。它的核心是一个节点类，节点中保存数据以及指向下一个节点的指针。单链表节点结构如下：
template<typename T> struct ListNode { T data; ListNode* next; explicit ListNode(const T& value) : data(value), next(nullptr) {} };链表与数组最大的区别在于内存是否连续。下面这张结构图展示了单链表的组织方式：
graph LR A[节点1 data: 10] --> B[节点2 data: 20] B --> C[节点3 data: 30] C --> D[nullptr]下面给出一个带哨兵头的单向链表实现，支持头部插入、按值删除和遍历输出：
#include <iostream> #include <memory> template<typename T> class SinglyLinkedList { public: SinglyLinkedList() : head_(std::make_unique<ListNode<T>>(T{})) {} void push_front(const T& value) { auto node = std::make_unique<ListNode<T>>(value); node->next = head_->next; head_->next = node; } bool remove(const T& value) { ListNode<T>* prev = head_.get(); ListNode<T>* curr = head_->next; while (curr) { if (curr->data == value) { prev->next = curr->next; return true; } prev = curr; curr = curr->next; } return false; } void print() const { for (ListNode<T>* p = head_->next; p; p = p->next) { std::cout << p->data << " "; } std::cout << std::endl; } private: template<typename U> struct ListNode { U data; ListNode* next; explicit ListNode(const U& value) : data(value), next(nullptr) {} }; std::unique_ptr<ListNode<T>> head_; };这里使用unique_ptr管理哨兵头的生命周期，而所有插入节点的next仍然是裸指针，这也是教学实现中常见的方式。理解链表后，树结构中的父子指针关系就不再陌生。
三、栈与队列：受限的线性结构
栈和队列都可以看作对线性表的访问方式加以限制后的结果。栈是后进先出，队列是先进先出。
3.1 用数组实现栈
一个简单的动态数组栈可以通过vector快速实现，插入和删除都发生在同一端：
#include <vector> #include <stdexcept> template<typename T> class Stack { public: void push(const T& value) { data_.push_back(value); } void pop() { if (data_.empty()) { throw std::out_of_range("stack is empty"); } data_.pop_back(); } const T& top() const { if (data_.empty()) { throw std::out_of_range("stack is empty"); } return data_.back(); } bool empty() const { return data_.empty(); } size_t size() const { return data_.size(); } private: std::vector<T> data_; };3.2 用双指针队列实现队列
队列需要在头部删除、尾部插入。为了避免数组头部删除时全体搬移元素，可以采用数组循环队列。这里用一个固定容量数组和两个指针head、tail表示队首和队尾：
#include <vector> #include <stdexcept> template<typename T> class CircularQueue { public: explicit CircularQueue(size_t capacity) : data_(capacity + 1), head_(0), tail_(0) {} bool empty() const { return head_ == tail_; } bool full() const { return (tail_ + 1) % data_.size() == head_; } void push(const T& value) { if (full()) { throw std::overflow_error("queue is full"); } data_[tail_] = value; tail_ = (tail_ + 1) % data_.size(); } T pop() { if (empty()) { throw std::underflow_error("queue is empty"); } T value = data_[head_]; head_ = (head_ + 1) % data_.size(); return value; } private: std::vector<T> data_; size_t head_; size_t tail_; };循环队列把数组首尾连接成环，用取模运算实现下标回绕。这种技巧在消息队列、缓存调度等系统中非常常见。
四、二叉搜索树：查找效率的第一次跃升
二叉搜索树要求任意节点满足：左子树的所有值小于该节点，右子树的所有值大于该节点。这个性质使得查找路径可以沿着一条分支走到叶子，平均时间复杂度为 O(log n)。
graph TD A[50] --> B[30] A --> C[70] B --> D[20] B --> E[40] C --> F[60] C --> G[80]插入、查找、删除的递归实现如下：
template<typename T> struct TreeNode { T key; TreeNode* left; TreeNode* right; explicit TreeNode(const T& value) : key(value), left(nullptr), right(nullptr) {} }; template<typename T> class BinarySearchTree { public: BinarySearchTree() : root_(nullptr), size_(0) {} void insert(const T& key) { root_ = insert(root_, key); } bool contains(const T& key) const { return find(root_, key) != nullptr; } void remove(const T& key) { root_ = remove(root_, key); } size_t size() const { return size_; } private: TreeNode<T>* insert(TreeNode<T>* node, const T& key) { if (!node) { ++size_; return new TreeNode<T>(key); } if (key < node->key) { node->left = insert(node->left, key); } else if (key > node->key) { node->right = insert(node->right, key); } return node; } TreeNode<T>* find(TreeNode<T>* node, const T& key) const { if (!node || node->key == key) return node; if (key < node->key) return find(node->left, key); return find(node->right, key); } TreeNode<T>* remove(TreeNode<T>* node, const T& key) { if (!node) return nullptr; if (key < node->key) { node->left = remove(node->left, key); } else if (key > node->key) { node->right = remove(node->right, key); } else { if (!node->left) { TreeNode<T>* rightChild = node->right; delete node; --size_; return rightChild; } if (!node->right) { TreeNode<T>* leftChild = node->left; delete node; --size_; return leftChild; } TreeNode<T>* successor = findMin(node->right); node->key = successor->key; node->right = remove(node->right, successor->key); } return node; } TreeNode<T>* findMin(TreeNode<T>* node) const { while (node && node->left) { node = node->left; } return node; } TreeNode<T>* root_; size_t size_; };删除有两个子节点的节点时，通常用右子树的最小值节点替换，再递归删除该后继节点。二叉搜索树的主要问题在于：如果插入序列本身有序，树会退化成一条链，查找复杂度会恶化到 O(n)。这正是平衡树要解决的痛点。
五、AVL 树：用旋转维持平衡
AVL 树是第一种被发明的自平衡二叉搜索树。它为每个节点维护一个「平衡因子」，即左右子树高度之差，并要求平衡因子绝对值不超过 1。一旦失衡，就通过四种旋转恢复平衡。
graph TD A[30] --> B[20] A --> C[50] B --> D[10] B --> E[25] C --> F[40] C --> G[60]5.1 节点高度与平衡因子
template<typename T> struct AVLNode { T key; AVLNode* left; AVLNode* right; int height; explicit AVLNode(const T& value) : key(value), left(nullptr), right(nullptr), height(1) {} }; template<typename T> int height(AVLNode<T>* node) { return node ? node->height : 0; } template<typename T> int balanceFactor(AVLNode<T>* node) { if (!node) return 0; return height(node->left) - height(node->right); }5.2 四种旋转
当某个节点的平衡因子为 2 时，说明左子树过高；平衡因子为 -2 时，说明右子树过高。再结合子树的倾斜方向，共形成四种情况：左左、右右、左右、右左。旋转操作的核心是交换父子关系，让较中间的那个节点成为新的局部根。
template<typename T> AVLNode<T>* rotateRight(AVLNode<T>* y) { AVLNode<T>* x = y->left; AVLNode<T>* t2 = x->right; x->right = y; y->left = t2; y->height = 1 + std::max(height(y->left), height(y->right)); x->height = 1 + std::max(height(x->left), height(x->right)); return x; } template<typename T> AVLNode<T>* rotateLeft(AVLNode<T>* x) { AVLNode<T>* y = x->right; AVLNode<T>* t2 = y->left; y->left = x; x->right = t2; x->height = 1 + std::max(height(x->left), height(x->right)); y->height = 1 + std::max(height(y->left), height(y->right)); return y; }5.3 插入后的平衡修复
template<typename T> AVLNode<T>* insertAVL(AVLNode<T>* node, const T& key) { if (!node) { return new AVLNode<T>(key); } if (key < node->key) { node->left = insertAVL(node->left, key); } else if (key > node->key) { node->right = insertAVL(node->right, key); } else { return node; } node->height = 1 + std::max(height(node->left), height(node->right)); int balance = balanceFactor(node); // 左左 if (balance > 1 && key < node->left->key) { return rotateRight(node); } // 右右 if (balance < -1 && key > node->right->key) { return rotateLeft(node); } // 左右 if (balance > 1 && key > node->left->key) { node->left = rotateLeft(node->left); return rotateRight(node); } // 右左 if (balance < -1 && key < node->right->key) { node->right = rotateRight(node->right); return rotateLeft(node); } return node; }AVL 树的优点是查找极快，因为高度差被严格控制在 1 以内，最坏情况高度约为1.44 * log2(n)。但它的缺点是插入和删除可能需要频繁旋转。红黑树采用更宽松的平衡条件，在写入性能和查询性能之间取得了更好平衡，因此成为std::map、std::set的标准底层实现。
六、红黑树：从颜色约束到全局平衡
红黑树是一棵满足五条性质的二叉搜索树：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶子节点视作黑色空节点。
- 红色节点的子节点必须是黑色，即不能出现连续红色。
- 从任意节点到其所有后代叶子节点的路径上，黑色节点数量相同。
graph TD A[13 黑色] --> B[8 红色] A --> C[17 黑色] B --> D[1 黑色] B --> E[11 黑色] C --> F[15 红色] C --> G[25 红色] D --> H[NIL 黑色] D --> I[6 红色] F --> J[NIL 黑色] F --> K[NIL 黑色] G --> L[22 黑色] G --> M[27 黑色]这些性质共同保证：从根到叶子的最长路径不会超过最短路径的两倍，因此树的高度始终是 O(log n)。
6.1 节点定义
enum class Color { RED, BLACK }; template<typename T> struct RBNode { T key; Color color; RBNode* left; RBNode* right; RBNode* parent; explicit RBNode(const T& value) : key(value), color(Color::RED), left(nullptr), right(nullptr), parent(nullptr) {} };新插入节点默认设为红色，这样可以尽量不破坏「黑色高度相同」这条性质，只需修复可能出现的连续红色问题。
6.2 左旋与右旋
template<typename T> void rotateLeft(RBNode<T>*& root, RBNode<T>* x) { RBNode<T>* y = x->right; x->right = y->left; if (y->left) y->left->parent = x; y->parent = x->parent; if (!x->parent) { root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; x->parent = y; } template<typename T> void rotateRight(RBNode<T>*& root, RBNode<T>* y) { RBNode<T>* x = y->left; y->left = x->right; if (x->right) x->right->parent = y; x->parent = y->parent; if (!y->parent) { root = x; } else if (y == y->parent->left) { y->parent->left = x; } else { y->parent->right = x; } x->right = y; y->parent = x; }和 AVL 树不同，红黑树的旋转需要同时维护父指针，这使得代码量更大，但逻辑仍然可以归纳为固定的几种情况。
6.3 插入修复
插入一个新红色节点后，可能违反「红色节点不能有红色子节点」。修复过程分为「叔节点为红色」的改色情形，以及「叔节点为黑色」的旋转+改色情形，最多执行两次旋转即可完成调整。
template<typename T> void fixInsert(RBNode<T>*& root, RBNode<T>* node) { while (node != root && node->parent->color == Color::RED) { RBNode<T>* parent = node->parent; RBNode<T>* grandparent = parent->parent; if (parent == grandparent->left) { RBNode<T>* uncle = grandparent->right; if (uncle && uncle->color == Color::RED) { parent->color = Color::BLACK; uncle->color = Color::BLACK; grandparent->color = Color::RED; node = grandparent; } else { if (node == parent->right) { node = parent; rotateLeft(root, node); parent = node->parent; grandparent = parent->parent; } parent->color = Color::BLACK; grandparent->color = Color::RED; rotateRight(root, grandparent); } } else { RBNode<T>* uncle = grandparent->left; if (uncle && uncle->color == Color::RED) { parent->color = Color::BLACK; uncle->color = Color::BLACK; grandparent->color = Color::RED; node = grandparent; } else { if (node == parent->left) { node = parent; rotateRight(root, node); parent = node->parent; grandparent = parent->parent; } parent->color = Color::BLACK; grandparent->color = Color::RED; rotateLeft(root, grandparent); } } } root->color = Color::BLACK; }6.4 插入入口与辅助方法
template<typename T> void insertRB(RBNode<T>*& root, const T& key) { RBNode<T>* node = new RBNode<T>(key); RBNode<T>* parent = nullptr; RBNode<T>* current = root; while (current) { parent = current; if (key < current->key) { current = current->left; } else { current = current->right; } } node->parent = parent; if (!parent) { root = node; root->color = Color::BLACK; return; } if (key < parent->key) { parent->left = node; } else { parent->right = node; } fixInsert(root, node); }红黑树的删除比插入更复杂，需要根据被删节点颜色、兄弟节点颜色、兄弟子节点颜色等组合情况处理，但核心仍然是通过改色与旋转维持五条性质。理解插入修复后，删除修复可以通过对称关系慢慢推导。
七、复杂度对比与选型建议
| 数据结构 | 查找 | 插入 | 删除 | 额外特点 |
|---|---|---|---|---|
| 单链表 | O(n) | O(1) 头部 | O(n) | 内存不连续，便于高频增删头部 |
| 栈/队列 | O(n) 遍历 | O(1) | O(1) | 访问顺序受限，适合临时缓冲 |
| 二叉搜索树 | O(log n) 平均 | O(log n) 平均 | O(log n) 平均 | 最坏退化为 O(n) |
| AVL 树 | O(log n) | O(log n) | O(log n) | 严格平衡，查询更快，旋转较多 |
| 红黑树 | O(log n) | O(log n) | O(log n) | 平衡条件宽松，写入开销更小 |
实际开发中，如果需要频繁查询、插入删除相对较少，AVL 树可能是更优选择；如果读写都很频繁，红黑树通常更合适。C++ 标准库的std::map、std::set和 Java 的TreeMap默认都采用红黑树。
八、总结
本文沿着「线性结构 → 树结构 → 平衡树」的路径，用 C++ 实现了链表、栈、队列、二叉搜索树、AVL 树和红黑树。它们的核心差异可以归纳为三点：
- 内存与指针组织：线性结构关注节点连接方式，二叉搜索树关注左右子树的大小关系。
- 平衡策略：AVL 树通过严格的高度差约束快速恢复平衡，红黑树通过颜色约束放宽平衡要求。
- 工程权衡：没有绝对最优的数据结构，只有更适合具体读写场景的选择。
建议读者先独立完成链表和二叉搜索树，再尝试分别实现 AVL 树与红黑树的插入逻辑。当你能在不看模板的情况下写出红黑树的旋转和着色过程时，对树形结构的理解就会上升到一个新的层次。
