N元樹插入和搜索的複雜性是什麼？

我正在C＃中實現N-1ry樹。我想知道如何計算下面的方法的複雜性。這裏是我的代碼：N元樹插入和搜索的複雜性是什麼？

結構：

public class Node 
{ 
    public int Value { get; set; } 
    public Node Children { get; set; } 
    public Node Sibilings { get; set; } 

}

這種方法用於搜索：

public Node search(Node root, int data) 
{ 
    if (root == null) 
     return null; 

    if (data == root.Value) 
     return root; 

    Node t = search(root.Children, data); 
    if (t == null) 
     t = search(root.Sibilings, data); 
    return t; 
}

這種方法插入：

public void Add(int[] data) 
{ 
    Node temp = null; 
    temp = search(ROOT, data[0]); 

    if (temp == null) 
     temp = new Node(data[0]); 

    if (this.ROOT == null) 
     ROOT = temp; 
    Node parent = temp; 

    for (int j = 1; j <= this.NoOfChildrens; j++) 
    { 
     // for first child 
     if (j == 1) 
     { 
      parent.Children = new Node(data[j]); 
      parent = parent.Children; 
     } 
     //for all other childs 
     else 
     { 
      parent.Sibilings = new Node(data[j]); 
      parent = parent.Sibilings; 
     } 

    } 

}

程序入口點：

static void Main(string[] args) 
{ 
    NAryTree naryTree = new NAryTree(3); 

    // 1st element in each row is node Value,>=2nd....=>value of child 

    int[][] data = { new int[] { 1, 2, 3, 4 }, new int[] { 2, 1, 6,0 }, new int[] { 3, 8, 9, 10 }, new int[] { 4, 0, 0, 0 } }; 

    naryTree.Add(data[0]); 
    naryTree.Add(data[1]); 
    naryTree.Add(data[2]); 
    naryTree.Add(data[3]); 
    naryTree.Add(new int[] {10,3,6,4}); 

    naryTree.preorder(naryTree.ROOT); 
    Console.ReadLine(); 
}

這些方法的bigO複雜性是什麼？

來源

2015-12-13 Qasim Ahmed

你已經只顯示了一些代碼，但缺乏代碼來重新平衡孩子在Add方法中提示O（total_number_of_nodes）是最好的選擇（可能會更糟糕，這取決於其他方法有多糟糕）。平衡樹應該獲得O（log n）以進行添加/刪除/搜索。 –

我無法理解這段代碼。在我看來，搜索方法至少應該有一個'for'。另外我認爲一個節點不應該訪問它的兄弟姐妹。 – Tempux

我只是實現了N-Ary樹，我更新了我的問題 –

讓我們看看我們在Search方法中有什麼。它不是一棵二叉樹，我們有遞歸。因此，Search方法將調用N次直到我們找到必要的值。因此，我們可以得出結論，我們有O（N），其中N是最大（最差）迭代的號碼找到在最後一次迭代的值：

public Node search(Node root, int data) 
{ 
    if (root == null) 
     return null; 

    if (data == root.Value) 
     return root; 

    Node t = search(root.Children, data); 
    if (t == null) 
     t = search(root.Sibilings, data); 
    return t; 
}

加法方法更簡單，因爲我們有for聲明，任何嵌套循環。所以我們有O(N)爲Addition方法。

As Wisconsin university says:

所以對於for循環（I = 0;我< N;我++）{ 序列語句}的循環執行了N次，那麼語句序列也執行N次。由於我們假設語句爲O（1），所以for循環的總時間爲N（0）（1），，其總體爲O（N）。

來源

2015-12-13 21:13:10 StepUp

N元樹插入和搜索的複雜性是什麼？

回答

相關問題