关于二分搜索树中圣经的例子

Question

不太明白为什么单词组成的vector可以进行二分查找。我的理解是想进行二分搜索，必须要有先把数据本身或者索引建立成树的结构？没看懂哪里做建立索引这件事了？

Answer 1

liuyubobobo 2017-05-25 01:18:10

在我们的测试用例中，（参见这个main函数 https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/04-Binary-Search-Tree-Search/main.cpp ）

我们创建了一个BST，之后将单词逐渐的放进BST，就是把我们的单词数据组织成二分搜索树的过程哦。在这个过程中，我们设置的每一个节点，key是一个string，表示那个单词；value是一个int，表示单词的频率。具体如下：

// 创建BST
BST<string, int> bst = BST<string, int>();

// 遍历vector中的所有单词   
for (vector<string>::iterator iter = words.begin(); iter != words.end(); iter++) {    
    // 查找单词在树中是否存在，如果存在，返回的*res中包含该单词的频率；否则，*res为NULL
    int *res = bst.search(*iter);     
    if (res == NULL)
        // 如果不存在，我们第一次看见这个单词，将这个单词插入到二分搜索树中，频率记做1    
        bst.insert(*iter, 1);      
    else    
        // 如果存在，我们又一次看见了这个单词，将单词的频率做加1操作
        (*res)++;    
}

• 提问者 马尔克ov #1

  谢谢老师。我的理解是这样的:树的结构取决于节点的value，因为这个原因才增加了搜索的效率。可是那个循环的函数里只有第一次见到这个单词才插入，那他的值只能是1。之后遇到重复的单词只是对value做++，可是树的结构如何变化呢？

• liuyubobobo 回复 提问者 马尔克ov #2

  树的结构取决于key，在这个例子里，key是单词。在这个例子例，树的结构变化靠的是：bst.insert(*iter, 1); 这句话。这里*iter是一个单词哦。

• 提问者 马尔克ov 回复 liuyubobobo #3

  原来如此！谢谢老师