binary-tree - 平衡 BST 与平衡二叉树：复杂性

Question

我正在确定平衡 BST 与平衡 BT 上不同操作的复杂性。我想知道我是否已经弄清楚了正确的复杂性。操作如下，

寻找最小的元素

对于平衡的 BST，这将是 O(LogN)，对于 BT，这将是 O(N)。

在 PreOrder 中创建元素列表

这对于两者来说都是 O(N)，因为所有节点都将被遍历。

创建一个小于某个值的元素列表 v

这对于两者来说都是 O(N)，尽管使用中序遍历实现平衡的 BST 可能会快得多。

从树上取下所有叶子

这对于两者来说都是 O(N)，需要遍历所有节点才能找到叶节点。

这些结论正确吗？

标签： binary-treebinary-search-treecomplexity-theoryverify