字典树(Trie )

温故知新:

• 树的定义
• 二叉树，前中序列遍历，层次遍历
• DFS和BFS
• 二叉搜索树(BFS)定义，左子树都小于根，右子树都大于根，中序遍历是有序序列

实际问题：搜索引擎中自动联想

定义: 多叉树，常用于搜索引擎的文本词频统计，用于最大新都减少不必要的字符串比较，查找效率高于哈希表

基本性质:

1. 节点本身不存完整单词
2. 从根节点到某一节点，路径上经过的字符链接起来，为该节点对应的字符串
3. 每个节点的所有子节点路径代表的字符串都不相同

注意，图中的to, ted, tea 并不实际存在，只是表示按照路径查找之后连接后的单词

字典树

核心思想:

• 空间换时间（树的每层至少存在26个分支）
• 利用字符串的公共前缀来降低查询时间的开销，以达到提高效率的目的

Trie模板

class Trie(object):
    
    def __init__(self): 
        self.root = {} 
        self.end_of_word = "#" 
        
    def insert(self, word): 
        node = self.root 
        for char in word: 
            node = node.setdefault(char, {}) 
        node[self.end_of_word] = self.end_of_word 

    def search(self, word): 
        node = self.root 
        for char in word: 
            if char not in node: 
                return False 
            node = node[char] 
        return self.end_of_word in node 

    def startsWith(self, prefix): 
        node = self.root 
        for char in prefix: 
            if char not in node: 
                return False 
            node = node[char] 
        return True

实现字典树: 看题解，临摹一种写法，不必要自己去创造（除非你想）.动态采用字典数据结构（哈希表）

单词搜索: 无论是1还是2，都很经典, 要学习计算时间复杂度（这是面试的最高难度）

并查集

直接套用模板即可，常用来解决组团和配对问题(Group or not?)

属于

基本操作

• makeSet(s): 新建一个新的并查集，包括s个元素集合
• unionSet(x,y): 合并元素x和元素y，要求x和y所在集合不相交，如果相交则不合并
• find(x): 找到元素x所在集合的代表，该操作也可以用来判断两个元素是否位于同一个集合，只要将他们各自的代表比较一下就可以

路径压缩

代码模板: Python

def init(p): 
    # for i = 0 .. n: p[i] = i; 
    p = [i for i in range(n)] 

def union(self, p, i, j): 
    p1 = self.parent(p, i) 
    p2 = self.parent(p, j) 
    p[p1] = p2 
    
def parent(self, p, i): 
    root = i 
    while p[root] != root: 
        root = p[root] 
    while p[i] != i: # 路径压缩 ?
        x = i; i = p[i]; p[x] = root 
    return root

struct DSU
{
    std::vector<int> data;
    
    void init(int n) { data.assign(n, -1); }
    
    bool unionSet(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x != y)
        {
            if (data[y] < data[x])
            {
                std::swap(x, y);
            }
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }

    bool same(int x, int y) { return root(x) == root(y); }

    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }

    int size(int x) { return -data[root(x)]; }
};

//https://leetcode-cn.com/problems/friend-circles/solution/547-by-ikaruga/

朋友圈：每个人都是一个人，然后根据好友关系矩阵，如果M[i][j]==1, 就合并，最后统计孤立的集合。

高级搜索

不要死磕，多过遍数（你不是一个人懵逼）

初级搜索改进

1. 不重复(斐波那契)、剪枝（括号生成）
2. 双向搜索，启发式搜索（优先级搜索）

剪枝

括号生成: 剪枝体现在右括号一定要小于左括号。而不是生成所有可能后，再去判断是否符合要求

思考题: DP如何解决括号生成的问题。

N皇后问题: 剪枝体现在，发现col, row diagonal只要存在皇后，立马放弃（剪枝），而不是先把所有可能都生成之后，才去判断当前布局是否符合要求。

数独问题: 剪枝体现在对行、列、块进行判断，用于判断是否合法，不符合就不再递归。更好的操作，预先扫描数组，记录每行、每列、每个方块的可填数组，记录哪些位置需要进行填写。

双向BFS

