构造算法决策树

Question

在今天晚上的一次采访中，我被要求回答这个问题：

为该算法的任意三个输入构建决策树：

For i = 1 to n - 1 do
    If L[i] > L[i+1] 
       swap(L[i],L[i+1])
For i = n-1 downto 2 do
    If L[i] < L[i-1] 
       swap(L[i],L[i-1])

我认为我的答案是错误的，因为我得到了16个叶子。我做了以下工作：

                                    Root : 
                                  {a, b, c}
                                    /   \
                       (i>i+1)     /     \  (i<i+1)
                                  /       \
                              {b,a,c}        {a,b,c}
                               /   \          /   \
                              /     \        /     \
                             /       \      /       \
                       {b,c,a}   {b,a,c}   {a,c,b}   {a,b,c}

这完成了第一个循环，然后我以同样的方式将输入扩展到第二个循环，在每个节点假设一个决策<和一个决策>，每次都会从每个节点得到两个答案，最终给你16个叶子。

这是正确的吗？若否，应如何处理？

Answer 1

对于n = 3，第二个循环只运行一次，对于i = 2。因此，每个节点有两个答案，您将得到2*4 =8个叶子。