GATE 2008：二叉搜索树的时间复杂度

Question

给你一个二叉搜索树的post阶遍历P，对n个元素1,2,.........,n。您必须确定以 P 作为其 post 顺序遍历的唯一二叉搜索树。 最有效算法的时间复杂度是多少？

(a) theeta(logn)

(b) theeta(n)

(c) theeta(nlogn)

(d) none of the above, as tree cannot be uniquely determined

答案是(b)，请说明解决方法。如果我们已经得到 post-order 遍历，我们不需要应用 sorting(O(nlogn)) 来按顺序计算吗？

Answer 1

不，您不必对它进行排序。

在post阶遍历中可以找到一些隐藏的信息。喜欢：

最后一个元素总是树根
前面所有大于根的元素都是右子树的一部分。所有较小的元素都是左子树的一部分。
您可以递归地应用上述规则。

之所以如此，是因为您只有不同的元素。如果有重复，遍历的树就不可能是唯一的。

这是一个示例实现（在 Python 中）显示了这一点：

from collections import deque

def visit(in_queue, limit = None):
    if len(in_queue) == 0 or in_queue[-1] < limit:
        return None
    root = in_queue.pop()
    right = visit(in_queue, max(root, limit))
    left = visit(in_queue, limit)

    if left is None and right is None:
        return root
    else:
        return (left, root, right)

def print_graphviz(tree):
    if not isinstance(tree, tuple):
        return tree
    left = print_graphviz(tree[0])
    right = print_graphviz(tree[2])

    if left is not None: print tree[1], '->', left
    if right is not None: print tree[1], '->', right
    return tree[1]

def make_tree(post_order):
    return visit(deque(post_order))

print 'digraph {'
print print_graphviz(make_tree([0, 2, 1, 4, 3, 6, 8, 7, 5]))
print '}'

运行像这样：

python test.py | dot -Tpng | display

你会得到一个漂亮的树输出：

Answer 2

你可以取中心元素（它是这个子树的根），左树将使用较小的数字构建，右树将使用较大的数字构建（一切都使用递归）。在伪代码中：

make_BST(T[]):

如果 T 中的元素少于 2 个：return 具有此元素的树
否则：return 树的根是 T 的中心元素（我们将其命名为 x），左子将是 make_BST（T 中小于 x 的元素），右子将是make_BST（T 中大于 x 的元素）

当然你应该只记住整个T和所考虑范围的左右边界。

该算法的复杂度为 T(n) = T(n/2) + T(n/2) + O(1) 所以 T(n) = O(n) 所以这与上面 post 中的复杂性相同。

Answer 3

在postoders遍历中，根总能在最后一个节点找到，所以需要o(logn)的时间复杂度。现在，在快速排序中，以根为轴心，小于根的元素在左侧，其余元素在右侧，假设有 k 个这样的元素小于根。所以，递归方程是，

T(n)=T(k)+T(n-k-1)+O(logn)

现在，在最坏的情况下让 k=0，所以等式看起来像

T(n)=T(n-1)+O(logn)

求解得到

T(n)=O(logn!) [O(logn)= O(log1)+O(log2)+O(log3)+...+O(logn)] 这将小于 O(logn)+O(logn)+...+O(logn).

所以，我们可以得到上层O(nlogn)。

答案：- theta(n logn)

GATE 2008：二叉搜索树的时间复杂度

GATE 2008: Time Complexity of Binary Search Tree

algorithm

binary-tree

binary-search-tree