学习笔记

字典树在搜索的时候经常会用到，可以用O(1)的复杂度找到查找的词组且补全高频查找结果，一般搜索引擎查询补全用的比较多。

字典树也是一种树，只是这个树和我们前面学的BFS和二叉堆不太一样，这个是颗N叉树，再者数据存储也不太一样，正常树的节点是存储完整的数据，而字典树每个节点其实只会存一个字符，当其到达尾部之后（一般条件是isEnd为true），将整个遍历路径连起来会组成一个字符串，这就是查询的结果。

字典树的缺点是空间占用会很大，是一种典型的空间换时间的思想。

并查集这块东西会比较死，记住模板然后认清使用场景，直接套上去用就行了，基本是定式操作，主要是牢记模板。

其使用场景主要是组团和配对问题。判断两个人是否是朋友，判断群组关系等。

并查集代码模板如下：

public class UnionFind {

    private int count = 0;
    private int[] parent;

    public UnionFind(int n) {
        count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }


    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;
        parent[rootP] = rootQ;
        count--;
    }

}

是严格的二叉平衡树，它的范围在{-1,0,1}之间，当某个节点不在这个范围之后，就需要进行相应的旋转进行平衡。

旋转主要有四种：

1. 左旋
2. 右旋
3. 左右旋
4. 右左旋

但是AVL有个很大的问题，节点需要存储额外信息，且需要频繁的去平衡，但是实际工程中存在一定程度的不平衡其实也是能接受的。

因此红黑树这种近似平衡二叉树就诞生了。

红黑树是一个近似平衡的二叉树，它不需要频繁的去触发平衡操作。它能确保任何一个几点左右子树的高度差小于两倍。

红黑树是满足一下条件的二叉搜索树：

• 每个结点要么是红色，要么是黑色
• 根结点是黑色
• 每个叶结点(NIL结点，空结点)是黑色的
• 不能有相邻接的两个红色节点
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色结点

因为计算机是用二进制而不是十进制存储，因此位运算会非常高效。

常见操作：

• 左移 <<
• 右移 >>
• 或运算 | 0011|1011=1011
• 与运算 & 0011&1011=0011
• 按位取反 ~ ~0011=1100
• 按位异或(相同为零不同为一) ^ 0011^1011

异或：相同为零，不同为一。也可用“不进位加法”来理解。

异或操作的一些特点：

x^0=x(当x不为0，结果就是x；当x为0，根据相同为零得出来的也是0，还是x)

x^1s=~x

x^(~x)=1s

x^x=0

c=a^b=>a^c=b,b^c=a //交换两个数

a^b^c=a^(b^c)=(a^b)^c

1. 将x最右边的n位清零：x&(~0<<n)
2. 获取x的第n位值(0或者1)：(x>>n)&1
3. 获取x的第n位幂值：x&(1<<n)
4. 仅将第n位置为1：x|(1<<n)
5. 仅将第n位置为0：x&(~(1<<n))
6. 将x最高位至第n位(含)清零：x&((1<<n)-1)

判断奇偶

x%2==1 -> x&1==1

x%2==0 -> x&1==0

x/2->x>>1

x=x&(x-1) 清零最低位1

x&-x=>得到最低位的1

x&~x=>0