二叉堆

基于堆的排序方式。

  • 结构：它是一个完全二叉树，通常用数组来表示。
    • 对于数组中下标为 i 的节点：
      • 其父节点的下标是 (i-1)/2（向下取整）。
      • 其左子节点的下标是 2*i + 1。
      • 其右子节点的下标是 2*i + 2。
  • 性质：
    • 最大堆：每个节点的值都大于或等于其子节点的值。堆顶是最大值。
    • 最小堆：每个节点的值都小于或等于其子节点的值。堆顶是最小值。

堆化

对于一个节点，如果它不满足堆的性质（比如它的值小于其某个子节点），就将其 “下沉” ，直到它大于其子节点，或到达叶子节点。

  • 过程：
    1. 在当前节点、其左子节点、其右子节点中，找出值最大的节点。
    2. 如果最大节点不是当前节点，则交换当前节点和这个最大节点。
    3. 递归或迭代地对被交换下去的那个子节点位置继续执行堆化操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void heapify(vector<int> &arr, int n, int i){
    // n: size of heap
    // i: index of root
    // 最大堆
    int largest_index = i;    // 假设根节点最大
    int left_index = 2*i + 1;
    int right_index = 2*i + 2;
    // 第一步：在左右节点中找最大节点
    if(left_index < n && arr[left_index] > arr[largest_index]){
        // 左比根大，左做根，再递归处理
        largest_index = left_index;
    }
    if(right_index < n && arr[right_index] > arr[largest_index]){
        // 右比根大，右做根，再递归处理
        largest_index = right_index;
    }
    // 第二步：下沉
    if(largest_index != i){
        // 根节点不是最大的，那就跟最大的交换
        swap(arr[i], arr[largest_index]);
        heapify(arr, n, largest_index);
    }
}

建堆

需要对半数节点堆化。

1
2
3
for(int i = n/2-1; i >= 0; --i){
    heapify(arr, n, i);
}

二叉查找树 (BST)

一个类似二分查找的结构。核心是左<中<右。

注意：左边所有节点都小于root，右边所有节点都大于root。

构建

由一个数组建立一个二叉搜索树，首先要注意的是根节点也有数值。二叉树的定义仍遵循LeetCode的经典定义

1
2
3
4
5
6
7
8
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

并定义一个数组 arr 。

选出一个数，插入树中，那么它有3种情况：成为根节点、插入左子树、插入右子树。这就得到了一个递推关系，以此实现二叉树的构建/插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void insert(TreeNode *root, int val){
    if(!root){
        root = new TreeNode(val);
        return;
    }
    if(val < root->val){
        // 小的数要到左边去
        if(root->left){
            // 左子树存在，那就在左子树找
            insert(root->left, val);
        }else{
            // 左子树不存在，变成叶子
            root->left = new TreeNode(val);
        }
    }else{
        // 往右同理
        if(root->right){
            insert(root->right, val);
        }else{
            root->right = new TreeNode(val);
        }
    }
}

或者更好的函数式解法：

