type
status
date
slug
summary
tags
category
icon
password
Property
目录
红黑树，是一种平衡二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。
AVL树和红黑树：
- AVL树：严格平衡（左右子树高度差不超过1），所以AVL树的查找、插入、删除效率高： ，但插入和删除节点后，要维持树的平衡状态，做的旋转处理还是很多的
- 红黑树：近似平衡（控制最长路径不超过最短路径的2倍），变了一种方式来控制树的平衡，相较于AVL树，没有那么严格
红黑树更多是一种折中的选择，它舍弃平衡二叉树的严格平衡，换取节点插入时尽可能少的调整。
type
status
date
slug
summary
tags
category
icon
password
Property
倒排索引常使用在搜索引擎当中，是搜索引擎为文档内容建立索引，实现内容快速检索必不可少的数据结构。。
倒排索引的存储：内存索引和B+树索引。
正排索引
假设目前有两个 HTML 页面，一个页面内容是 "I like search engines."，而另一个页面内容是 "I search keywords in google."，现在将其按照单词进行划分，形成下表所示的结构：
ㅤ | I | like | search | engine | keywords | in | google |
P1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
P2 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
其中，每一行表示一个页面，每一列表示一个单词，0 表示该单词未出现在该页面中，而 1 则表示该单词出现在该页面中。那么当我们搜索含有关键词 "engine" 的页面时，我们需要遍历上表的每一行，这就是正排索引。
其定义如下：当用户发起查询时（假设查询为一个关键词），搜索引擎会扫描索引库中的所有文档，找出所有包含关键词的文档，这样依次从文档中去查找是否含有关键词的方法叫做正排索引。
type
status
date
slug
summary
tags
category
icon
password
Property
目录
线段树（Segment Tree）：一种基于分治思想的二叉树，用于在区间上进行信息统计。它的每一个节点都对应一个区间
[left, right] ，left、right 通常是整数。每一个叶子节点表示了一个单位区间（长度为 1），叶子节点对应区间上 left == right。每一个非叶子节点 [left, right] 的左子节点表示的区间都为 [left, (left + right) / 2]，右子节点表示的的区间都为 [(left + right) / 2 + 1, right]。线段树是一棵平衡二叉树，树上的每个节点维护一个区间。根节点维护的是整个区间，每个节点维护的是父亲节点的区间二等分之后的其中一个子区间。当有个元素时，对区间的操作（单点更新、区间更新、区间查询等）可以在 的时间复杂度内完成。
一棵区间为
[0, 7] 的线段树：
线段树的特点：
type
status
date
slug
summary
tags
category
icon
password
Property
字典树（Trie）：又称为前缀树、单词查找树，是一种树形结构。顾名思义，就是一个像字典一样的树。它是字典的一种存储方式。字典中的每个单词在字典树中表现为一条从根节点出发的路径，路径相连的边上的字母连起来就形成对应的字符串。
例如下图就是一棵字典树，其中包含有
a、abc、acb、acc、ach、b、chb 这 7 个单词：
这棵字典树用边来表示字母，从根节点到树上某一节点的路径就代表了一个单词。比如 1 → 2 → 6 → 10 表示的就是单词
acc。为了清楚地标记单词，可以在每个单词的结束节点位置增加一个 end 标记（图中红色节点），表示从根节点到这里有一个单词。字典树的结构比较简单，其本质上就是一个用于字符串快速检索的多叉树，树上每个节点都包含多字符指针。将从根节点到某一节点路径上经过的字符连接起来，就是该节点对应的字符串。
字典树设计的核心思想：利用空间换时间，利用字符串的公共前缀来降低查询时间的开销，最大限度的减少无谓的字符串比较，以达到提高效率的目的。
字典树的基本性质：
- 根节点不包含字符，除根节点外，每个节点都只包含一个字符
- 从根节点到某一节点，路径航经过的字符串连接起来，就是该节点对应的字符串
type
status
date
slug
summary
tags
category
icon
password
Property
哈夫曼树是一种最基本的压缩编码方法。对于如图所示的两棵二叉树，每个叶子节点都带有权值:
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度。例如，树 a 中根节点到结点 D 的路径长度为 4，树 b 中根节点到结点 D 的路径长度为 2。树的路径长度就是从树根到每一结点的路径长度之和。因此，树 a 的路径长度就为 20，树 b 的路径长度为 16。
如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。
例如，树a的，树b的。
其中，【带权路径长度(WPL)】最小的二叉树称作【哈夫曼树】，也称作最优二叉树。
将树 a 转化为哈夫曼树的步骤如下：
- 首先把带有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即：A5，E10，B15，D30，C40。
- 然后取头两个最小权值的结点作为一个新结点 N1 的两个孩子结点，注意相对较小的是左孩子，这里 A 是 N1 的左孩子，E 为 N1 的右孩子。则新节点的权值为两个叶子结点的权值的和，即 5+10=15。
- 然后将 N1 替换 A 与 E，插入有序序列中，保持从小到大的顺序排列。即 N115，B15，D30，C40。
type
status
date
slug
summary
tags
category
icon
password
Property
目录
根据应用场景的不同，STL实现了两种不同结构的关联式容器：树型结构和哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树（红黑树）作为其底层结构，容器中的元素是一个有序的序列。
pair类模板
关联式容器存储的是“键值对”形式的数据，例如：
<“penny”,“leonard”>。这个键值对第一个元素作为键（key），第二个元素作为值（value）。考虑到 “键值对” 并不是普通类型的数据，C++ STL标准库提供了
pair类模板 ，其专门用来将2个普通元素first和second创建成一个新元素<first, second>。pair类模板定义在#include<utility>头文件中： type
status
date
slug
summary
tags
category
icon
password
Property
目录
哈希表（Hash Table）：也叫做散列表。是根据关键码值（Key Value）直接进行访问的数据结构。
哈希表通过「键
key 」和「映射函数 Hash(key) 」计算出对应的「值 value」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数）」，存放记录的数组叫做「哈希表（散列表）」。哈希表的关键思想是使用哈希函数，将键
key 映射到对应表的某个区块中。可以将算法思想分为两个部分：- 向哈希表中插入一个关键码值：哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中。
- 在哈希表中搜索一个关键码值：使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值。
type
status
date
slug
summary
tags
category
icon
password
Property
Brute Force 算法
Brute Force 算法：简称为 BF 算法，暴力匹配算法，也可以叫做朴素匹配算法。
BF 算法思想：对于给定文本串
T 与模式串 p，从文本串的第一个字符开始与模式串 p 的第一个字符进行比较，如果相等，则继续逐个比较后续字符，否则从文本串 T 的第二个字符起重新和模式串 p 进行比较。依次类推，直到模式串 p 中每个字符依次与文本串 T 的一个连续子串相等，则模式匹配成功。否则模式匹配失败。
BF 算法的效率很低。最坏情况是每一趟比较都在模式串的最后遇到了字符不匹配的情况，每轮比较需要进行
m次字符对比，总共需要进行n-m+1轮比较，总的比较次数为m*(n-m+1) 。所以BF算法的最坏时间复杂度为在最理想的情况下（第一次匹配直接匹配成功），BF 算法的最佳时间复杂度是
在一般情况下，根据等概率原则，平均搜索次数为，所以 Brute Force 算法的平均时间复杂度为