学习笔记 1.字典树 字典树， Trie树，又称单词直接查找数或键树，是一种树形结构，典型要应用是用于统计或排序大量的字符串(但不限于字符串)，所以京城被搜索引擎系统用于文本词频统计 优点： 最大限度地减少无畏的字符串比较，查询效率比哈希表高 基本性质： 1.节点本身不存在完成单词 2.从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串 3.每个节点的所存子节点路径代表的字符都不相同 核心思想 1.Trie tree的核心思想是空间换时间 2.利用字符串的公共前缀来降低查询时间的开销以达到提供效率的目的

2.高级搜索 一、并查集 适用情景： 1.组团、配对问题 2.Group or not

基本操作 makeSet(S):建立一个新的并查集，其中包含S个单元素集合 unionSet(x,y):把元素X和元素Y所在的集合合并，要求X、Y所在的集合不相交，如果相交则不合并 find(x):找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一集合，只要将他们的代表比较一下就可以

红黑树和AVL AVL 平衡因子：它的子子树的高度减去它的右子树的高度(有时相反) 不大于绝对值1 平衡因子的由来：查询的时间复杂度等于树的深度 通过旋转操作进行平衡(四种) 1.左旋 2.右旋 3.左右旋 4.右左旋

AVL总结： 1、AVL是一个平衡二叉搜索树 2、每个节点存平衡因子{-1,0,1} 3、四种旋转操作 AVL不足：节点需要存储额外的信息，且调整次数频繁

红黑树 1.红黑树是一种近似平衡的二叉搜索树，它能够确保任何一个节点的左右子树的高度差小于2倍，具体来说，红黑树是满足如下条件的二叉搜索树： 1、每个节点，要么红色，要么黑色 2、根节点是黑色 3、每个叶节点（NIL节点、空节点）是黑色 4、不能有相邻的两个红色节点 5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点 关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长

AVL与红黑树对比 1、AVL查询效率比红黑树快 2、红黑树的插入删除操作比AVL快（旋转少） 3、读操作多，写操作少，使用AVL 4、插入和删除操作多，使用红黑树