二叉树到DLL转换的时间复杂度
time complexity of binary tree to DLL conversion
我正在研究一种将二叉树转换为双 Link 列表 (DLL) 的算法。
1. If left subtree exists, process the left subtree
…..1.a) Recursively convert the left subtree to DLL.
…..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
…..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
…..2.a) Recursively convert the right subtree to DLL.
…..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
…..2.c) Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).
这个算法的时间复杂度是多少？
这是一个link的程序
http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/
首先我们可以看到所有节点在其后代的 root 角色中被访问了一次。除了在步骤 1.b 和 2.b[= 中执行的循环外，为一个这样的根所做的所有工作都是不变的57=]，除了递归地为后代节点完成的工作。
我们可以说算法在 O(n) + O(f(n)) 中运行，其中 f 需要仍然定义，但第一项 O(n) 说明所有节点在除那些循环之外的所有步骤上花费的时间。
由于我最初的回答是错误的，我现在进入一些（可能太多）细节以获得正确的答案：
在完全平衡的树中，具有 n 个节点的树的每个（子）根执行的循环迭代次数对应于深度 d(n) 那棵树。这个 d(n) 对应于（对于平衡树）： log2(n+1) .如果我们将执行left->right!=NULL和right->left!=NULL的工作算作一个工作单元（在this code中），那么每个节点的执行单元数是d(n) .
如果我们从递归中累加这个时间，我们得到每个节点数的工作单元总数n:
f(1) = 1
f(n) = 2.f((n-1)/2) + d(n)
在table:
| n | d(n)=log(n+1) | f(n) |
+----+---------------+------+
| 1 | 1 | 1 |
| 3 | 2 | 4 |
| 7 | 3 | 11 |
| 15 | 4 | 26 |
| 31 | 5 | 57 |
| .. | .. | .. |
根据公式，f(n) 列中的值对应于它上面的值加上它旁边的值的两倍。
可以计算出 f(n) = 2d+1-d-2 = 2n-log(n+1)，上面的table表示第一列减去第二列的两倍就是第三列。
在时间复杂度表示法中可以去掉常数项，常数因子可以设置为1，增加n增长最快的项抵消掉其他项，所以我们最终得到 O(n)。
因为每个节点的恒定时间我们已经有 O(n)，所以没有任何变化。获得中序 predecessor/successor 所花费的时间不会影响总时间复杂度。
因此时间复杂度是O(n).
我正在研究一种将二叉树转换为双 Link 列表 (DLL) 的算法。
1. If left subtree exists, process the left subtree
…..1.a) Recursively convert the left subtree to DLL.
…..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
…..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
…..2.a) Recursively convert the right subtree to DLL.
…..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
…..2.c) Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).
这个算法的时间复杂度是多少？
这是一个link的程序 http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/
首先我们可以看到所有节点在其后代的 root 角色中被访问了一次。除了在步骤 1.b 和 2.b[= 中执行的循环外，为一个这样的根所做的所有工作都是不变的57=]，除了递归地为后代节点完成的工作。
我们可以说算法在 O(n) + O(f(n)) 中运行，其中 f 需要仍然定义，但第一项 O(n) 说明所有节点在除那些循环之外的所有步骤上花费的时间。
由于我最初的回答是错误的，我现在进入一些（可能太多）细节以获得正确的答案：
在完全平衡的树中，具有 n 个节点的树的每个（子）根执行的循环迭代次数对应于深度 d(n) 那棵树。这个 d(n) 对应于（对于平衡树）： log2(n+1) .如果我们将执行left->right!=NULL和right->left!=NULL的工作算作一个工作单元（在this code中），那么每个节点的执行单元数是d(n) .
如果我们从递归中累加这个时间，我们得到每个节点数的工作单元总数n:
f(1) = 1
f(n) = 2.f((n-1)/2) + d(n)
在table:
| n | d(n)=log(n+1) | f(n) |
+----+---------------+------+
| 1 | 1 | 1 |
| 3 | 2 | 4 |
| 7 | 3 | 11 |
| 15 | 4 | 26 |
| 31 | 5 | 57 |
| .. | .. | .. |
根据公式，f(n) 列中的值对应于它上面的值加上它旁边的值的两倍。
可以计算出 f(n) = 2d+1-d-2 = 2n-log(n+1)，上面的table表示第一列减去第二列的两倍就是第三列。
在时间复杂度表示法中可以去掉常数项，常数因子可以设置为1，增加n增长最快的项抵消掉其他项，所以我们最终得到 O(n)。
因为每个节点的恒定时间我们已经有 O(n)，所以没有任何变化。获得中序 predecessor/successor 所花费的时间不会影响总时间复杂度。
因此时间复杂度是O(n).