第4章树

作者: 橡树人 | 来源:发表于2020-03-06 05:01 被阅读0次

JZ-062-二叉查找树的第 K 个结点
【机器学习实战】第9章树回归
「每日一算法」什么是B-树
漫画算法：什么是 B 树？
漫画：什么是B-树？
漫画：什么是B-树？
【剑指Offer】062——二叉树的第k个结点（栈、树）
2018-11-29 第四部分图论部分第11章
B树算法普及和索引结构
剑指offer | 二叉搜索树的第k个结点

对于大规模输入，链表的线性访问时间是不可接受的。

在本章里，我们先介绍二叉搜索树这种简单的数据结构，其大部分操作的平均访问时间是 $O(\log N)$ 。接着，我们从理论上给出了对二叉搜索树的第一种简单修改，保证了在最坏情形下的运行时间上界是 $O(\log N)$ 。再接着，我们给出了对二叉搜索树的第二种修改，从本质上保证了对长指令的每种操作的运行时间都是 $O(\log N)$ 。

二叉搜索树是实现两个库集合类TreeSet和TreeMap的基础，这两个库集合类被许多应用使用。由于树这种结构在计算机科学中是一种非常有用的抽象，所以我们会讨论如何在其他更普遍的应用中使用树的，比如

如何应用树来实现几种流行的操作系统的文件系统。
如何使用树来计算表达式的值。
如何使用树来支持平均情形的 $O(\log N)$ 的搜索时间，及如何优化为最坏情形下的 $O(\log N)$ 上界，及当数据保存在硬盘上时，如何实现才能保证最坏情形下有 $O(\log N)$ 的搜索时间上界。
讨论如何使用集合类TreeSet和TreeMap。