Symbol Table - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

符号表（Symbol Tables）

详解

《常见算法与数据结构》符号表ST（1）——基本介绍 《常见算法与数据结构》符号表ST（2）——初等实现分析和有序符号表

要点

1. 注意符号表不像二叉树，无前驱predecessor后继successor查询
2. 符号表的搜索不是基于比较的
3. 只有search/insert/delete
4. 用AVL树实现符号表，查询的时间复杂度是O(logn)，插入的时间复杂度是O(logn)
5. 用符号表排序 O(n^2)
   1. 将每个值插入符号表 O(n)
   2. 搜索最小值 O(n)
   3. 重复：找后继successor，即下一个最小值

适用场景

单词拼写检查 Spelling correction (key=misspelled word, data=word) 编译器 Scheme interpreter (key=variable, data=value) 负载均衡 Web server (key=ip address, data=connection handler)

飞行员时间表 Pilot Scheduling

1. 检查在时间t安排是否可行 O(1)
2. 查找飞行员p的时间表
   • 非常适合符号表！
   • 插入新飞行员 O(1)
   • 可以搜索（和更新）现有飞行员 O(1)
   • 列出所有飞行员 O(n)

文档相似度 Document Distance

1. 阅读每个文档
   • 读取并解析文件
   • 将每个（单词，计数）放入HashMap中 (key=word, value=count在文档中出现的次数)