c++ - 如何找到启动二叉搜索树的好点

Question

我有一个包含大量单词的文本文件，超过 20K，但是它们都是按字母顺序排列的，现在假设你得到一个随机文件，你不知道它有多大，你如何找到一个好的开始点做一棵平衡良好的树？注意:我在 C++ 中执行此操作。谢谢你的任何建议!我目前正在这样阅读它们:

template <typename T>
int BST<T>::loadFromFile(string filename)
{
    int count = 0;
    string tempdata;
    ifstream fin(filename);
    if(!fin)
{
    cout<< "Error: Could no open file\n";
    count--;
}
while(fin)
{
    fin>>tempdata;
    if(fin)
    {
        insertEntry(tempdata);
        cout<<"Word: "<<tempdata<<" Count:"<<count<<endl;
        count++;

    }
}
fin.close();
return count;
}//end of loadFromFile() function

^间距错误，我永远无法将我的代码正确复制到问题中:P

编辑:如果我的插入方法单词正确，我相信在它读取按字母顺序排序的文件后它应该是这样的\行，因为每个单词都比下一个大。

Answer 1

all how would you find a good starting point to make a well balanced tree?

将文件读入元素 vector v

排序 vector v;

a) 从中间加载单个树元素 = (size/2)

b) 从左半部分递归加载 (v[0] .. v[middle]-1),

c) 从右半部分递归加载 (v[middle + 1] .. v[size()]

删除 vector

---

2014-08-02 更新。

我想我会提供一些关于将排序后的 vector 内容以“良好”顺序传输到二叉树的“递归”性质的见解..一个非随机顺序应该使(简单二叉)树在完全的。

最坏的情况下插入可能会让您进行 O(n) 搜索。

平衡(简单)二叉树的复杂度为 O(log n)。

     static void buildTree(std::vector< std::string >& v)
        { 
           // validation code ... 

           // create 1st node of tree 
           treeStart = new(TreeNode);
           assert(treeStart);

           // announce
           std::cout << "buildTree(std::vector& v)\n" << std::endl;

           // recurse through vector, invoking insertR() for each element
           buildTreeR(v,
                      0,             // smallest index
                      (v.size()-1)); // biggest index

        }


     // recurse through the vector to determine which element to insert
     static void buildTreeR(std::vector< std::string >& v,
                            size_t si,  size_t bi) // small indx, big indx
        {
           // validation code
           do
           {
              size_t di = bi - si;  // delta index 

              switch (di)
              {

              case 0: // 1 elment
              {
                 treeStart->insertR(v[si]);
              }
              break; 

              case 1: // 2 consecutive elements - i.e. 7-6 = 1,  6 7
              {
                 treeStart->insertR(v[si]);  // left
                 treeStart->insertR(v[bi]);  // right
              }
              break;

              case 2: // 3 consecutive elements - i.e. 3-1 = 2,  1 2 3 
              {
                 size_t m = si + 1;
                 treeStart->insertR(v[m]);   // insert middle

                 treeStart->insertR(v[si]);  // insert left 

                 treeStart->insertR(v[bi]);  // insert right 
              }
              break;               

              default: // 4 or more elements - i.e. 32767-0 = 32767, 
              {
                 size_t delta = (bi - si) / 2;

                 size_t m = si + delta;  // the middle of this range

                 treeStart->insertR(v[m]); // insert middle element 

                 buildTreeR (v, si, m-1);  // recurse on left  
                                           // smallest index thru (middle-1)

                 buildTreeR (v, m+1, bi);  // recurse on right 
                                           // (middle+1) thru biggest index
              }
              break;

              }// switch   

           }while(0);

        } // void buildR(std::vector< std::string >& v, size_t si, size_t bi)

---

仅供引用 - 在我 7 岁的戴尔电脑上，g++ v4.8.1，ubuntu 12.04，

32,767 个项目和 152,729 字节(每个字符串约 5 个字节)的性能。

  buildTree from vec: 
            duration: 132,013 us
         total bytes: 152,729

此外，此 vector 的类型是使用

调用的

 std::stable_sort(v.begin(), v.end());
 // this resulted in a lexicographic sort, probably what you want



 vector    after sort: 
        sort duration: 25,273 us
          total bytes: 152,729
       sizeof(vector): 12
        vector.size(): 32767

存在更复杂的替代方案 - AVL 树、红黑树等。另一方面，有了这些，您可能可以放弃 vector 和排序。

(使用的性能结果-O0)