二叉排序树

一、性质

1. 左子树 < 根节点
2. 右子树 > 根节点
3. 中序遍历的结果，是一个有序序列

数据结构，就是定义一种性质，并且维护这种性质。

二、插入操作

1. 插入的新节点，一定会做为叶子结点

三、删除操作

1. 删除度为0的节点，直接删除
2. 删除度为1的节点，把『孤儿子树』挂到其父节点上面去
3. 删除度为2的节点，可以转化成删除度为1的节点

对于度为2的节点：

1. 前驱：左子树最大值
2. 后继：右子树最小值

四、随堂练习

1. 插入顺序会影响最终的树形结构
2. 不同的树形结构，查找效率不同

平均查找效率：节点查找次数的期望值，$\frac{总次数}{节点数量}$，假设每个节点等概率的被查找

五、扩展内容

1. 二叉排序树的删除代码优化
   1. 删除掉处理度为0的代码逻辑，不影响代码整体功能
2. 如何解决==排名==相关的检索需求
   1. 修改二叉排序树的结构定义，增加 size 字段，记录每棵树的节点数量
   2. $k = LS - 1$，根节点就是排名第 k 位的元素
   3. $k \le LS$，排名第 k 位的元素在左子树中
   4. $k \gt LS，search_k(root->rchild, k - LS - 1)$
3. 解决 Top-K 问题（找到小于第 k 位的所有元素）
   1. 根节点就是第 k 位元素的话，就把左子树中的值全部输出出来
   2. 第 k 位在左子树中，前 k 位元素全都在左子树中
   3. 第 k 位在右子树中，说明根节点和左子树中的元素，都是前 k 位元素里面的值
4. 二叉排序树和快速排序的关系
   1. 二叉排序树是快速排序在思维逻辑结构层面用的数据结构
   2. 思考1：快速排序的时间复杂度和二叉排序树建树时间复杂度之间的关系
   3. 思考2：快速选择算法和二叉排序树之间的关系
   4. 程序=算法+数据结构

所谓算法设计及分析能力：分类讨论及归纳总结的能力

---

• ← Previous Post
• Next Post →