字典树(Trie)，又称为单词查找树、键树，是一种树形式的数据结构，其特点是 将单词按照字母的顺序组织树的结构。

【优势】

可以最大限度地减少字符串的比较次数，提高查询效率。是从树的组织形式上对查找的优化。

【与树的不同】

根节点不存任何数据，每一个子节点存一个字母，从根出发，向下查找即可进行搜索。

【基本性质】

• 节点本身不存完整单词，而是单词中的某个字母。
• 从跟节点到某一节点，路径上经过的字符连起来就是单词。
• 每个节点的所有子节点路径代表了不同的字符。

【应用场景】

• 群组问题
• 朋友圈问题

【基本操作】

• makeSet(x)：创建一个新订单并查集，并且包含单个元素的集合

• unionSet(x, y)：把元素 x 和元素 y 所在的集合合并。

  注意：x 和 y 所在的几乎不想交

• find(x)：找到元素 x 所在的集合的代表，也可以用于判断两个元素是否位于同一个集合（各自的代表比较一下即可）

【存储结构实现】

可用数组表示，并且每个元就是集合代表。

使用元素值本身等于下标值，表示元素代表

【路径压缩】

相同代表的元素路径直接指向代表，缩短路径，提高查找效率

AVL 树是 特殊的二叉搜索树，是严格平衡的二叉树，要求每个元素的平衡因子在 -1, 0 , 1 之间。即左右子树深度差的绝对值不超过 1。

【优点】

查询效率较高，因为树的深度控制严格。

【缺点】

• 需要增加额外空间存储平衡因子
• 增加删除元素需要频繁进行调整，消耗性能

【AVL 树的旋转】

• 左旋：
• 右旋：
• 左右旋：
• 右左旋：

注意：旋转过程，仍然需要考虑排序树的性质，就可以知道有子树的节点在旋转时如何处理。

红黑树是非严格的 近似平衡 二叉搜索树，保证树的高度差不超过二倍即可。

【红黑树性质】

• 根节点是黑色的
• 每个节点要么是黑色，要么是红色
• 叶子节点（或 NIL 节点）是黑色的
• 不能有相邻的两个红色节点
• 从任何一个节点到每个叶子节点所有路径中，都包含相同数目的黑色节点。

【优点】

• 经常插入删除元素，比 AVL 树调整次数少，提高性能
• 存储颜色占用存储空间少

位运算是计算机底层硬件的实现，计算效率极高（移位速度比算术运算快）。

【常用运算】

• <<

• >>

• &

• |

• ！

• ^

【利用异或运算的常用操作】

• x ^ 0 = x：原理就是相同的 0 位仍然是 0, 1 位还是1，所以不变，由异或的性质所决定的
• x ^ x = 0：异或的性质，自己和自己每一位都相同，所以，最终结果为 0.
• x ^ 1s = ~x：使用全 1 操作，利用异或性质，把 x 的 1 位变成 0，0 位因为与 1 异或，所以不变。
• x ^ ~x = 1s：异或性质，直接可理解

【移位操作】

• 左移 n 位：相当于乘以 2^n
• 右移 n 位：表示除以 2^n

【其他差用位运算】

• x & (1s << n)：全 1 左移 n 位与 x 进行与运算，用补位的 0 清除 x 后 n 位。
• (x >> n) & 1：获取 x 的低 n 位的值，即判断 x 的第 n 位是 0 还是 1
• x & ((1 << n) - )：将 x 最高位到第 n 位清零。