C++ 替罪羊树

2025年03月22日 | 阅读 9 分钟

牺牲树（Scapegoat Trees） 是一种自平衡二叉搜索树，通过在树失衡时重建子树来保持其操作（如插入、删除和搜索）的效率。与 AVL 树或红黑树在每次插入或删除后立即使用旋转来维持平衡不同，牺牲树采用了一种不那么激进的平衡策略，它允许树在一段时间内保持失衡。

这意味着当树变得过于失衡时，树不会立即重新平衡，而是允许失衡增长。一旦失衡超出了树深处的某个阈值，就会重建一个子树。通过使用 α-平衡准则（用于检测失衡的阈值），树可以确保其高度保持对数级别。这有助于在处理动态和不可预测的数据集时保持高效的搜索、插入和删除操作。

关键特性

C++ 中牺牲树 的几个关键特性如下：

二叉搜索树 (BST)： 牺牲树遵循标准的 BST 属性。对于任何节点，左子树包含小于该节点值的元素，右子树包含大于该节点值的元素。这种结构允许高效的搜索，其时间复杂度与树的高度成正比。
平衡准则： 牺牲树根据由参数 α 控制的准则来维持平衡。该准则确保在每个子树中，任一侧都不会比另一侧显著大。如果此时条件被违反，例如子树失衡，则会对相关的子树进行纠正。它不依赖于像 AVL 或红黑树那样的旋转；相反，当出现失衡问题时，树会重新构建整个子树。它将树的高度保持在节点数量的对数范围内。
α-平衡： 当一个节点的某个子树的大小超过该节点所代表的子树总大小时，该节点就被认为是失衡的。如果检测到失衡，树会找到一个“牺牲节点”（最深的失衡节点），并重建以该节点为根的子树。

关键操作

C++ 中牺牲树 的几个关键操作如下：

1. 插入

节点最初可以像在普通 BST 中一样插入到牺牲树中。通过与现有节点比较，将节点放置在其正确的位置。插入后，树会检查是否有节点刚刚变得失衡，方法是将新插入节点的深度与应有的深度（与 log(n) 成正比，其中 (n) 是节点数）进行比较。如果实际深度大于此阈值，树将找到最深的失衡节点（牺牲节点），并重建以该节点为根的子树以恢复平衡。

2. 删除

牺牲树中的删除操作类似于普通 BST 的删除操作。将被删除的节点被移除，树被重构以保持二叉搜索树 (BST) 的属性。然而，与插入不同，删除不会立即触发子树重建。相反，只有当删除后树中的节点数量下降到由树达到的最大大小的某个比例决定的阈值以下时，树才会重建。这使得即使在多次删除后，高度也能保持在对数范围内。

3. 查找牺牲节点

牺牲节点是检测到失衡的节点。插入后，如果其深度超过对数边界，树将从新插入的节点向根回溯，并检查每个节点的子树大小。第一个违反 α-平衡条件的节点被称为牺牲节点。该牺牲节点将成为将被重建的子树的根。

4. 重建

一旦找到牺牲节点，该节点处的子树将被重建为一个最优平衡的子树。通常，这种重建是通过收集子树中的所有节点，排序，然后构建一个新的平衡树来完成的。这种重建确保了整个树的高度最多与 log(n) 成正比；因此，由于一些失衡的节点，不会发生显著的性能下降。

示例

让我们通过一个例子来说明 C++ 中的牺牲树。

 
#include <iostream>
#include <vector>
#include <cmath>

