Нахождение самого левого потомка для каждого узла дерева в линейном времени?

Статья , которую я читаю, утверждает, что

Легко видеть, что существует алгоритм линейного времени для вычисления функции l()

Где l() дает самый левый потомок (и вход, и выход находятся в поступорядоченном обходе дерева). Однако я могу думать только о наивной реализации O(n^2), где n - это число узлов в дереве.

В качестве примера рассмотрим следующее дерево: 
  a
 / 
c   b

При обходе после заказа, дерево - это c b a. Соответствующая функция l() должна давать c b c.

Вот моя реализация во времени O(n^2). 

public Object[] computeFunctionL(){
    ArrayList<String> l= new ArrayList<String>();
    l= l(this, l);
    return l.toArray();
}

private ArrayList<String> l(Node currentRoot, ArrayList<String> l){
    for (int i= 0; i < currentRoot.children.size(); i++){
        l= l(currentRoot.children.get(i), l);
    }
    while(currentRoot.children.size() != 0){
        currentRoot= currentRoot.children.get(0);
    }
    l.add(currentRoot.label);
    return l;
}

Дерево сделано так: 

public class Node {
private String label;
private ArrayList<Node> children= new ArrayList<Node>();
...
3 2
theory algorithm data-structures graph-theory

3 ответа:

Существует простой рекурсивный алгоритм, который может вычислить эту информацию за O (1) Время на узел. Поскольку существует n полных узлов, это будет выполняться за O(n) общее время.

Основная идея заключается в следующем рекурсивном понимании:
  • для любого узла n без левого потомка l (n) = n.
  • в противном случае, если n оставил ребенка L, то l(n) = l(L).
Это дает начало этому рекурсивному алгоритму, который аннотирует каждый узел своим значением l: 
function computeL(node n) {
   if n is null, return.

   computeL(n.left)
   computeL(n.right)

   if n has no left child:
      set n.l = n
   else
      set n.l = n.left.l

Надежда это помогает!

1

Вы можете найти l() для всего дерева менее чем за O(n^2) времени. Идея состоит в том, чтобы обойти дерево по порядку, поддерживая стек узлов, которые вы посетили, проходя левую ветвь. Когда вы добираетесь до листа, это самый левый узел для всей ветви.

Вот пример: 

class BTreeNode
{
    public readonly int Value;
    public BTreeNode LeftChild { get; private set; }
    public BTreeNode RightChild { get; private set; }
}

void ShowLeftmost(BTreeNode node, Stack<int> stack)
{
    if (node.LeftChild == null)
    {
        // this is the leftmost node of every node on the stack
        while (stack.Count > 0)
        {
            var v = stack.Pop();
            Console.WriteLine("Leftmost node of {0} is {1}", v, node.Value);
        }
    }
    else
    {
        // push this value onto the stack so that
        // we can add its leftmost node when we find it.
        stack.Push(node.Value);
        ShowLeftmost(node.LeftChild, stack);
    }
    if (node.RightChild != null)
        ShowLeftmost(node.RightChild, stack);
}

Сложность явно не O (n^2). Скорее, это O (n).

Требуется O(n), чтобы пересечь дерево. Ни один узел не помещается в стек более одного раза. Худший случай для этого алгоритм-это дерево, содержащее все левые узлы. В этом случае нужно O(n) пересечь дерево и o (n) перечислить стек. В лучшем случае это дерево, содержащее все правильные узлы,и в этом случае нет никакого стека для перечисления.

Таким образом, O (n) временная сложность, с O(n) наихудшим дополнительным пространством для стека.

1

Взгляните на раздел 3.1:

[0]}3.1. Нотация. Пусть T[i]-это I-й узел в дереве в соответствии с соотношением слева направо. нумерация после заказа, l (i) - номер самого левого листового потомка поддерева укоренен в T[i].

Учитывая это предложение о нотации, я бы предположил, что функция l () относится к нахождению одного узла в линейном времени.

Может быть более элегантный(лучше, чем O (n^2)) способ найти l () для всего дерева, но я думаю, что это относится к одному узлу.

0