Advanced Trees(高级树)

remove from a BST(删除 BST 中的节点)

如果要删除的节点没有子节点,那么直接将其删除即可。

如果要删除的节点只有一个子节点,那么直接将其子节点替换为其位置即可。

如果要删除的节点有两个子节点,那么找到后继节点,然后将其替换为要删除的节点,然后删除后继节点。

void deleteNode(TreeNode*& node, int value) {
    if (node == nullptr) return;
    if (node->data == value) {
        if (node->left == nullptr && node->right == nullptr) {
            delete node;
            node = nullptr;
        } else if (node->left == nullptr) {
            TreeNode* temp = node;
            node = node->right;
            delete temp;
        } else if (node->right == nullptr) {
            TreeNode* temp = node;
            node = node->left;
            delete temp;
        } else {
            TreeNode* temp = getSuccessor(node->right);
            node->data = temp->data;
            delete temp;
        }
    } else if (node->data > value) {
        deleteNode(node->left, value);
    } else {
        deleteNode(node->right, value);
    }
}

TreeNode* getSuccessor(TreeNode* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

Stanford Set(斯坦福集合)

使用（略微修改的）二叉树实现

• 有序元素

• O(log N)时间搜索、添加和删除元素

---

树成员模板

returnType TreeSet::functionName(parameters)
{
    helper(root, parameters);
}

returnType helperName(TreeNode* node, parameters){
    ...
}

Tree maps(树映射)

• 每个树节点将同时存储一个键（key）和一个值（value）

• 树是按其键(key)的二叉搜索树（BST）顺序排列

• 键必须是可比较的（具备 < 运算符）以便进行排序

struct TreeMapNode {
    string key;
    int value;
    TreeMapNode* left;
    TreeMapNode* right;
};

Balanced Trees(平衡树)

当你的二叉搜索树不平衡的时候,你将会失去(log n)的性质.

就像如果你存入了 10000 个元素,但是你却只用了 100 个,那么你就失去了对这 100 个元素的快速查找的能力.

为了解决这个问题,我们需要使用一种平衡树,比如 AVL 树,红黑树,或者伸展树.

Red-Black Trees(红黑树)

给每个节点赋予红色或黑色的“颜色”。

• 根节点是黑色。根节点的直接子节点是红色。所有叶子节点是黑色。

• 如果一个节点是红色，则它的所有子节点必须都是黑色。

• 从一个节点向下到最底部的每条路径必须包含相同数量的“黑色”节点。

树旋转(Tree Rotations)

• 左旋(Left Rotation)：将一个节点的右子树上移，使其成为父节点的左子树。

• 右旋(Right Rotation)：将一个节点的左子树上移，使其成为父节点的右子树。

• 左右旋(Left-Right Rotation)：先左旋，再右旋。

• 右左旋(Right-Left Rotation)：先右旋，再左旋。

Tries(Prefix Trees)

非常适合用于查找前缀或作为字典使用

• 每个节点对应于一个单词的字母，通过遍历树来追溯这个单词

• 每个节点知道到该节点的字母是否能拼成一个单词

struct TrieNode{
    bool isWord;
    trieNode* children[26];
};

## 扩展(哈夫曼树)

哈夫曼树（Huffman Tree）是一种用于数据压缩的树形结构，主要用于生成哈夫曼编码。其主要特点和构建方法如下：

1. 构造一棵二叉树，每个节点对应于一个字符，树的高度为字符的个数。

2. 构造一棵带权路径最短的二叉树，权值即字符出现的频率。

3. 合并两个二叉树，权值较大的树作为左子树，权值较小的树作为右子树。

4. 重复步骤3，直到得到一棵只有一个节点的树，即哈夫曼树。