我正在实施BST。
现在我想重新平衡我的树。我已经做了一个可以在O(nlogn)中完成的实现，但是当我用Google搜索一下时，我发现在O(n)中是可行的，但是我找不到如何实现。这是我的代码:
现在，方法isBalanced()需要O(n)时间，并检查我的树是否平衡。我可以删除该语句，但是toArrayList()方法也需要O(n)时间。这种方法给了我一个arraylist，树中的所有节点从最低到最高排序。
因此，如果我使用master方法计算我的复杂度，我会得到O(nlogn)作为复杂度。我真的不知道如何在不使用arraylist / array的情况下实现它。我已经检查了Day-stout-warren算法，但我不明白:)
最佳答案
您的算法具有线性时间复杂度。重复关系是T(n) = 2 * T(n / 2) + O(1)，所以是T(n) = O(n)。