如何实现分支预测友好的AVL树升序与降序遍历？

针对递归遍历因分支预测失效导致的性能问题，以下几种方案可有效提升遍历的分支预测友好性：

1. 线索化二叉树遍历（Threaded Binary Tree） #

将AVL树转换为中序线索化二叉树，把每个节点的空指针替换为遍历的前驱/后继线索：

• 空左指针指向该节点在中序遍历中的前驱节点
• 空右指针指向该节点在中序遍历中的后继节点

遍历过程中无需频繁判断子树是否为空，而是沿着线索线性移动，分支跳转模式高度规律，分支预测器能轻松命中。

升序遍历示例代码 #

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
    bool isLeftThread;  // 标记左指针是否为线索
    bool isRightThread; // 标记右指针是否为线索
} Node;

void traverseAscendingThreaded(Node *root) {
    Node *cur = root;
    while (cur != NULL) {
        // 找到当前节点的最左有效子节点（跳过线索）
        while (!cur->isLeftThread && cur->left != NULL) {
            cur = cur->left;
        }
        // 输出节点数据
        outVals[totOuts++] = cur->data;
        
        // 利用线索直接跳转到后继节点
        if (cur->isRightThread) {
            cur = cur->right;
        } else {
            cur = cur->right;
        }
    }
}

2. 预缓存遍历序列 #

如果AVL树的修改操作不频繁，可以预先将节点按遍历顺序存入数组：

• 当树结构发生变更时，重新生成升序和降序的节点序列数组
• 后续遍历直接线性遍历数组，完全消除分支判断

这种方式的遍历性能接近数组线性访问，彻底解决分支预测失效问题，适合查询远多于修改的场景。

3. 迭代式遍历优化（栈模拟+分支消除） #

如果不想修改树结构，可以用栈模拟递归，但通过调整逻辑减少分支判断。比如一次性处理所有左子树节点入栈，让分支判断模式更固定：

void traverseAscendingIterative(Node *root) {
    Node *stack[STACK_SIZE];
    int stackTop = -1;
    Node *cur = root;

    while (cur != NULL || stackTop >= 0) {
        // 一次性将所有左子节点入栈，减少分支判断次数
        while (cur != NULL) {
            stack[++stackTop] = cur;
            cur = cur->left;
        }
        cur = stack[stackTop--];
        outVals[totOuts++] = cur->data;
        cur = cur->right;
    }
}

这种方式的分支判断模式比递归更规律，分支预测器的命中率会显著提升。

内容的提问来源于stack exchange，提问作者Serge Rogatch