han*_*dev 3 time complexity-theory traversal binary-search-tree
通常,如果使用深度优先遍历,我们就有O(n)时间.但是,如果我们首先找到最小元素然后调用successor()方法n时间,那么它的时间复杂度是多少？
我想这可能是O(n log n)因为继任者O(log n)似乎并不正确.任何人都可以在这里提供任何深入的分析(可能涉及一些限制分析)？
如果每个节点都存在父指针,则调用后继方法n次需要O(n)时间.要看到这一点,观察到树中的每个边缘最多被访问两次(一次从父到子,一次从子到父)由所有后继调用组合.因此,所有后继呼叫所访问的边缘总数最多为2n.所以运行时间是O(n).
现在,如果不存在父指针,则在每个调用中我们必须从根开始并通过遍历O(log n)节点(如果树是平衡的)来搜索后继元素.因此复杂性变为O(n log n).