先默写BFS模板代码

def BFS(graph, start, end):
    visited = set()
    queue = []
    queue.append[start]
    while queue: #不为空
        # 处理
        node = queue.pop()
        visited.add(node)

        process(node)
        nodes = generate_related_nodes(node)
        queue.push(nodes)
    #other process work
    ... 

双向BFS就是从A和L分别往中间搜索，两个人在中间碰头

双向BFS

单词接龙（硅谷非常高频）

双向模板

def dBFS(graph, start, end):
    visited = set()
    front = []
    back = []
    front.append(start)
    back.append(end)
    while front and back:
        nodes = set()
        for node in front:
            visited.add(node) #加入访问
            process(node) # 处理当前node
            nodes.append(generate_related_nodes(node)) #获取子节点
        front = nodes
        # 从较小的set开始
        if len(back) < len(front):
            front, back = back, front
    ...
        

是否双向BFS一定要用set？

很多时候，双向BFS的队列底层数据结构会用set，特别是那种左边动一步，右边动一步，每次就把所有一层的节点处理完，生成新的一层的节点的情况，用set能更好的判断对面的节点是否也在当前的节点里有。

启发式搜索

不需要着急学习这一块，注意多过遍数（你不是一个人一脸懵逼的听完第一遍）

启发式搜索（Heuristic Search, A*）,Heuristic指的是根据某一些条件，我们不断的优化搜索方向，本质上用的就是利用优先级进行查找。

def AstarSearch(graph, start, end):

    pq = collections.priority_queue() # 优先级 —> 估价函数
    pq.append([start]) 
    visited.add(start)

    while pq: 
        node = pq.pop() # can we add more intelligence here ?
        visited.add(node)

        process(node) 
        nodes = generate_related_nodes(node) 
         unvisited = [node for node in nodes if node not in visited]
        pq.push(unvisited)

核心是在定义在估价函数, h(n)。

一些相似度度量方法：https://dataaspirant.com/2015/04/11/five-most-popular-similarity-measures-implementation-in-python/

二进制矩阵的最短路径， 估计函数，曼哈顿距离

滑动谜题: 经典题目是 8 puzzles

• DFS/BFS
• A*, 得分为坐标差

红黑树和AVL树

这个章节主要是了解性质，需要掌握红黑树和AVL树的异同，以及AVL树的四种旋转操作。

温故知新:

• 思考下树的结构和二叉树的结构
• 树的遍历，前中序遍历，DFS，BFS
• 二叉搜索树(BST), 查找，插入，删除（要求理解逻辑）

起因：二叉搜索树的极端情况，退换成链表

改进：平衡二叉树，包括2-3 树, AA 树,B+ Tree, 红黑树和AVL 树

这些数据结构面试的时候只需要理解原理，不需要书写

AVL树: 完全平衡二叉树

发明者是G. M. Adelson-Velsky和Evgenii Landis

• 平衡因子（记录左子树和右子树的高度差）
• 旋转操作（左旋，右旋，左右旋，右左旋）
• 不足: 节点需要存储额外信息，且调整次数频繁（维护成本高）

面试要点：平衡因子的由来，四种基本旋转操作，

右右子树，都在右边，左旋

左旋

左左子树，都在左边，右旋

右旋

左右子树，左右都有，左右旋

左右旋

右左子树，左右都有，右左旋

右左旋

思考题1：下面是什么树形，应该如何调整

思考题1

思考题2：下面是什么树形，应该如何调整

思考题2

红黑树: 近似平衡二叉树

面试要点：高度差2倍，红黑树的五点性质

保证任何一个节点的左右子树高度差小于两倍（例如，左边是5，右边可以是10，或者2.5 ）即

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

红黑树

面试关键知识点：

1. AVL树比红黑树查找速度快（因为完全平衡）
2. 红黑树比AVL树更快的插入和删除（因为近似平衡）
3. AVL存放平衡因子（或高度信息），要求的一个整型，而红黑树只需要一个1bit存放红黑信息
4. 红黑树应用于C++的map, multimap, multiset, 而AVL树用于数据库（对查询要求较高）