查找树search tree: 一种数据结构,支持多种动态集合操作。search, minimum, maximum, predecessor, successor, insert, delete等
可以用作字典,也可以用作优先队列
binary search tree中,执行基本操作的时间和树的高度成正比。
随机构造的n节点bst,最坏情况运行时间是O(lg n)
但如果树是n结点的线性链,这些操作的最坏情况运行时间是O(n)
bst的问题:如何保证随机构造?或者,某些变种能使得最坏情况性能仍然不错?(红黑树)
bst基本性质:
设x是bst的某结点。则 key[LeftChild[x]]<=key[x]. key[RightChild[x]]>=key[x].
Inorder. PreOrder. PostOrder. 时间是O(n)(n为bst的结点数)
递归版本,非递归版本
中序输出算法可以按顺序输出n个结点,时间是O(n)(假设bst已经构造好)
与最小堆比较:能否在O(n)时间内,按序输出含有n个结点的树中的关键字?