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

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

一、二叉排序树（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 三大结构特性总结

特性	BST	AVL	红黑树
平均查找效率	O(logN)	O(logN)	O(logN)
最坏效率	O(N)	O(logN)	O(logN)
动态操作调整	不调整	高度差>1立即调整	最多旋转2次
用途	理解基础	插入/考点	高频应用点

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存储颜色需要重载结构

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