分而治之三元树搜索
Divide and Conquer Ternary Tree Search
我正在尝试解决一个练习，给你一个完美的三元树，其中每个节点都包含一个整数。我们要计算有多少内部节点满足这些规范：
- 节点数大于其所有children
- 最大的child是中间的
例如，在下面的树中，只有 3 个节点符合这些规范
设计并分析分治算法，计算满足规范的节点数。这个算法应该是O(n)的，其中n是叶子的个数，n是3的幂。不考虑树的数据结构，只解释一个算法
所以我尝试设计这个算法：
我是算法设计的新手，我不知道我所做的时间复杂度是多少，甚至不知道它是分而治之的算法。如果您知道如何帮助我计算这个的时间复杂度或检查它是否真的是一个分而治之的解决方案，请告诉我。另外，如果您有比我更好的想法，请帮忙。谢谢
首先，几乎每个递归都可以视为分而治之，因为您将问题拆分为子问题。
其次，请注意您最多访问树的每个节点一次，因此 运行 时间确实是您希望的 O(n)
- 我刚刚注意到您将
n 定义为叶子数，而不是节点数，但分析仍然有效，因为对于高度为 h 的树，节点数是1+3+..+3^h-1 = O(3^h) 并且在 h 层中恰好有 3^h 个叶子。所以该算法确实在 ~O(3n)=O(n) 时间 中运行
最后一点，我觉得你做的其实很好！但实际上，我认为在这种情况下编写递归主要是按“分支”而不是按级别，这意味着你先深入再深入。
为了更清楚地说明这一点，我的意思是最终代码将如下所示：
def countSpeacialNodes (Node t):
if t doesnt have children: return 0
if t is bigger than its children AND t's biggest child is the middle:
return 1+CSN(t.left)+CSN(t.middle)+CSN(t.right)
else return CSN(t.left)+CSN(t.middle)+CSN(t.right)
所以对于summarist来说，你可以注意到这里前进到树的深度而不是树的“宽度”，而且没有必要标记节点
希望对您有所帮助
我正在尝试解决一个练习，给你一个完美的三元树，其中每个节点都包含一个整数。我们要计算有多少内部节点满足这些规范：
- 节点数大于其所有children
- 最大的child是中间的
例如，在下面的树中，只有 3 个节点符合这些规范
设计并分析分治算法，计算满足规范的节点数。这个算法应该是O(n)的，其中n是叶子的个数，n是3的幂。不考虑树的数据结构，只解释一个算法
所以我尝试设计这个算法：
首先，几乎每个递归都可以视为分而治之，因为您将问题拆分为子问题。
其次，请注意您最多访问树的每个节点一次，因此 运行 时间确实是您希望的 O(n)
- 我刚刚注意到您将
n定义为叶子数，而不是节点数，但分析仍然有效，因为对于高度为h的树，节点数是1+3+..+3^h-1 = O(3^h)并且在h层中恰好有3^h个叶子。所以该算法确实在 ~O(3n)=O(n) 时间 中运行
最后一点，我觉得你做的其实很好！但实际上，我认为在这种情况下编写递归主要是按“分支”而不是按级别，这意味着你先深入再深入。 为了更清楚地说明这一点，我的意思是最终代码将如下所示：
def countSpeacialNodes (Node t):
if t doesnt have children: return 0
if t is bigger than its children AND t's biggest child is the middle:
return 1+CSN(t.left)+CSN(t.middle)+CSN(t.right)
else return CSN(t.left)+CSN(t.middle)+CSN(t.right)
所以对于summarist来说，你可以注意到这里前进到树的深度而不是树的“宽度”，而且没有必要标记节点
希望对您有所帮助