如何打印出二叉搜索树中第 n 个最频繁出现的词？

Question

这关系到"a software algorithm"https://whosebug.com/help/on-topic

我目前正在编写一个单词计数器字典程序。为了存储不同的字数，我使用了二进制搜索三，其中字为键，频率为值。

这是我的二叉搜索树 class

public class BinarySearchTree<AnyKey extends Comparable<? super AnyKey>, AnyValue>
    implements MyTreeMap<AnyKey, AnyValue>{
              protected BinaryNode<AnyKey, AnyValue> root;
              protected BinaryNode<AnyKey, AnyValue> insert(AnyKey x, 
                      AnyValue y, BinaryNode<AnyKey, AnyValue> t ){
                    if( t == null )
                         t = new BinaryNode<AnyKey, AnyValue>(x, y );
                   else if( x.compareTo( t.element ) < 0 )
                         t.left = insert( x, y, t.left );
                  else if( x.compareTo( t.element ) > 0 )
                        t.right = insert( x, y, t.right );
                 else
                          throw new IllegalArgumentException( x.toString( ) );  
                return t;
      }

这是我的节点 class

class BinaryNode<AnyKey, AnyValue> {
      BinaryNode( AnyKey theElement, AnyValue theValue ){
          element = theElement;
          value = theValue;
          left = right = null;
       }
       AnyKey             element; 
       AnyValue    value;
        BinaryNode<AnyKey, AnyValue> left;    
       BinaryNode<AnyKey, AnyValue> right;  
     }

我正在尝试在我的二进制搜索树中编写此方法

@Override
public void PrintMostFrequent(int n) {

}

它会根据频率打印出第n个最常见的单词。我有一个关于如何在伪代码中执行此操作的想法。
1。创建一个集合来保存节点
2。将树中的所有节点添加到此集合
3。根据计数对集合进行排序
4。迭代排序的集合并打印出第 n 个最频繁的。

这是解决这个problem/write这个方法的最佳方法吗？我担心创建一个单独的集合可能过于昂贵，而且排序在计算上也会很昂贵。

Answer 1

你的方法描述的也很不错。当您考虑需要在树中添加一个插入新词时，这将很复杂，这将需要 O(logn) 和排序列表 O(n) 在最坏的情况下然后再次搜索 O(n)。

为了更好地搜索第 n 个频繁节点并插入一种方法，可以创建 另一个 BST 但频率为。因此，在两棵树中插入一个新节点都需要 O(logn) 和搜索 O(logn) 。

在上述方法中，您有数据冗余，即第二棵树将同时具有单词和频率。因此，为了避免你可以做的是在第二个 BST 中只需将频率和一个对单词节点的引用放在第一个 BST 中，你就可以在任何时间点从一棵树跳到另一棵树。

Answer 2

一个解决方案是：

初始化 TreeSet<Node> result 按节点词频排序。
将树中的前 n 个元素添加到集合中。
遍历其余元素，用较高的值替换集合中的最低值。 if current > result.lowest() then result.pollFirst(); result.add(current)

这具有有限的空间成本并且应该更快，因为大多数元素可以直接跳过。

但是请注意，除非您处理的是巨大的数组并且已发现此函数的减速，否则您的解决方案的简单性使其成为更好的选择。

如何打印出二叉搜索树中第 n 个最频繁出现的词？

How to print out the nth most frequent words in a binary search tree?

java

algorithm

tree

binary-tree

binary-search-tree