将一般树转换为二叉树的时间和空间复杂度是多少?!
谢谢
不知道你说的“将军树”是什么意思。无论如何,插入平衡二叉树的时间复杂度是
O(log n)
,其中 n
是树中当前的项目数,因此从一些项目列表构建完整的树将是 O(n log n)
,其中 n
是要插入的项目总数。
您还必须包括从另一棵树上获取物品所需的时间。那个时间取决于你拥有的树的类型。为了争论,我假设你可以在线性时间内遍历它,所以从现有树中获取数据是
O(n)
.
这使您的总时间复杂度
O(n + (n log n))
.
所需的额外空间将是
n * sizeof(node)
,其中 sizeof(node)
是二叉树节点的大小。请注意,如果存储在“通用树”节点中的项目是指针,则您不必支付复制实际对象的成本——只是二叉树节点的开销,通常是三个指针:数据、左子链接和右子链接。