二叉搜索樹中最常見的元素

我們如何找到BST中最常出現的元素？我想過使用哈希映射來實現它。有沒有簡單的方法？二叉搜索樹中最常見的元素

來源

2013-07-13 Jayram Singh

請注意，「最常見的元素」意味着你允許重複。如果每個密鑰都是唯一的，那麼樹中的所有密鑰的頻率都是** 1 **。（並且不存在的鍵明顯爲零的頻率） – wildplasser

它可以在一個以上的方式來完成 -

執行BST的Inorder Traversal。這會給你一個元素的排序列表。做一個線性遍歷來找到最重複的元素。 time O(n) space O(n)
像你說的Hashtable。做任何BST的DFS traversals。將每個元素插入一個散列表，並將計數設置爲1.如果元素已經存在，則增加count + 1。然後遍歷哈希表來找出頻繁出現的元素。最差情況下的時間爲O(n)，空間爲O(n)，但在實踐中，如果數據集有大量重複項，此方法應占用較少的空間。

來源

2013-07-13 13:06:35

寧願在進行遍歷而不是再次遍歷元素時執行它。 –

@RajHassani第二種情況導致空間利用率較低，這可能是可取的。 –

那就是做最徹底的方法：

初始化哈希映射，它映射一個值，其數量發生。
迭代BST有序：
- 散列[node.value] + = 1

你可以在適當的位置（O(1)額外存儲器的複雜性）：

保持2 O(1)變量指示出現次數和元素的最大數量，按順序迭代樹，保證它以不斷增加的方式進行更新，並更新元素最大的事件：

curmax = 0 
maxnode = null 
for each node in BST.inorder(): 
    if next.value == node.value: 
     max ++ 
    else: 
     max = 1 
    if max > curmax: 
     curmax = max 
     maxnode = node

來源

2013-07-13 13:08:18 0x90

這個問題相當於一個排序的數組找到最常見的元素 - 同樣的算法應用：

啓動計數器在零
增加計數器而當前元素等於前一個元素
當您找到一個不同的元素時，將計數器與當前最佳運行進行比較;是否有必要更換
繼續到下一個元素

唯一的區別是，而不是用一個循環數組遍歷你做一個樹的遍歷用遞歸函數。在這兩種情況下，該算法在樹中的元素數量上都是線性的。如果樹是平衡的，則算法需要調用棧上的空間爲O(LogN)。

來源

2013-07-13 13:08:43 dasblinkenlight

自BST以來。它不能被認爲是平衡的。 –

@SrikarAppal他沒有假設它是平衡的，他只是給出算法的時間複雜度將會是_如果它是平衡的。雖然，公平地說，他也應該給出完全線性樹（最大不平衡）的複雜性。 – AJMansfield

是的，他沒有假設。但我的觀點並非如此。對於最大不平衡的BST，在這種情況下所用的空間將是堆棧中的「O（n）」，這與在BST中進行遍歷，將元素存儲在數組中並且線性掃描以找到最頻繁的元素一樣好。我猜這兩種方法都沒有錯...... –

我們可以像上述那樣使用修改的inorder遍歷並跟蹤上一個元素。

TreeNode prev = null; 
int count = 1, max = 0; 
List<Integer> list = new ArrayList<>(); 


private void inorder(TreeNode root) { 
    if (root == null) return; 
    inorder(root.left); 
    if (prev != null) { 
     if (root.val == prev.val) 
      count++; 
     else 
      count = 1; 
    } 
    if (count > max) { 
     max = count; 
     list.clear(); 
     list.add(root.val); 
    } else if (count == max) { 
     list.add(root.val); 
    } 
    prev = root; 
    inorder(root.right); 
}

由於序遍歷讓我們按升序排列元素這一技術是有用的，這裏的列表將包含這些元素。

來源

2017-03-16 04:39:45

二叉搜索樹中最常見的元素

回答

相關問題