第19章树结构模块

课程目录第19章树结构模块

树结构模块：二叉树、二叉搜索树、平衡树的基本接口

树结构，说白了就是嵌入式世界里最优雅的数据组织方式之一。我做了十几年嵌入式，从最早的AVR到现在的ARM Cortex-M系列，树结构几乎贯穿了我所有的项目。你想想看，链表虽然简单，但查找起来太慢；数组虽然快，但插入删除又麻烦。树结构正好在两者之间找到了平衡点。

今天咱们聊聊二叉树、二叉搜索树和平衡树。嗯，别被这些名字吓到，其实核心思想就一个：怎么让数据组织得更聪明。

二叉树：最基础的树结构

二叉树，每个节点最多有两个孩子。左孩子、右孩子，就这么简单。我在项目中遇到过最典型的场景——用二叉树来组织菜单结构。每个菜单项要么有子菜单（左子树），要么有同级菜单（右子树），遍历起来特别直观。

// 二叉树节点结构
typedef struct TreeNode {
    void *data;                 // 数据指针
    struct TreeNode *left;      // 左孩子
    struct TreeNode *right;     // 右孩子
} TreeNode;

// 创建节点
TreeNode* tree_create_node(void *data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    if (node) {
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    return node;
}

// 前序遍历
void tree_preorder(TreeNode *root, void (*visit)(void*)) {
    if (!root) return;
    visit(root->data);
    tree_preorder(root->left, visit);
    tree_preorder(root->right, visit);
}

小提示：二叉树遍历有三种方式——前序、中序、后序。我个人习惯用中序遍历二叉搜索树，因为出来的结果就是有序的。这个技巧在调试时特别有用。

二叉搜索树：让查找更快

二叉搜索树（BST）有个核心规则：左子树所有节点都小于根节点，右子树所有节点都大于根节点。这个规则一加上，查找效率就从O(n)降到了O(log n)。

我曾经在一个传感器数据采集项目中用过BST。传感器ID是整数，需要快速查找对应的校准参数。用BST做索引，几千个传感器查一遍也就十几次比较，比遍历链表快了一个数量级。

// 二叉搜索树插入
BSTNode* bst_insert(BSTNode *root, int key, void *data) {
    if (!root) {
        return bst_create_node(key, data);
    }
    
    if (key < root->key) {
        root->left = bst_insert(root->left, key, data);
    } else if (key > root->key) {
        root->right = bst_insert(root->right, key, data);
    } else {
        // 键值已存在，更新数据
        root->data = data;
    }
    return root;
}

// 二叉搜索树查找
void* bst_search(BSTNode *root, int key) {
    while (root) {
        if (key == root->key) return root->data;
        if (key < root->key) root = root->left;
        else root = root->right;
    }
    return NULL;  // 没找到
}

注意：二叉搜索树有个致命问题——如果插入的数据是有序的，树会退化成链表。我踩过这个坑，当时用递增的ID建树，结果查找效率直接掉到O(n)。后来才意识到需要平衡树。

平衡树：解决退化问题

平衡树的核心思想很简单：在插入或删除后，通过旋转操作让树保持平衡。常见的平衡树有AVL树和红黑树。AVL要求更严格（左右子树高度差不超过1），红黑树则宽松一些。

我个人更推荐红黑树。为什么？因为AVL的旋转太频繁了，在嵌入式系统里，每次旋转都要做内存操作，性能开销不小。红黑树虽然平衡性稍差，但旋转次数少，整体性能反而更好。

核心要点：平衡树不是完美的平衡，而是「足够好」的平衡。红黑树保证最长路径不超过最短路径的2倍，这个约束在实际应用中完全够用。

实战：实现一个简单的红黑树模块

好了，理论说完了，咱们动手写一个红黑树模块。红黑树有5条规则，我记了十年都没忘：

每个节点要么红要么黑
根节点是黑色
叶子节点（NULL）是黑色
红色节点的子节点必须是黑色
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

嗯，第4条和第5条是最关键的。第4条保证了不会出现连续的红节点，第5条保证了树的平衡性。

// 红黑树节点颜色
typedef enum { RED, BLACK } Color;

// 红黑树节点
typedef struct RBNode {
    int key;
    void *data;
    Color color;
    struct RBNode *left, *right, *parent;
} RBNode;

// 左旋操作
void rb_left_rotate(RBTree *tree, RBNode *x) {
    RBNode *y = x->right;
    x->right = y->left;
    
    if (y->left != NULL) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    
    if (x->parent == NULL) {
        tree->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_insert_fixup(RBTree *tree, 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 {
                // 情况2：叔叔是黑色，需要旋转
                if (z == z->parent->right) {
                    z = z->parent;
                    rb_left_rotate(tree, z);
                }
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                rb_right_rotate(tree, z->parent->parent);
            }
        } else {
            // 对称情况，左右互换
            // ... 代码类似，left/right互换
        }
    }
    tree->root->color = BLACK;
}

调试技巧：红黑树最容易出错的地方是插入修复时的指针操作。我曾经花了一整天调试一个红黑树bug，最后发现是parent指针没更新。建议你在每次旋转后，用断言检查所有节点的parent指针是否正确。

红黑树模块的接口设计

一个好的模块，接口要清晰。我习惯把红黑树封装成这样的接口：

// 红黑树模块接口
typedef struct {
    RBNode *root;
    int (*compare)(const void *a, const void *b);
    size_t size;
} RBTree;

// 创建红黑树
RBTree* rb_create(int (*compare)(const void*, const void*));

// 插入节点
int rb_insert(RBTree *tree, void *key, void *data);

// 删除节点
int rb_delete(RBTree *tree, void *key);

// 查找节点
void* rb_search(RBTree *tree, void *key);

// 遍历（中序）
void rb_inorder(RBTree *tree, void (*visit)(void*, void*));

// 销毁树
void rb_destroy(RBTree *tree);

你看，接口只有6个函数，但覆盖了增删查改所有操作。这就是模块化设计的好处——使用者不需要关心内部的红黑树旋转逻辑，只需要调用接口就行。

知识体系总览

下面这张图展示了树结构模块的核心知识体系，从基础到实战，一目了然：

从这张图可以看出，树结构的学习路径很清晰：从最基础的二叉树开始，加上排序规则变成二叉搜索树，再加上平衡机制变成平衡树，最后落地到红黑树实战。每一步都是在前一步的基础上增加复杂度。

总结一下：树结构模块的核心就三件事——节点怎么组织、怎么插入删除、怎么保持平衡。红黑树虽然代码看起来复杂，但核心逻辑就是插入修复那几行代码。你把这个搞懂了，其他平衡树都是类似的思路。

好了，红黑树模块就聊到这儿。代码我已经给了核心部分，剩下的删除操作和销毁操作，建议你自己动手实现一遍。相信我，自己写一遍比看十遍都管用。

📚 课程目录

树结构模块：二叉树、二叉搜索树、平衡树的基本接口

二叉树：最基础的树结构

二叉搜索树：让查找更快

平衡树：解决退化问题

实战：实现一个简单的红黑树模块

红黑树模块的接口设计

知识体系总览