建设BST的

Question

http://www.geeksforgeeks.org/group-multiple-occurrence-of-array-elements-ordered-by-first-occurrence/

请检查这个问题。

如何做BST方法这个问题。

他们提到总时间复杂度将是O（NLogN）。

树的时间复杂度是如何遍历LogN的？

请帮

Answer 1

搜索，删除和插入运行时间都依赖于树的高度，或为O(h) BST。退化树几乎看起来像一个链表可以产生O(N)的运行时间。

。另一方面，考虑一个自我平衡的树，如AVL树中，查找运行时间低了O(logN)界定，因为像二进制搜索，我们通过各一半时间在左，右子树划分搜索空间高度几乎相同。