程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23484 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

12 | 树的深度优先搜索(下):如何才能高效率地查字典?

黄申 2019-01-09
你好,我是黄申。今天咱们继续聊前缀树。
上节结尾我给你留了道思考题:如何实现前缀树的构建和查询?如果你动手尝试之后,你会发现,这个案例的实现没有我们前面讲的那些排列组合这么直观。
这是因为,从数学的思想,到最终的编程实现,其实需要一个比较长的流程。我们首先需要把问题转化成数学中的模型,然后使用数据结构和算法来刻画数学模型,最终才能落实到编码。
而在前缀树中,我们需要同时涉及树的结构、树的动态构建和深度优先搜索,这个实现过程相对比较复杂。所以,这节我就给你仔细讲解一下,这个实现过程中需要注意的点。只要掌握这些点,你就能轻而易举实现深度优先搜索。

如何使用数据结构表达树?

首先,我想问你一个问题,什么样的数据结构可以表示树?
我们知道,计算机中最基本的数据结构是数组和链表。数组适合快速地随机访问。不过,数组并不适合稀疏的数列或者矩阵,而且数组中元素的插入和删除操作也比较低效。相对于数组,链表的随机访问的效率更低,但是它的优势是,不必事先规定数据的数量,表示稀疏的数列或矩阵时,可以更有效地利用存储空间,同时也利于数据的动态插入和删除。
我们再来看树的特点。树的结点及其之间的边,和链表中的结点和链接在本质上是一样的,因此,我们可以模仿链表的结构,用编程语言中的指针或对象引用来构建树。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(26)

  • Jsoulan
    感觉后面栈描述的过程像广度优先遍历呢

    作者回复: 栈是先进后出,还是深度优先。队列先进先出,适合广度优先

    2019-01-09
    8
  • pyhhou
    对于思考题:
         1. 图中结点之间的关系是 “邻居”, 树中结点之间的关系 “父子”,如果是无向图,“邻居” 之间是互通的,但是 “父子” 默认是单向关系,一般遍历从 “父” 到 “子”,子结点中一般不保留父结点的信息
         2. 图和树不一样的是,图会存在 “环” 的概念,就是回路,树中永远不可能有回路,否则就不是一棵树
    可以说链表是特殊的树,树是特殊的图。
    综上所述,对比树,在一般的图中做深度优先搜索的区别就是:我们需要记录我们之前访问过的结点,防止重复访问

    作者回复: 分析得很到位

    2019-03-12
    5
  • Wing·三金
    用 python 实现了 DFS 和字典树,比起 C++ 简直不要简单太多,感觉有点暴殄天物……

    ### 在 python 中定义一个结点类
    class Node:
        def __init__(self, alpha, pre, exp):
            self.alpha = alpha
            self.prefix = pre
            self.explanation = exp
            self.sons = dict()
        
        def find(self, alpha):
            if self.sons.get(alpha) == None:
                return False
            else:
                return True
            
        def create(self, alpha, son):
            self.sons[alpha] = son
            self.sons = {key: self.sons[key] for key in sorted(set(self.sons))}
            return True
        
        def get(self, alpha):
            return self.sons[alpha]

    class DictTree:
        def __init__(self, words, alpha=''):
            self.root = Node(alpha, '', '')
            self.build(words)
            
        def build(self, words):
            for word in words:
                self.add(word)
        
        def add(self, word):
            cur_node = self.root
            for i in word:
                i = i.lower()
                pre = cur_node.prefix + cur_node.alpha
                
                if not cur_node.find(i):
                    cur_node.create(i, Node(i, pre, ''))
                    
                cur_node = cur_node.get(i)
                
            cur_node.explanation = "This is a pyeudo explanation of '%s'" % word

        def DFS_search(self, word):
            word = word.lower()
            cur_node = self.root
            i = 0
            while True:
                if i == len(word):
                    if cur_node.explanation != '':
                        return cur_node.explanation
                    else:
                        return "The word '%s' is not in this dictionary." % word
                
                if cur_node.find(word[i]):
                    cur_node = cur_node.get(word[i])
                    i += 1
                    continue
                else:
                    return "The word '%s' is not in this dictionary." % word

    DFS 的实现可以用 list 代替 stack,在“压入”时可以用 reversed 函数直接逆序。

    作者回复: 是的 Python简洁很多

    2019-03-19
    3
  • Geek_zy
    老师遍历出所有的单词 是不是用explanation判断更合适,因为一个通路是可以有多个单词的。
    public static void dfsByStack(){
            Stack<TreeNode> stack = new Stack<>();
            stack.push(headNode);
            while(stack.size()>0){
                TreeNode node = stack.pop();
                if(!StringUtils.isEmpty(node.explanation)){
                    System.out.println(node.explanation);
                }
                Map<Character, TreeNode> sons = node.sons;
                sons.forEach((sonKey,sonValue)->{
                    stack.push(sonValue);
                });
            }
        }

    作者回复: 这也是可以的,适用于字典的应用场景👍

    2019-10-22
    1
  • Paul Shan
    这里深度优先遍历的顺序和前一篇文章中的不太一样,区别在于前一篇文章中的深度遍历,当发现一个新节点的时候入栈,然后马上处理这个新节点也就是栈顶,这篇文章中是把一个节点相连的所有节点入栈,然后再处理栈顶元素,请问老师,我的理解是否准确?

    作者回复: 是的,一个只要访问最深的某条路径,一个是需要遍历所有路径

    2019-08-23
    1
  • qinggeouye
    文中深度优先搜索代码,if else 分枝:
    if (node.sons.size() == 0){
    ...
    }else{
    ...
    }

    如果一个单词完全是另一个单词的前缀,打印出一个单词,另一个应该不会打印了,比如这种:
    word_dict = {'successful': '成功的', 'success': '成功'}

    作者回复: 很好的发现,如果是这样,就是说不一定非要叶子结点才是一个单词,需要把每个点再设置一个状态,表明这个结点是不是一个合法的单词。我稍后修改一下代码。

    2019-02-24
    1
  • Joe
    老师讲解的树有多个分支,这里用C++简单演示了下二叉树的DFS。
    /**
     * Objective:Given a b-tree, do the depth-first-search(DFS) or traversal.
     * Appraoch: stack, no recursion.
     * Example:
     * 1
     * / \
     * 2 3
     * / \ / \
     * 4 5 6 7
     * Output:
     * preorder: 1 2 4 5 3 6 7
     */

    #include <iostream>
    #include <stack>
    using namespace std;

    // tree node
    class TreeNode {
      public:
      int data;
      TreeNode* left = NULL;
      TreeNode* right = NULL;

      public:
      TreeNode(int data)
          : data(data) {
      }
    };
    // depth-first-search
    class DFS {
      public:
      void printDFS(TreeNode* root) {
        stack<TreeNode*> s;
        s.push(root);
        // begins!
        while (!s.empty()) {
          TreeNode* temp = s.top();
          s.pop();
          // push right first
          if (temp->right != NULL) {
            s.push(temp->right);
          }
          if (temp->left != NULL) {
            s.push(temp->left);
          }
          // print data
          cout << temp->data << " ";
        }
      }
    };
    // test!
    int main(void) {
      // build tree.
      TreeNode* root = new TreeNode(1);
      root->left = new TreeNode(2);
      root->right = new TreeNode(3);
      root->left->left = new TreeNode(4);
      root->left->right = new TreeNode(5);
      root->right->left = new TreeNode(6);
      root->right->right = new TreeNode(7);

      DFS test;
      cout << "Depth-First-Search: " << endl;
      test.printDFS(root);
    }
    输出:
    Depth-First-Search:
    1 2 4 5 3 6 7

    作者回复: 很好的实现,代码简洁

    2019-01-17
    1
  • mickey
    勘误:

    栈是先进后出。

    第3步将结点123、879、945和131压入栈中。

    第4步,重复第2步和第3步弹出和压入的步骤,处理结点123,.....

    123结点应该是最后处理的,应该先处理131.

    作者回复: 图里画的是对的,文字表达有歧义,我稍后改一下

    2019-01-10
    1
  • Being
    广度优先一般用队列来做,FIFO,这样做到层级遍历;深度优先则用栈来做,FILO,这样做到按深度一条条的遍历下去。在实现上是这么区别的,我看上面有同学混淆了。

    作者回复: 总结的很好

    2019-01-09
    1
  • 半湖思絮
    字典树查找Java
    public class Lesson12_1 {

        /**
         * @Description: 前缀树的结点
         */
        class TreeNode {

            public char label;
            public HashMap<Character, TreeNode> sons = null;
            public String prefix = null;
            public String explanation = null;

            // 初始化结点
            public TreeNode(char l, String pre, String exp) {
                label = l;
                prefix = pre;
                explanation = exp;
                sons = new HashMap<>();
            }

            private TreeNode build(String str, String exp, String pre, TreeNode root) {
                if ("".equals(str)) {
                    this.explanation = exp;
                    return root;
                }
                // 处理当前字符串的第一个字母
                char c = str.toCharArray()[0];
                TreeNode found = null;

                // 如果字母结点已经存在于当前父结点之下,找出它。否则就新生成一个
                if (this.sons.containsKey(c)) {
                    found = this.sons.get(c);
                } else {
                    TreeNode son = new TreeNode(c, pre, "");
                    this.sons.put(c, son);
                    found = son;
                }

                return found.build(str.substring(1), exp, pre + str.substring(0, 1), root);
            }

            public TreeNode build(String str, String exp) {
                return this.build(str, exp, "", this);
            }

            public String search(String str) {
                if ("".equals(str)) {
                    return null;
                }

                TreeNode found = this;
                char[] chars = str.toCharArray();
                for (char c : chars) {
                    if (!found.sons.containsKey(c)) {
                        return null;
                    } else {
                        found = found.sons.get(c);
                    }
                }

                return found.explanation;
            }
        }

        @Test
        public void test() {
            TreeNode treeNode = new TreeNode((char) 0, "", "");
            treeNode.build("hello", "你好").build("helloworld", "你好世界");
            System.out.println(treeNode.search("hello"));
        }
    }
    2019-12-12
  • teddytyy
    图的深度优先搜索需要标记访问过的节点
    2019-12-05
  • 一页遮目
    说到这里,你可能会好奇,为什么只有结点的定义,而没有边的定义呢?实际上,这里的有向边表达的是父子结点之间的关系,我把这种关系用 sons 变量来存储父结点。

    老师,这里是不是说错了,应该是 sons 变量来存储子结点。

    作者回复: 对

    2019-12-04
  • 于江水
    上一节迭代法会在一个结点判断选择一个分支继续下去,从这一节的栈的方法,看起来会遍历一些无用的分支,整体上看针对查找某个单词,迭代法性能会更高吗?

    作者回复: 递归或者栈主要是用于遍历,对于单个词的查找没有必要

    2019-11-16
  • Yang
    判断当前节点是否被访问过。
    2019-11-05
  • Geek_zy
    private static TreeNode headNode = new TreeNode('~',"im head node",null);
        public static void buildPrefixTree(String word){
            if(StringUtils.isEmpty(word)) {
                return;
            }

            TreeNode findNode = headNode;
            String prefix = "";
            String explanation = null;

            for(int i=0;i<word.length();i++){
                char c = word.charAt(i);
                Map<Character, TreeNode> sons = findNode.sons;
                if(sons.containsKey(c)){
                    findNode = sons.get(c);
                }else{
                    if(i == word.length()-1){
                        explanation = prefix + c;
                    }
                    TreeNode sonNode = new TreeNode(c,explanation,prefix);
                    sons.put(c,sonNode);
                    findNode = sonNode;
                }
                prefix += c;
            }
        }


        public static TreeNode findWrod(String word){

            if(StringUtils.isEmpty(word)) {
                return null;
            }
            TreeNode findNode = headNode;

            for(int i=0;i<word.length();i++){
                char c = word.charAt(i);
                Map<Character, TreeNode> sons = findNode.sons;

                if( sons.size()!=0 && sons.containsKey(c)){
                    findNode = sons.get(c);
                }else{
                    return null;
                }
            }

            if(StringUtils.isEmpty(findNode.explanation)){
                return null;
            }

            return findNode;
        }

        /**
         * 使用栈便利所有的单词
         */
        public static void dfsByStack(){
            Stack<TreeNode> stack = new Stack<>();
            stack.push(headNode);
            while(stack.size()>0){
                TreeNode node = stack.pop();
                if(!StringUtils.isEmpty(node.explanation)){
                    System.out.println(node.explanation);
                }
                Map<Character, TreeNode> sons = node.sons;
                sons.forEach((sonKey,sonValue)->{
                    stack.push(sonValue);
                });
            }
        }
    2019-10-22
  • Better me
    老师这章代码有相应的github地址吗,想看看递归实现

    作者回复: 暂时没有,以后有机会我整理一下

    2019-07-28
  • 不知道老师还会看留言不?
    explanation 这个词条解释,我有点疑惑 。这里的节点是单个字母,那如果有词条解释,比如boy, fly, 对于y这个单词,显然有很多可能组成单词解释

    作者回复: 应该是看到从根到这个结点为止所有前缀所组成的单词,explanation是针对这个词的

    2019-07-03
  • 漏网之鱼
    字典树数据结构的prefix变量在这里有什么用处呢,我们好像不需要往上查找父节点吧

    作者回复: 有的时候需要知道这个单词是哪个

    2019-06-24
  • 以前学数据结构,印象很深的是一点是:可以用二叉树来表示树,用二叉树的右孩子结点们来表示树的兄弟结点。
    字典树其实用二叉树来表示会更好:
    (1)不用在Node中去设置sons这样的变量,只要一个left和right就好,更节省空间
    (2)无论是创建操作,还是查找操作,全程都不需要递归或者手动操作栈,在右孩子链表中查找该对应字母就好,找到后,就用它的左孩子的右孩子链表去查找下一个字母,纯迭代操作,效率很高。

    作者回复: 这个想法很好👍,不过如果要遍历所有可能的单词,可能还是需要递归或者栈操作?

    2019-06-22
  • 史明春Larry
    一般图中需要考虑是否有循环,需要记录节点是否已经访问过

    作者回复: 是的

    2019-04-14
收起评论
26
返回
顶部