template <typename T>
class ScapegoatTree {
private:
    struct Node {
        T key;
        Node* left;
        Node* right;
        int size;
        Node(T k) : key(k), left(nullptr), right(nullptr), size(1) {}
    };
    Node* root;
    int maxSize;
    const double alpha; 
    // Calculate the Size of a given node's subtree
    int size(Node* node) {
        return node ? node->size : 0;
    }
    // Update the Size of a node based on its children
    void updateSize(Node* node) {
        if (node) {
            node->size = 1 + size(node->left) + size(node->right);
        }
    }
    // Check if a node is alpha-balanced
    bool isBalanced(Node* node) {
        return size(node->left) <= alpha * size(node) && size(node->right) <= alpha * size(node);
    }
    // Perform an in-order traversal to collect nodes in a subtree
    void flatten(Node* node, std::vector<Node*>& nodeList) {
        if (!node) return;
        flatten(node->left, nodeList);
        nodeList.push_back(node);
        flatten(node->right, nodeList);
    }
    // Rebuild a subtree into a balanced BST from a sorted list of nodes
    Node* buildBalancedTree(std::vector<Node*>& nodeList, int start, int end) {
        if (start > end) return nullptr;
        int mid = (start + end) / 2;
        Node* node = nodeList[mid];
        node->left = buildBalancedTree(nodeList, start, mid - 1);
        node->right = buildBalancedTree(nodeList, mid + 1, end);
        updateSize(node);
        return node;
    }
    // Rebuild the subtree rooted at the given node
    Node* rebuild(Node* node) {
        std::vector<Node*> nodeList;
        flatten(node, nodeList);
        return buildBalancedTree(nodeList, 0, nodeList.size() - 1);
    }
    // Recursively insert a node and return the scapegoat node if unbalanced
    Node* insert(Node* node, T key, Node*& scapegoat) {
        if (!node) return new Node(key);
        if (key < node->key) {
            node->left = insert(node->left, key, scapegoat);
        } else {
            node->right = insert(node->right, key, scapegoat);
        }
        updateSize(node);
        if (!isBalanced(node)) {
            scapegoat = node;
        }
        return node;
    }
    // Recursively search for a node with a given key
    Node* search(Node* node, T key) {
        if (!node || node->key == key) return node;
        if (key < node->key) return search(node->left, key);
        return search(node->right, key);
    }
    // Find the minimum node in a subtree
    Node* findMin(Node* node) {
        while (node->left) node = node->left;
        return node;
    }
    // Recursively delete a node and return the updated root
    Node* deleteNode(Node* node, T key) {
        if (!node) return nullptr;
        if (key < node->key) {
            node->left = deleteNode(node->left, key);
        } else if (key > node->key) {
            node->right = deleteNode(node->right, key);
        } else {
            // Node found
            if (!node->left) {
                Node* rightChild = node->right;
                delete node;
                return rightChild;
            } else if (!node->right) {
                Node* leftChild = node->left;
                delete node;
                return leftChild;
            } else {
                Node* minRight = findMin(node->right);
                node->key = minRight->key;
                node->right = deleteNode(node->right, minRight->key);
            }
        }
        updateSize(node);
        return node;
    }
    // Recursively find the depth of the inserted node
    int depth(Node* node, T key, int currentDepth) {
        if (!node) return -1;
        if (node->key == key) return currentDepth;
        if (key < node->key) return depth(node->left, key, currentDepth + 1);
        return depth(node->right, key, currentDepth + 1);
    }
    // Calculate the logarithmic bound for the height
    int logBound(int n) {
        return std::floor(log(n) / log(1.0 / alpha));
    }
    // Private in-order traversal method for printing
    void inOrder(Node* node) {
        if (!node) return;
        inOrder(node->left);
        std::cout << node->key << " ";
        inOrder(node->right);
    }

public:
    ScapegoatTree(double alpha = 2.0 / 3.0) : root(nullptr), maxSize(0), alpha(alpha) {}
    // Insert a key into the scapegoat tree
    void insert(T key) {
        Node* scapegoat = nullptr;
        root = insert(root, key, scapegoat);
        if (!scapegoat) {
            int currentSize = size(root);
            if (currentSize > maxSize) {
                maxSize = currentSize;
            }
        } else {
            if (depth(root, key, 0) > logBound(maxSize)) {
                root = rebuild(scapegoat);
            }
        }
    }
    // Search for a key in the tree
    bool search(T key) {
        return search(root, key) != nullptr;
    }
    // Delete a key from the tree
    void remove(T key) {
        root = deleteNode(root, key);
        if (size(root) < alpha * maxSize) {
            root = rebuild(root);
            maxSize = size(root);
        }
    }
    // Public method to print the tree (in-order traversal)
    void printTree() {
        inOrder(root);
        std::cout << std::endl;
    }
};
int main() {
    ScapegoatTree<int> tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(30);
    tree.insert(40);
    tree.insert(50);
    tree.insert(60);
    tree.insert(70);
    std::cout << "Tree after insertions: ";
    tree.printTree();
    std::cout << "Searching for 30: " << (tree.search(30) ? "Found" : "Not Found") << std::endl;
    std::cout << "Searching for 100: " << (tree.search(100) ? "Found" : "Not Found") << std::endl;
    tree.remove(30);
    std::cout << "Tree after deleting 30: ";
    tree.printTree();
    return 0;
}   

输出

 
Tree after insertions: 30 40 50 60 70 
Searching for 30: Found
Searching for 100: Not Found
Tree after deleting 30: 40 50 60 70

说明

