File tree Expand file tree Collapse file tree
Expand file tree Collapse file tree Original file line number Diff line number Diff line change 1- 学习笔记
1+ ![ image-20200724101337721] ( C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200724101337721.png )
2+
3+ #### Trie树理论
4+
5+ ![ image-20200724101620805] ( C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200724101620805.png )
6+
7+ ![ image-20200724101740662] ( C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200724101740662.png )
8+
9+ ![ image-20200724101959980] ( C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200724101959980.png )
10+
11+ ![ image-20200724102059615] ( C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200724102059615.png )
12+
13+
14+
15+ Trie 树优于哈希表的另一个理由是，随着哈希表大小增加，会出现大量的冲突，时间复杂度可能增加到 O(n)，其中 n是插入的键的数量。与哈希表相比，Trie 树在存储多个具有相同前缀的键时可以使用较少的空间。此时 Trie 树只需要 O(m)的时间复杂度，其中 m 为键长。而在平衡树中查找键值需要 O(mlogn) 时间复杂度。
16+
17+ 应用：
18+
19+ 1 . 自动补全，eg: 谷歌的搜索建议
20+
21+ 2 . 拼写检查, eg: 文字处理软件中的拼写检查
22+
23+ 3 . IP 路由 (最长前缀匹配), eg: 使用Trie树的最长前缀匹配算法，Internet 协议（IP）路由中利用转发表选择路径。
24+
25+ 4 . T9 (九宫格) 打字预测, eg: T9（九宫格输入），在 20 世纪 90 年代常用于手机输入
26+
27+ 5 . 单词游戏, eg: Trie 树可通过剪枝搜索空间
28+
29+
30+
31+ ![ image-20200725101845954] ( C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200725101845954.png )
32+
33+
34+
35+ #### 并查集
36+
37+ ![ image-20200726190851020] ( C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200726190851020.png )
38+
39+ ![ image-20200725101230990] (C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200725101230990.png<img src =" C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200725101211828.png " style =" zoom 33% ;" />
40+
41+
42+
43+ ![ image-20200725103138542] ( C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200725103138542.png )
44+
45+
46+
47+
48+
49+ ![ image-20200725104510761] ( C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200725104510761.png )
50+
51+
52+
53+
54+
55+ AVL 和红黑树
56+
57+ ![ image-20200726201312875] ( C:\Users\RL\AppData\Roaming\Typora\typora-user-images\image-20200726201312875.png )
58+
59+ 四种旋转，和为什么引入旋转
You can’t perform that action at this time.
0 commit comments