信息技术大学
二叉搜索树
数据结构与算法·面试高频 · 第 2 章 树与图
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
二叉搜索树
数据结构与算法·面试高频 · 第 2 章 树与图
BST 性质与验证
左小右大层层成立：BST 把有序性种进了树结构，验证却别只比父子。
性质
左子树全小于根，右子树全大于根
验证陷阱
只比父子会漏判孙辈越界，要带上下界递归
中序验证
中序遍历严格递增，即合法 BST
BST 增删节点
插入走到空位挂上即可；删除分三档：叶子直接摘，单孩接位，双孩找后继。
插入
按大小走到空位，新节点挂上即完成
删除双孩
右子树最小者（后继）顶替，再去删后继原位
复杂度
平均 O(log n)，退化成链表时 O(n)
中序有序性应用
BST 的中序就是排序结果：第 K 小、找错误对，全靠这一条有序性。
第 K 小
中序遍历计数，第 K 个弹出即答案
纠错定位
中序序列里的逆序对，即被交换的两节点
平衡树概念（AVL/红黑树）
退化是 BST 的命门：平衡树用旋转兜住层高，红黑树是工业界的折中赢家。
AVL
严格平衡，子树高差 ≤1，查询快、调整勤
红黑树
五条性质近似平衡，增删查稳定 O(log n)
应用
TreeMap、epoll 的 fd 管理、内核调度器
本节要点
- ✓BST：左小右大，验证带上下界
- ✓删除双孩节点，找后继顶替
- ✓中序有序：第 K 小与纠错全靠它
- ✓红黑树近似平衡，工业首选
延伸主题：手写 BST 删除用 BST 实现第 K 小
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1验证 BST 为什么不能只比较子与父？
参考答案BST 的约束作用于整棵子树：右子树的左孙完全可能比根还小。只比父子挡不住跨层越界；带（下界，上界）递归或检查中序严格递增才是正确姿势。
2删除双孩节点为什么找后继来顶替？
参考答案后继是右子树的最小值，比左子树都大、比右子树其余都小，顶替后左右性质都不破坏；且它至多有一个右孩子，删除它又退化为简单情形。
3红黑树为什么比 AVL 更受工程欢迎？
参考答案AVL 严格平衡查询更快，但插删要频繁旋转维护；红黑树近似平衡，调整少、增删查综合稳定。工业场景写多读杂，少折腾的红黑树胜出。