[MIT6.006] 5. Binary Search Trees, BST Sort 二分搜索树，BST排序
第5节课主要讲述了二分搜索树概念和BST排序。讲师提出一个关于“跑道预订系统”的问题，假设飞机场只有一个跑道，飞机需要为未来降落时间t进行预订，如果时间集合R中，在t时间前后k分钟内没有其他飞机着陆计划，时间t可以被安排进R中。那么请问“时间t被安排进R”的时间复杂度能不能为Ο(log2n)（假设R长度为n）？
首先我们先看下图的一个例子：
如果现在时间是37, 然后R集合中，在41.2，49，和56.3三个时间点上，其他飞机已经预订了跑道。如果我此次要预订t=53进行着陆，是可以安排的因为49+3<53<56.3-3，而如果是t=44，飞机无法安排因为t=41.2的飞机着陆完毕后t=41.2+3=44.2>41.2。而t=20的时间也不能安排，因为现在已经是t=37了。“挨个遍历R中所有元素进行时间t的比较”下的时间复杂度是Ο(n)。
如果时间集合R是个已经排好序的数列，那么就可以用之前课程提到的二分查找法去做，具体如下图所示：
假设想要安排的时间t=34，那么我想从中间开始对比，t=34>32，那么之后就在数列右半边的中间数进行对比，最后找到插入点位于32和37之间。整个操作除了二分查找插入点还有移动（shifting，因为插入点后的数据需要向后移动），整个过程的时间复杂度是Ο(log2n+n)， n的原因是最坏情况下，插入点在数列首元素前面。
而如果通过第4节课的Heap来做，时间复杂度是Ο(n)。可见，以上三种方法都不能实现Ο(log2n)的时间复杂度，为此讲师提出了二分搜索树（BST）进行操作。BST的该概念如下图所示：
二分搜索树的属性是，对于所有结点x:
- 如果y是x的左子树，y的值 ≤ x的值；
- 如果y是x的右子树，y的值 ≥ x的值；
举个构建BST和插入飞机时间t的例子：
先重构建BST说起：
- 插入49，放在树的顶端；
- 插入79，因为79>49，放在49右下边；
- 插入46，因为46<49，放在49左下边；
- 插入41，因为41<46，放在41左下边。
此时要插入时间t=42（k=3）：
- 42<49-3，可以放在49左下边；
- 42<46-3，可以放在46左下边；
- 41+3>42，所以42不能放在41右下边，因此t=42不能被安排进R。
若h为BST的高，那么插入（不带检查）的时间复杂度是Ο(h)。
之后讲师提出一个新问题：求Rank(t) - 在时间≤t下，多少飞机能被安排进R？在回答这个问题之前，需要了解关于“子树尺寸subtree size”的概念，如下图所示：
子树尺寸subtree size = 当前结点（1个）+ 当前结点下所有结点数。
那么，在“时间≤t下，多少飞机能被安排进R？”的解决步骤如下：
- 树向下走到最终该达到的时间点（walk down tree to find desired time）；
- 对较小的结点进行添加操作（add in the nodes that are smaller）;
- 将左子树尺寸进行添加操作（add in the subtree size to the left）。
上面的步骤可能比较难理解，但通过下面例子就能很好的明白了：
- 如果问题中的t=79，那么先看BST的根节点：49<79，则+1；
- 看左子树：对49的左子树尺寸进行添加操作，则+2；
- 看右子树：79=79，则+1，对79的左子树尺寸进行添加操作，再加2；
最后结果为5（即时间≤79下，5个飞机能被安排进R）。
关于“时间t被安排进R”的时间复杂度能不能为Ο(log2n)？”和BST时间复杂度Ο(h)的关系将在后面课程进行讲解。
最新文章
- Gradle使用小结
- dingding post POST请求
- Android SDK Tools和Android SDK Platform-tools
- web应用配置
- Xcode全局断点
- ASP.NET 窗体间传值实现方法详解
- ubuntu下新建VPN连接
- 重装系统时，将MBR分区转为GPT 分区
- SQL Server索引进阶：第四级，页和区
- FileUtil
- 重新想象 Windows 8 Store Apps (22) - 文件系统: 访问文件夹和文件, 通过 AQS 搜索本地文件
- C#删除只读文件或文件夹(解决File.Delete无法删除文件)
- C++ Socket学习记录 -1
- C++生成dump文件
- 微信小程序基于最新版1.0开发者工具分享－小试牛刀(视频)+发布流程
- Struts(十四)：通用标签-form表单
- day21 Pythonpython time模块和datetime模块详解
- 模仿jQuery的ajax的封装
- 剑指offer（31）1~n整数中1出现的次数
- codeforces 578a//A Problem about Polyline// Codeforces Round #320 (Div. 1)