考研数据结构之树形查找：二叉排序树、平衡二叉树与红黑树（包含真题解析）

考研数据结构之树形查找：二叉排序树、平衡二叉树与红黑树

一、二叉排序树（BST）

1.1 概念

二叉排序树（Binary Search Tree）满足以下性质：

1. 若左子树不为空，左子树上所有节点值 < 根节点值
2. 若右子树不为空，右子树上所有节点值 > 根节点值
3. 左右子树各自也是二叉排序树

1.2 查找效率

平均时间复杂度为 O(logN)，最坏情况退化为 O(N)（单侧树）

1.3 常考题型（简答题/选择题）

真题1： 给定序列{5,2,8,3,6,1,9,7}构造BST，查找8的平均查找长度ASM是多少？

// BST构建核心代码
typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

// 插入函数
BSTNode* insertBST(BSTree T, int key) {
    if(!T) {
        T = (BSTNode*)malloc(sizeof(BSTNode));
        T->key = key;
        T->lchild = T->rchild = NULL;
    } else if(key < T->key) {
        T->lchild = insertBST(T->lchild, key);
    } else if(key > T->key) {
        T->rchild = insertBST(T->rchild, key);
    }
    return T;
}

// 查找函数
BSTNode* bstSearch(BSTree T, int key, int* count) {
    if(!T) return NULL;
    (*count)++;
    if(key == T->key) return T;
    else if(key < T->key) 
        return bstSearch(T->lchild, key, count);
    else 
        return bstSearch(T->rchild, key, count);
}

解析：
按状态构建二叉排序树后：

       5
     /   \
    2     8
   / \   / \
  1   3 6   9
          /
         7

查找各元素比较次数：5->8: 3次比较，其他元素合计比较12次
ASM=(1+2+2+3+3+4+1+3)/8 = 19/8 ≈ 2.38

二、平衡二叉树（AVL）

2.1 核心性质

1. 左子树和右子树的高度差绝对值不超过1
2. 每个子树最大高度差导致的旋转分为4种情况：
   • LL型：单左单旋转
   • RR型：单右单旋转
   • LR型：先左旋后右旋
   • RL型：先右旋后左旋

2.2 旋转实现代码

typedef struct AVLNode {
    int key;
    struct AVLNode *lchild, *rchild; 
    int height;
} AVLNode, *AVLTree;

int height(AVLNode *node) {
    return node ? node->height : 0;
}

// 右单旋
AVLNode* singleRightRotation(AVLNode* root) {
    AVLNode* newRoot = root->lchild;
    root->lchild = newRoot->rchild;
    newRoot->rchild = root;
    
    root->height = 1 + max(height(root->lchild), height(root->rchild));
    newRoot->height = 1 + max(height(newRoot->lchild), height(newRoot->rchild));
    
    return newRoot;
}

// 左单旋
AVLNode* singleLeftRotation(AVLNode* root) {
    AVLNode* newRoot = root->rchild;
    root->rchild = newRoot->lchild;
    newRoot->lchild = root;
    
    root->height = 1 + max(height(root->lchild), height(root->rchild));
    newRoot->height = 1 + max(height(newRoot->lchild), height(newRoot->rchild));
    
    return newRoot;
}

// 插入实现
AVLNode* insertAVL(AVLNode* node, int key) {
    if(!node) {
        node = (AVLNode*)malloc(sizeof(AVLNode));
        node->key = key;
        node->lchild = node->rchild = NULL;
        node->height = 1;
    } else if(key < node->key) {
        node->lchild = insertAVL(node->lchild, key);
        // 检查平衡
        if(height(node->lchild) - height(node->rchild) == 2) {
            if(key < node->lchild->key) {
                node = singleRightRotation(node); // LL型
            } else {
                node = doubleLRRotation(node); // LR型
            }
        }
    } else if(key > node->key) {
        node->rchild = insertAVL(node->rchild, key);
        // 不完整实现...（根据类似逻辑补充048）
    }
    updateHeight(node);
    return node;
}

2.3 真题示例

真题2： 已知初始为空的AVL树，依次插入的顺序是50,25,10,5,70,100,80,75，则插入5时需要进行什么调整？

解析：

1. 插入过程分析：
   • 插入5时导致结点25失衡（左左失衡）
   • 向上追溯：25的父节点10左子树插入导致50失衡（右子树插入后标记高度）
2. 需进行操作：
   • 首先对以25为根的子树进行单右旋
   • 然后对根节点50进行单左旋

三、红黑树（RBT）

3.1 核心性质

1. 每个节点是红色或黑色
2. 根节点是黑色
3. 每个叶子节点(NIL)是黑色（实际可能用空子节点代替）
4. 红色节点的子节点必须是黑色
5. 任意节点到其每个叶子的所有路径都包含相同数目的黑色节点

3.2 考研重点（选择/填空）

• 高度上界为 2log2(n+1)
• 最小黑节点路径包含 logN 黑节点
• 不要求完全平衡，但能保证查找效率 O(logN)

3.3 真题示例

真题3： 关于红黑树的说法正确的是？
A. 每个红色节点的左子节点一定是黑色
B. 黑高指从根到任一叶子路径上的黑色节点数目
C. 【具体某平衡结构更高效判断】
D. 插入50,30,总结90后三次比较出现RAUSE

解析：

• A：错误，红黑树保证没有相邻红色节点而不是交替
• B：正确，定义明确
• D：属于二叉排序树常规判断原型，选项与红黑无关

四、考点对比与备考策略

4.1 三大结构特性总结

4.2 考研复习重点

1. AVL旋转机制：眼睛练习对应旋转类型判断
2. RBT特性应用：能应用黑像素守恒原理
3. 注意"假排序树"陷阱题，如序列是否能生成特定形态BST

五、典型错误预防锦囊

1. BST退化问题
   错误：平均复杂度为 O(logN)
   正确：必须强调"平衡情况下"，否则蜕变成链表

2. RBT高度计算问题
   示例：判断结点15时红黑树的最大高度（考试常考）

3. 平衡判断时机
   注意AVL在插入节点后需从插入处回溯判断平衡性

C语言完整测试用例

（完整源码片段展示）

void testBST() {
    BSTree root = NULL;
    int arr[] = {5,2,8,3,6,1,9,7};
    for(int i=0; i<8; i++) {
        root = insertBST(root, arr[i]);
    }
    printf("构建BST完成！");
}

// 测试AVL单左旋
AVLTree testAVL_LL() {
    AVLTree root = NULL;
    root = insertAVL(root, 30);
    root = insertAVL(root, 20);
    root = insertAVL(root, 10); // 引发LL失衡
    return root;
}

六、强化训练建议

建议针对以下典型场景练习：

1. 手动模拟前中序恢复原结构
2. 画出插入调整过程（每年必考操作题）
3. 实现BST的delete操作
4. 掌握反复左旋/右旋的参数传递机制

✅ 代码完整率提升技巧：注意AVLNode需要height更新函数，RBT存储颜色需要重载结构

后续文章将系统的专项突破手写结构难题，欢迎收藏。