如何在O（N）時間構建二叉樹？

繼續前面的問題here我很想知道如何從N個未排序的大整數的數組中構建一個N次的二叉樹？如何在O（N）時間構建二叉樹？

2016-03-07 Shane MacLaughlin

這很好。祝你好運。你有問題嗎？ –

據我所知，這是不可能的，因爲這意味着你可以在O（n）時間排序列表。 –

是的。如何在O（n）時間從未排序的整數構建二叉樹？ –

好吧，只是爲了完整性...問題中的二叉樹是從一個數組構建的，並且每個數組元素都有一個葉。它使它們保持原有的索引的順序，的值不是的順序，所以它不會讓你神奇地讓你在線性時間排序。它也需要平衡。

打造線性一次這樣的樹，你可以用一個簡單的遞歸算法是這樣的（使用基於0的索引）：

//build a tree of elements [start, end) in array 
//precondition: end > start 
buildTree(int[] array, int start, int end) 
{ 
    if (end-start > 1) 
    { 
     int mid = (start+end)>>1; 
     left = buildTree(array, start, mid); 
     right = buildTree(array, mid, end); 
     return new InternalNode(left,right); 
    } 
    else 
    { 
     return new LeafNode(array[start]); 
    } 
}

來源

2016-03-07 21:30:23

謝謝，我誤解了不需要排序的樹。 –

@MattTimmermans：我將帽子重新格式化爲粗體，因爲帽子（至少在SO上）被認爲是粗魯的。 –

除非在列表中有一些前提條件允許您在常量時間內爲每個項目計算樹中的位置，否則無法'構建'，即按順序將項插入到O中的樹中（N）時間。每個插入必須最多與Log M次進行比較，其中M是樹中已有項目的數量。

來源

2016-03-07 19:23:20 tt9

這就是我的理解，。這就是說，僅僅因爲我們沒有看到算法並不意味着它不存在。 –

二叉搜索樹是計算機科學中研究最多的主題之一。他們建立在比較原則的基礎上。已經證明，基於BST的最快插入比較是O（log n）。要獲得比這更快的速度，你需要在數據集中有一些預先存在的結構。例如，如果你知道你的數據集已經被排序了，你可以想出一個更快的方法來構建樹。 – tt9

@ user2313300是真實的，但這意味着能夠解決O（n）中的'SORT'，這已被證明是不可能的。 –

我同意，這在一般的似乎是不可能的（假設我們有一個一般的，全序集小號的ñ項目。）下面是一個非正式的說法，我本質上降低BST建設上小號到排序問題S。

非正式的論點。讓S是一組N元素。現在構建二進制搜索樹T，其存儲來自S的項目O（N）時間。

現在，當您訪問它們時，請執行樹的逐步走動並打印葉子的值。您基本上對S中的元素進行了排序。這帶你O（| T |）步驟，其中| T |是樹的大小（即節點的數量）。（在BST的大小是O（N日誌N）在最壞的情況下。）

如果| T | = O（N日誌N）那麼你只解決了普通的排序問題在O（ N日誌N）這是一個矛盾的時間。

來源

2016-03-07 19:33:31 blazs

我同意這是不可能的一般情況下，有大量的可能值的項目正在排序。如果要排序的項目有少量可能的值，並且這些值可以枚舉，則可以使用類似計數排序的東西在O（N）中進行排序，請參閱https://en.wikipedia.org/wiki/。 Counting_sort如果我們可以在這種情況下在O（n）中排序，我想我們也可以構造一棵樹。 –

**如果**給出了一個排序數組，那麼你可以在線性時間內構建一個二叉搜索樹，但是隻有當表達式需要* O（N）*空間時（即你使用類似於堆的方式使用數組）。我認爲問題在於這是否可能。 – blazs

含糊的想法：1.排序數組; 2.將排序數組的中間元素放入根中; 3.對子陣列進行遞歸（第一和最後一半），即將它們的根分別作爲第二和第三個元素。（索引i處元素的左邊孩子是2 * i;右邊孩子是2 * i + 1。） – blazs

我有一個想法，它是如何可能的。

使用RadixSort排序數組，這是O（N）。此後，用遞歸程序插入到葉子，如：

node *insert(int *array, int size) { 
    if(size <= 0) 
    return NULL; 
    node *rc = new node; 
    int midpoint = size/2; 
    rc->data = array[midpoint]; 
    rc->left = insert(array, midpoint); 
    rc->right = insert(array + midpoint + 1, size - midpoint - 1); 
    return rc; 
}

由於我們沒有從上往下遍歷樹，但總是將節點連接到當前葉子，這也是O（1）。

來源

2016-03-07 20:55:24 maxihatop

如果對整數沒有上限，則不能在O（N）中使用RadixSort。 – Mickey

如何在O（N）時間構建二叉樹？

回答

相關問題