此 C++ 牺牲树实现是一种自平衡二叉搜索树 (BST)，它通过偶尔重建失衡的子树来保持平衡。代码包含关键组件，如节点结构、插入、搜索、删除和子树重建。

节点结构

Node struct 代表每个树节点，它包含一个键 (key)、指向左右子节点的指针 (left 和 right) 以及一个整数 size，表示以该节点为根的子树中的节点数。size 字段至关重要，因为它有助于检查子树的平衡。使用此 α-平衡准则来检测平衡并重建失衡的子树，以确保其树的高度保持对数范围。因此，即使处理动态和非确定性数据集，搜索、插入和删除通常也是高效的。

树结构

主类 ScapegoatTree 包含根节点 (root)、树达到的最大大小 (maxSize) 和平衡因子 (alpha)，通常设置为 2/3。平衡因子控制何时将子树视为失衡。在空树中，根最初为 nullptr，maxSize 初始化为零。

插入操作

insert() 函数首先执行典型的 BST 插入。插入新节点后，树会使用 isBalanced() 函数检查从新插入节点到根的路径上的任何节点是否已失衡。如果其左子树或右子树的大小大于其总大小的某个分数（由 alpha 控制），则该节点失衡。

如果找到失衡，将识别最深的失衡节点（牺牲节点）。插入操作保证了 O(logn) 的摊销时间复杂度，因为重建只在失衡发生时偶尔发生。

搜索操作

search() 函数很简单。它像常规 BST 一样遍历树以查找包含所需键的节点。如果找到键，则返回该节点；否则，返回 nullptr。

删除操作

remove() 函数遵循标准的 BST 删除规则，其中通过用其中序前驱或后继（如果它有两个子节点）替换节点，或者通过删除节点并重新连接其子节点来移除节点。与插入不同，删除不会立即触发重建。相反，会检查树的大小，如果它相对于最大大小 (小于 alpha * maxSize) 变得太小，则会重建整个树以确保平衡。

子树重建

子树重建过程在维持牺牲树的平衡方面起着至关重要的作用。它涉及收集子树中的所有节点（使用 flatten() 函数），并将它们重建为一棵完美平衡的树。它确保失衡的子树能够以对树的其余部分最小的干扰得到纠正。

复杂度分析

时间复杂度

插入

在平衡树的情况下，牺牲树中的插入与二叉搜索树 (BST) 中的插入类似，平均需要 O(logn) 的时间。然而，插入后，树可能会失衡，从而触发牺牲节点的检测和子树的重建。
查找牺牲节点涉及遍历从插入节点到根的路径，这需要 O(logn) 时间。
摊销复杂度： 树的重建不频繁。尽管重建子树需要 O(k) 时间，但它只会在多次插入后发生，并且插入的摊销成本仍为 O(logn)。这是因为偶尔重建的成本分摊到许多操作上。

删除

如果树是平衡的，则删除遵循标准的 BST 删除过程，耗时 O(logn)。
与插入不同，删除不会立即触发重建。相反，只有当树的大小相对于达到的最大大小的比例低于某个阈值时，才会触发重建。如果触发，重建整个树需要 O(n) 时间，但同样，这种情况很少发生。
摊销复杂度： 与插入类似，删除的摊销时间复杂度为 O(logn)。

搜索

牺牲树中的搜索与标准 BST 搜索相同，如果树保持平衡，其时间复杂度为 O(logn)。

空间复杂度

空间复杂度为 O(n)，因为树中的每个节点都需要恒定空间，而树中有 n 个节点。
此外，在重建过程中，会使用一个临时数组来存储子树的节点，这可能需要 O(k) 的空间，但 k≤n。因此，总空间复杂度为O(n)。

下一主题C++ 中的连续树

C++ 替罪羊树

关键特性

关键操作

1. 插入

2. 删除

3. 查找牺牲节点

4. 重建

示例

说明

复杂度分析

时间复杂度

空间复杂度

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 替罪羊树

关键特性

关键操作

1. 插入

2. 删除

3. 查找牺牲节点

4. 重建

示例

说明

复杂度分析

时间复杂度

空间复杂度

相关帖子

C++ 中在七段显示器中使用最少段查找元素

C++ Gilbert-Johnson-Keerthi (GJK) 算法

C++ 中的拉马努金-纳格尔猜想

C++ 连接木棍的最小成本

C++ 中的豪爽数

C++ 中的可变 lambda

C++ 中的标点符号

C++ 中的尼科马库斯定理（奇数正整数的第 k 组之和）

C++ 中的自传数字