1
2
3
4
5
6
7
8
9
10
11
TreeNode* insert(TreeNode *root, int val) {
    if (!root) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

查找

理解3个状态即可：找到，在左边找，在右边找。

1
2
3
4
5
6
TreeNode *query(TreeNode *root, int key){
    if(!root || root->val == key){
        return root;
    }
    return (root->val < key) ? query(root->right, key) : query(root->left, key);
}

删除

删除操作需要仔细理解。对于叶子节点直接变空即可，但接下来需要考虑存在子树、存在父节点的情况。

特别考虑左右子树都存在的情况，假如此时 del 函数已经执行到将被删除的节点，那么：

  1. 将当前节点的值改为右子树中的最小值
  2. 删除右子树中的那个节点
  3. 左子树保持不变

特别注意删除节点需要的 delete 操作，否则节点内存仍存在。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
TreeNode* del(TreeNode *root, int val){
    if(!root){
        return nullptr;
    }
    if(val < root->val){
        root->left = del(root->left, val);
        delete 
    }else if(val > root->val){
        root->right = del(root->right, val);
    }else{
        // 找到
        if(!root->left){
            // 只有右子树，那就直接返回右子树
            TreeNode *tmp = root->left;   // 关键：防止内存问题
            delete root;
            return tmp;
        }else if(!root->right){
            // 左边同理
            TreeNode *tmp = root->right;
            delete root;
            return tmp;
        }else{
            // 如果左右都存在，那就找到右子树最小值，也就是右的最左
            TreeNode *succ = root->right;
            while(succ->left){
                succ = succ->left;
            }
            root->val = succ->val;
            root->right = del(root->right, succ->val);    // 右边变成删除了后继节点的树
        }
    }
    return root;
}

平衡二叉树 (AVL)

上述的BST存在一个极端情况：一条链，这可能由于数组读取顺序所导致。

平衡查找树确保子树尽量平均。

性质

  • 左子树和右子树深度之差的绝对值不大于1
  • 左子树和右子树也都是平衡二叉树
  • 平衡因子(Balance Factor) ：二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子

判定

直接翻译条件得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
int height(TreeNode *root){
    if(!root){
        return 0;
    }
    return max(height(root->left), height(root->right)) + 1;
}

bool isBalanced(TreeNode *root){
    if(!root){
        return true;
    }
    return isBalanced(root->left) && isBalanced(root->right) && abs(height(root->left) - height(root->right)) <= 1;
}

BST 平衡化

四种不平衡情况（假设节点 A 是最低不平衡节点）：

  1. LL 型：A 的左子树的左子树插入导致
  2. RR 型：A 的右子树的右子树插入导致
  3. LR 型：A 的左子树的右子树插入导致
  4. RL 型：A 的右子树的左子树插入导致

判断四种情况，可使用balance factor。

LL型 ：左子树的左子树插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeNode *right_rotate(TreeNode *root){
    // LL 型右旋
    // root 是待旋转的根节点
    TreeNode *left_child = root->left;   // 要变成根节点
    
    // 旋转
    root->left = left_child->right;
    left_child->right = root;
    
    // 改变高度
    left_child->h = max(height(left_child->left), height(left_child->right)) + 1;
    root->h = max(height(root->left), height(root->right)) + 1;

    return left_child;
}

RR型：右子树的右子树插入

1
2
3
4
5
6
7
8
9
10
11
TreeNode *left_rotate(TreeNode *root){
    // RR 型左旋
    // 与right rotate 镜像
    TreeNode *right_child = root->right;
    root->right = right_child->left;
    right_child->left = root;
    right_child->h = max(height(right_child->left), height(right_child->right)) + 1;
    root->h = max(height(root->left), height(root->right)) + 1;

    return right_child;
}

LR型： 左子树的右子树插入

1
2
3
4
5
6
7
TreeNode *left_right_rotate(TreeNode *root){
    // LR  
    // 左子树逆时针 (left rotate)
    root->left = left_rotate(root->left);
    // 根节点顺时针 (right rotate)
    return right_rotate(root);
}

RL型：右子树的左子树插入

1
2
3
4
5
TreeNode *right_left_rotate(TreeNode *root){
    // RL, 镜像
    root->right = right_rotate(root->right);
    return left_rotate(root);
}

实现插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
TreeNode *insert(TreeNode *root, int key){
    // AVL 构建
    if(!root){
        return new TreeNode(key);
    }
    if(key < root->val){
        root->left = insert(root->left, key); 
    }else
    if(key > root->val){
        root->right = insert(root->right, key);
    }else{
        return root;
    }
    // 执行到这里说明执行过插入步骤了，因此需要旋转
    root->h = max(height(root->left), height(root->right)) + 1;
    int balance_factor = height(root->left) - height(root->right);

    if(balance_factor > 1 && key < root->left->val){
        // 左子树高，并且将要插入左边，就是LL的情况。
        // 不必考虑root->left是否为空，因为balance_factor已经考虑了
        return right_rotate(root);
    }
    if(balance_factor < -1 && key > root->right->val){
        // RR
        return left_rotate(root);
    }
    if(balance_factor > 1 && key > root->left->val){
        // LR
        return left_right_rotate(root);
    }
    if(balance_factor < -1 && key < root->right->val){
        return right_left_rotate(root);
    }
    return root;
}

多路平衡查找树 (B-树)

主要用于文件系统中，在B-树中，每个结点的大小为一个磁盘页，结点中所包含的关键字及其孩子的数目取决于页的大小。

性质

m 阶 B-树 满足：

(1) 每个结点最多有 m 棵子树（即最多 m-1 个关键字）。
(2) 根结点如果不是叶子，则至少有 2 棵子树（即至少 1 个关键字）。
(3) 非根非叶结点至少有 ⌈m/2⌉ 棵子树，即至少 ⌈m/2⌉ - 1 个关键字。
(4) 结点的结构：

1
(n, A₀, K₁, A₁, K₂, A₂, …, Kₙ, Aₙ)

其中：

  • K₁ < K₂ < … < Kₙ
  • A₀ 指向关键字都小于 K₁ 的子树
  • Aᵢ 指向关键字介于 Kᵢ 与 Kᵢ₊₁ 之间的子树
  • Aₙ 指向关键字大于 Kₙ 的子树
  • ⌈m/2⌉ - 1 ≤ n ≤ m - 1

(5) 所有叶子结点在同一层，不含信息（B-树中叶子不含关键字，只作为查找失败的出口，实际存储时可能存放指向实际数据的指针或为空）。

称节点的值是关键字。

定义

红黑树

待补充

线段树

常用的区间查询与更新数据结构，尤其适合处理区间最值、区间和、区间覆盖、区间修改等动态问题。

结构

  • 数组存储，大小为原数组4倍
  • 节点表示区间和

Huffman 树

用于数据压缩的数据结构。

编码过程

考虑一个字符串 s ，统计每个字符的词频，根据词频建立二叉树，得到 Huffman 编码。

贪心 ： 使词频最高 的元素，编码最短，也就是使词频低的元素编码尽可能长。

路径 ： Huffman 树产生 Huffman 编码，而编码依赖路径。定义 左节点出发，表示0；右节点出发，表示1 ，记录经过的路径，并将路径以 比特流 存储。

建树过程 ： 根据以上论述可知，频次低的元素在树底，频次越高越靠近树根。

编码实现

  1. 利用 map 存储字符-频次对。
  2. 利用 pq 创建树节点 并自动排序：让频次低的在堆顶
  3. 每次取两个Node， 连上parent，parent的频次等于二者之和，再将parent push至pq 。
  4. 重复。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct TreeNode {
    char ch;
    int freq;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : ch(0), freq(0), left(nullptr), right(nullptr){};
    TreeNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    TreeNode(char c, int f, TreeNode *left, TreeNode *right) : ch(c), freq(f), left(left), right(right) {}
    bool operator>(const TreeNode &other) const {
        return freq > other.freq;
    }
};

string s;     
map<char, int> map;     // 字符，频次
map<char, string>  hCode;    // Huffman 编码 Hash table
priority_queue<TreeNode*, vector<TreeNode*>, greater<TreeNode*>> pq;      // 确保频次最低节点在堆顶的pq

for(char c : s){
    freq[c]++;
}
for(auto it : freq){
    pq.push(new TreeNode(it.first, it.second));     // Node(char, freq)
}

// 建树
while(pq.size() > 1){
    auto left = pq.top();
    pq.pop();
    auto right = pq.top();
    pq.pop();
    auto parent = new TreeNode(0, left->freq + right->freq, left, right);
    pq.push(parent);
}
auto root = pq.top();
pq.pop();

// dfs编码：获取字符的二进制表示
void dfs(TreeNode *root, map<char, string> &hCode, string code){
    if(!root){
        return;
    }
    if(!root->left && !root->right){
        hCode[root->ch] = code;       // 没有子节点，那就是最后的字符
    }
    dfs(root->left, hCode, code + "0");    // 向左，编码+‘0’
    dfs(root->right, hCode, code + "1");   // 向右，编码+‘1’
}

// 输出字符串编码后的bits
string bits;
for(auto ch: s){
    bits += hCode[ch];
}

解码过程与实现

得到的二进制比特流是“导航”，指示一个树上的指针某一时刻要往哪里走。当走到底，就取出字符，并重新指向root。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TreeNode *ptr = root;
string res;
for(auto it: bits){
    if(it == '0'){
        // 0是向左的
        ptr = ptr->left;
    }else{
        // 1是向右的
        ptr = ptr->right;
    }
    // 走完这步，看是不是leaf节点
    if(ptr->ch != 0){
        res += ptr->ch;
        ptr = root;
    }
}

前缀树(字典树)

待补充