二叉查找树(Binary search tree),也叫有序二叉树(Ordered binary tree),排序二叉树(Sorted binary tree)。是指一个空树或者具有下列性质的二叉树:
-
若任意节点的左子树不为空,则左子树上所有的节点值小于它的根节点值
-
若任意节点的右子树不为空,则右子树上所有节点的值均大于它的根节点的值
-
任意节点左右子树也为二叉查找树
-
没有键值相等的节点
typedef struct BiSearchTree{ ElemType key; struct BiSearchTree *lChild; struct BiSearchTree *rChild; }BiSearchTree; BiSearchTree *bisearch_tree_insert(BiSearchTree *tree,ElemType node); int bisearch_tree_delete(BiSearchTree **tree,ElemType node); int bisearch_tree_search(BiSearchTree *tree,ElemType node);
删除节点,需要重建排序树
- 删除节点是叶子节点(分支为0),结构不破坏
2)删除节点只有一个分支(分支为1),结构也不破坏
3)删除节点有2个分支,此时删除节点
思路一: 选左子树的最大节点,或右子树最小节点替换
int bisearch_tree_delete(BiSearchTree **tree,ElemType node){
if (NULL==tree) {
return -1;
}
// 查找删除目标节点
BiSearchTree *target=*tree,*parent=NULL;
while (NULL!=target) {
if (node<target->key) {
parent=target;
target=target->lChild;
}else if(node==target->key){
break;
}else{
parent=target;
target=target->rChild;
}
}
if (NULL==target) {
printf("树为空,或想要删除的节点不存在\n");
return -1;
}
//该节点为叶子节点,直接删除
if (!target->rChild && !target->lChild)
{
if (NULL==parent) {////只有一个节点的二叉查找树
*tree=NULL;
}else{
if (target->key>parent->key) {
parent->rChild=NULL;
}else{
parent->lChild=NULL;
}
}
free(target);//父节点处理,不然野指针,造成崩溃
}
else if(!target->rChild){ //右子树空则只需重接它的左子树,用左子树替换掉当前要删除的节点
BiSearchTree *del=target->lChild;
target->key = target->lChild->key;
target->lChild=target->lChild->lChild;
target->rChild=target->lChild->rChild;
free(del);
}
else if(!target->lChild){ //左子树空只需重接它的右子树
BiSearchTree *del=target->rChild;
target->key = target->rChild->key;
target->lChild=target->rChild->lChild;
target->rChild=target->rChild->rChild;
free(del);
}
else{ //左右子树均不空,p,t 2个指针一前以后,将左子树最大的节点(肯定是一个最右的节点)替换到删除的节点后,还需要处理左子树最大节点的左子树
BiSearchTree *p=target,*t=target->lChild;
while (t->rChild) {
p = t;
t=t->rChild;
}// 找到左子树最大的,是删除节点的直接“前驱”
target->key = t->key;
if (p!=target) {
p->rChild = t->lChild;
}else{
target->lChild = t->lChild;
}
free(t);
}
return 0;
}
是一种自平衡的二叉排序树。为什么需要这些自平衡的二叉排序树?
n个节点的完全二叉树,其查找,删除的复杂度都是O(logN),但是如果频繁的插入删除,导致二叉树退化成一个n个节点的单链表,也就是插入,查找复杂度趋于O(N),为了克服这个缺点,出现了很多二叉查找树的变形,如AVL树,红黑树,以及接下来介绍的 伸展树(splay tree)
这是一个经典的压缩算法。通过字符出现的频率
,优先级
,二叉树
进行的压缩算法。
对一个字符串,计算每个字符出现的次数,把这些字符放到优先队列(priority queue) 这这个priority queue转出二叉树
需要一个字符编码表来解码,通过二叉树建立huffman编码和解码的字典表
原始串: 二级制编码: huffman编码:
###存储结构和基本操作
struct node{ char *huffCode; // 叶子节点的huff编码 int weight; struct node *left,right; }
构建赫夫曼树
原则:出现频率越多的会在越上层,编码也越短,出现频率越少的在越下层,编码也越长。 不存在某一个编码是另一个编码的前缀,字符都在叶节点上,所以不会存在一个编码是另一个编码的前缀 二叉树每个节点要么是叶子节点,要么是双分支节点(且左分支编码为0,右分支编码为1)
压缩
- 扫描输入文件,统计各个字符出现的次数,对结构排序 (hash统计每个字符出现的次数)
- 根据排序结构,构建赫夫曼树 (贪心策略,每次选频率值最低的2个节点合并,需要优先队列帮组(priority queue,又叫最小堆))
- 对树进行遍历(左分支编码为0,右分支编码为1),得到各个字符的huffman编码,存到hash表中(这个就是编解码表,也可直接存储到节点中,如上面的char *huffCode)
- 重新对文件扫描,根据hash表进行压缩
压缩的文件为了能够解压缩,需要一个文件头,用来重建赫夫曼树,包括:
被编码的文本长度 unsigned int size
字符频率表 unsigned char freqs[NUM_CHARS]
解压缩
- 读取文件头
- 遍历编码后的bits,从赫夫曼树的根节点出发,遇到0,进入左子树,遇到1进入右子树,直到叶节点
字典树,英文名Trie树,Trie一词来自retrieve,发音为/tri:/ “tree”,也有人读为/traɪ/ “try”, 又称单词查找树,Trie树,是一种树形结构(多叉树)。
trie,又称为前缀树或字典树,是一种有序树,用于保存关联数组。
- 除根节点不包含字符,每个节点都包含一个字符
- 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串
- 每个节点的所有子节点包含的字符都不相同(保证每个节点对应的字符串都不一样)
最简单实现 ---- 26个字母表 a-z (没有考虑数字,大小写,其他字符)
子树用数组存储,浪费空间;如果系统中存在大量字符串,且这些字符串基本没有公共前缀,trie树将消耗大量内存
如果用链表存储,查询时需要遍历链表,查询效率有所降低
define ALPHABET_NUM 26
typedef struct Node{
char value;
struct Node *subTries[ALPHABET];
}*Trie
int Trie_insert(Trie *trie,char *word); // 插入一个单词
int Trie_search(Trie *trie,char *word);// 查找一个单词
int Trie_delete(Trie *trie,char *word);// 删除一个单词
trie树的增加和删除都比较麻烦,但索引本身就是写少读多,是否考虑添加删除的复杂度上升,依靠具体场景决定
DATrie libdatrie 双数组可以减少内存的使用量
double-array trie 参考作者的这篇论文 http://linux.thai.net/~thep/datrie/datrie.html
它的优点是:
节省空间:利用字符串的公共前缀来节约存储空间
最大限度地减少无谓的字符串比较
中文支持
查询效率比hash table 更优??
典型应用是:前缀查询 , 字符串查询,排序
用于统计,排序和保存大量的字符串(但不仅限于字符串)
经常被搜索引擎系统用于文本词频统计
排序大量字符串
用于索引结构
敏感词过滤
实际应用问题:
给你100000个长度不超过10的单词。对于每一个单词,我们要判断他出没出现过,如果出现了,求第一次出现在第几个位置
分析:
思路一:trie树 ,找到这个字符串查询操作就可以了,如何知道出现的第一个位置呢?我们可以在trie树中加一个字段来记录当前字符串第一次出现的位置。
已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串 分析:
给出N 个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。
分析:trie树查询单词的应用。先建立N个熟词的前缀树,然后按文章的单词一次查询。
给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本,文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如,若rob是不良单词,那么文本problem含有不良单词。
分析:先用不良单词建立trie树,然后过滤文本(每个单词都在trie树上查询,查询的复杂度O(1),效率非常高),这正是敏感词过滤系统(或垃圾评论系统)
的原理。
给你N 个互不相同的仅由一个单词构成的英文名,让你将它们按字典序从小到大排序输出 分析:这是trie树排序的典型应用,建立N个单词的trie树,然后线序遍历整个树,就可以达到效果。
###后缀树的应用
可以解决很多字符串的问题
- 查找字符串S1是否在字符串S中
- 指定字符串S1在字符串S中出现的次数
- 字符串S中的最长重复子串
- 2个字符串的最长公共部分