C++ 中的融合树

2025年5月15日 | 阅读 13 分钟

Fusion tree 是一种高级数据结构，主要用于存储和操作有序集合或关联数组。它由 Michael Fredman 和 Dan Willard 于 1990 年提出，旨在通过利用计算机处理器中的按位并行性和字级操作来实现更快的搜索速度。这种创新方法使得 Fusion Tree 能够比传统的平衡二叉搜索树等数据结构更有效地支持动态集合操作。

Fusion Tree 的主要概念是降低树的高度，从而减少搜索操作所需的比较次数。传统的平衡树，如 AVL 或 Red-Black 树，的高度与 log n 成比例，其中 n 是树中元素的数量。Fusion Tree 通过将有效高度降低到 w，其中 w 是机器的字大小（通常为 32 或 64 位），来改进这一点。这通过多种技术的组合实现，包括按位并行性、近似范围搜索和重要位的选择。

关键技术

按位并行性： Fusion Tree 利用处理器同时对多个位执行操作的能力。这意味着，树可以一次比较多个位的块，而不是逐个位进行比较，从而利用了机器的完整字大小。

近似范围搜索： Fusion Tree 采用近似范围搜索来缩小键在树节点子集中的位置。这有助于通过关注区分集合中键的重要位来减少比较次数。

压缩键： 在 Fusion Tree 中，通过提取重要位（即在所有键中变化最大的位）来以压缩形式表示键。这种压缩减小了键的大小并加快了比较操作。

字级并行性： 通过使用字级并行性，单个机器字可以用于存储多个信息片段，从而使树能够每次操作处理更多数据。

方法 1：使用按位提取和压缩。

按位提取和压缩是 Fusion Tree 中用于优化搜索操作的关键技术。这些技术使数据结构能够利用按位并行性，通过关注键的重要位来减少所需的比较次数。

按位提取

按位提取涉及识别 Fusion Tree 中存储的键的最高有效位（重要位）。选择这些重要位是基于它们区分键的能力。

识别键的变化： 第一步是检查键集并识别键变化最大的位位置。这些位置被认为是重要的，因为它们在区分一个键与另一个键方面贡献最大。

选择重要位： 一旦确定了可变的位位置，就会选择这些位的一个子集作为重要位。选择的重要位的数量是机器字大小 w 和树的分支因子 B 的函数。通常，重要位的数量为O(log B)。

示例：考虑一个小的键集：{12, 15, 7, 9}。它们的二进制形式为

12: 1100

15: 1111

7: 0111

9: 1001

在位置 0、1、2 和 3（从最低有效位开始）这些键之间存在差异。假设我们选择位置 1、2 和 3 作为重要位。

按位压缩

按位压缩涉及使用仅重要位创建每个键的压缩表示。它减小了键的大小，从而在搜索操作期间加快了比较速度。

压缩键

要压缩键，请提取重要位置的位并将它们连接起来形成一个更小的二进制数字。这通过移位和逻辑 AND 等按位运算来完成。

示例

对于键 12 (1100)，重要位位于位置 1、2 和 3。通过提取这些位，我们得到 100。

对于键 15 (1111)，重要位是：111。

对于键 7 (0111)，重要位是：111。

对于键 9 (1001)，重要位是：001。

然后使用这些压缩键在树内进行比较。

程序

#include <iostream>
#include <vector>
#include <algorithm>
const int WORD_SIZE = 32; // Assuming 32-bit machine
// Helper function to extract significant bits
std::vector<int> extractSignificantBits(const std::vector<int>& keys) {
    int maxKey = *std::max_element(keys.begin(), keys.end());
    int bitLength = 0;
    while (maxKey > 0) {
        bitLength++;
        maxKey >>= 1;
    }
    std::vector<int> significantBits;
    for (int i = 0; i < bitLength; i++) {
        significantBits.push_back(i);
    }
    return significantBits;
}
// Helper function to compress a key using significant bits
int compressKey(int key, const std::vector<int>& significantBits) {
    int compressedKey = 0;
    for (int bit : significantBits) {
        compressedKey = (compressedKey << 1) | ((key >> bit) & 1);
    }
    return compressedKey;
}
class FusionTreeNode {
public:
    std::vector<int> keys; // Original keys
    std::vector<int> compressedKeys; // Compressed keys
    std::vector<FusionTreeNode*> children;
    std::vector<int> significantBits;
    FusionTreeNode() = default;
    //Method to compress all keys in the node
    void compressKeys() {
        compressedKeys.clear();
        for (int key : keys) {
            compressedKeys.push_back(compressKey(key, significantBits));
        }
    }
    //Method to insert a key into the node
    void insert(int key) {
        auto it = std::lower_bound(keys.begin(), keys.end(), key);
        keys.insert(it, key);
        compressKeys();
        // Split node if necessary
        if (keys.size() > WORD_SIZE) {
            splitNode();
        }
    }
    //Method to split a node
    void splitNode() {
        int midIndex = keys.size() / 2;
        FusionTreeNode* leftChild = new FusionTreeNode();
        FusionTreeNode* rightChild = new FusionTreeNode(); 
        // Distribute keys to left and right children
        leftChild->keys.assign(keys.begin(), keys.begin() + midIndex);
        rightChild->keys.assign(keys.begin() + midIndex, keys.end());
        // Compress keys for left and right children
        leftChild->compressKeys();
        rightChild->compressKeys();
        // Clear keys in the current node and add children
        keys.clear();
        children.push_back(leftChild);
        children.push_back(rightChild);
    }
    //Method to search for a key in the node
    bool search(int key) {
        int compressedKey = compressKey(key, significantBits);
        auto it = std::lower_bound(compressedKeys.begin(), compressedKeys.end(), compressedKey); 
        if (it != compressedKeys.end() && *it == compressedKey) {
            // Further check the actual key to confirm the match
            return std::find(keys.begin(), keys.end(), key) != keys.end();
        }
        // Search in the corresponding child
        int index = it - compressedKeys.begin();
        if (index < children.size()) {
            return children[index]->search(key);
        }
        return false;
    }
    //Method to delete a key from the node
    void deleteKey(int key) {
        auto it = std::find(keys.begin(), keys.end(), key);
        if (it != keys.end()) {
            keys.erase(it);
            compressKeys();
        }
        // Handle rebalancing if necessary
    }
};
class FusionTree {
private:
    FusionTreeNode* root;
public:
    FusionTree(const std::vector<int>& keys) {
        root = new FusionTreeNode();
        root->keys = keys;
        root->significantBits = extractSignificantBits(keys);
        root->compressKeys();
    }
    //Method to insert a key into the fusion tree
    void insert(int key) {
        root->insert(key);
    }
    //Method to search for a key in the fusion tree
    bool search(int key) {
        return root->search(key);
    }
    //Method to delete a key from the fusion tree
    void deleteKey(int key) {
        root->deleteKey(key);
    }
};
int main() {
    // Sample keys
    std::vector<int> keys = {12, 15, 7, 9};
    // Create a fusion tree
    FusionTree fusionTree(keys);
    // Search for a key
    int searchKey = 15;
    std::cout << "Searching for key " << searchKey << ": " << (fusionTree.search(searchKey) ? "Found" : "Not found") << std::endl;
    // Insert a new key
    int newKey = 20;
    fusionTree.insert(newKey);
    std::cout << "Inserted key " << newKey << std::endl;
    // Delete a key
    int deleteKey = 7;
    fusionTree.deleteKey(deleteKey);
    std::cout << "Deleted key " << deleteKey << std::endl;
    // Search again for the deleted key
    std::cout << "Searching for key " << deleteKey << ": " << (fusionTree.search(deleteKey) ? "Found" : "Not found") << std::endl;
    return 0;
}

输出

Searching for key 15: Not found
Inserted key 20
Deleted key 7
Searching for key 7: Not found

说明

FusionTreeNode 类

此类表示 Fusion Tree 中的一个节点。它包含用于存储原始键、压缩键、子节点和重要位的向量。

CompressKeys(): 方法使用重要位压缩节点中存储的键。它遍历每个键，提取重要位，并构建压缩键。

Insert(): 方法将新键插入节点。它首先使用二分查找找到合适的插入位置。如果节点超过预定义的阈值（WORD_SIZE），它将分裂成两个子节点。

SplitNode(): 如果节点包含的键超过 WORD_SIZE 限制，则该方法将其分裂成两个子节点。它重新分配键到子节点并相应地对其进行压缩。

Search(): 方法在节点内搜索键。它使用重要位压缩搜索键，并在压缩键上执行二分查找。如果找到键，则会使用原始键验证匹配。

FusionTree 类

此类表示 Fusion Tree 本身，并作为操作的入口点。

构造函数： 使用一组键初始化 Fusion Tree。它创建根节点，将键分配给它，提取重要位，并压缩键。

Insert(): 将键插入委托给根节点。

Search(): 将键搜索委托给根节点。

DeleteKey(): 将键删除委托给根节点。

主函数

创建一个包含示例键的 Fusion Tree。演示了键操作，如搜索、插入和删除。输出这些操作的结果。

按位提取和压缩： 代码实现了从键中提取重要位并使用这些重要位压缩键的函数。

节点分裂： 当一个节点超过特定大小限制时，它会分裂成两个子节点以保持平衡和效率。

搜索优化： Fusion Tree 通过利用压缩键和二分查找来优化搜索操作。

可扩展性和性能

Fusion Tree 提供高效的搜索操作，尤其是在大型数据集的情况下。重要位和节点分裂的使用确保了树的平衡，有助于提高性能。

复杂度分析

时间复杂度

搜索操作

在 Fusion Tree 中，搜索操作主要涉及将搜索键与节点内的压缩键进行比较。

时间复杂度： O(logn)，其中 n 是 Fusion Tree 中的总键数。这种复杂度源于在节点内的压缩键上执行的二分查找。

插入和删除

Fusion Tree 中的插入和删除操作包括查找键的正确位置以及可能分裂节点以保持平衡。

时间复杂度： O(log^2 n) 均摊，其中 n 是总键数。

插入和删除可能会触发节点分裂，如果一个节点超过预定义的大小限制（WORD_SIZE）。这种分裂操作可能需要 O(logn) 时间。然而，由于它很少发生并且在多次操作中均摊，因此总体复杂度保持为 O(log^2 n) 均摊。

空间复杂度

内存使用

Fusion Tree 需要内存来存储键、压缩键、重要位和节点结构。

空间复杂度： O(nlogn)，其中 n 是总键数。

每个键都与其压缩表示一起存储，这需要额外的空间。此外，每个节点存储指向子节点的指针，这增加了空间开销。

节点分裂

当节点达到最大大小限制（WORD_SIZE）时，会发生节点分裂。

空间复杂度： 由于分裂过程中创建新节点，因此需要O(logn) 的额外空间。

当一个节点分裂时，它会创建两个新的子节点，每个子节点包含来自原始节点的键的一个子集。这些额外的节点会增加整体空间复杂度。

重要位

重要位决定了 Fusion Tree 中实现的压缩级别。

空间复杂度：O(logB)，其中 B 是树的分支因子。

选择的重要位的数量会影响压缩率，从而影响存储压缩键所需的空间。

方法 2：缓冲节点分裂方法

缓冲节点分裂方法是传统 Fusion Tree 数据结构的战略性增强，旨在通过减轻节点分裂操作的频率来优化性能。Fusion Tree 以其高效的有序数据存储和检索而闻名，它利用了按位并行性和压缩等技术。然而，频繁的节点分裂可能成为数据集快速变化的情况下的瓶颈。

在此方法中，每个 Fusion Tree 节点都配有一个缓冲区，作为键的临时存储空间。插入新键时，首先检查缓冲区是否有可用空间。如果缓冲区未满，则将键存储在那里。当缓冲区达到其限制时，会将一部分键传输到主键列表中。如果主列表超过其容量，则会发生分裂操作，但仅在考虑了缓冲区的内容之后。

通过延迟节点分裂直到主键列表显着填满，缓冲节点分裂减少了分裂频率和相关开销。此优化使 Fusion Tree 能够保持效率和可扩展性，使其适用于具有大型动态数据集的高性能应用程序。

程序

#include <iostream>
#include <vector>
#include <algorithm>
const int MAX_NODE_SIZE = 4; // Maximum number of keys in a node
const int BUFFER_SIZE = 2;   // Maximum number of keys in the buffer
class FusionTreeNode {
public:
    std::vector<int> keys;   // Main key list
    std::vector<int> buffer; // Buffer for temporarily storing keys
    FusionTreeNode* leftChild;
    FusionTreeNode* rightChild;
    FusionTreeNode() : leftChild(nullptr), rightChild(nullptr) {}
    // Insert a key into the node
    void insert(int key) {
        if (buffer.size() < BUFFER_SIZE) {
            buffer.push_back(key);
        } else {
            keys.insert(keys.end(), buffer.begin(), buffer.end());
            buffer.clear();
            if (keys.size() > MAX_NODE_SIZE) {
                splitNode();
            }
        }
    }
    // Split the node into two child nodes
    void splitNode() {
        leftChild = new FusionTreeNode();
        rightChild = new FusionTreeNode();
        int midIndex = keys.size() / 2;
        // Distribute keys between left and right child nodes
        leftChild->keys.assign(keys.begin(), keys.begin() + midIndex);
        rightChild->keys.assign(keys.begin() + midIndex, keys.end());
        // Clear the main key list
        keys.clear();
        // Move buffer contents to the main key list of the left child
        leftChild->keys.insert(leftChild->keys.end(), buffer.begin(), buffer.end());
        buffer.clear();
    }
    // Inorder traversal to print keys
    void inorder() {
        if (leftChild != nullptr) {
            leftChild->inorder();
        }
        for (int key : keys) {
            std::cout << key << " ";
        }
        if (rightChild != nullptr) {
            rightChild->inorder();
        }
    }
};
class FusionTree {
private:
    FusionTreeNode* root;
public:
    FusionTree() : root(nullptr) {}
    // Insert a key into the fusion tree
    void insert(int key) {
        if (root == nullptr) {
            root = new FusionTreeNode();
        }
        root->insert(key);
    }
    // Inorder traversal to print keys
    void printKeys() {
        if (root != nullptr) {
            root->inorder();
        }
    }
};
int main() {
    // Create a fusion tree
    FusionTree fusionTree;
    // Insert keys into the fusion tree
    fusionTree.insert(10);
    fusionTree.insert(5);
    fusionTree.insert(15);
    fusionTree.insert(3);
    fusionTree.insert(7);
    fusionTree.insert(12);
    fusionTree.insert(18);
    // Print keys in the fusion tree
    std::cout << "Keys in the fusion tree: ";
    fusionTree.printKeys();
    std::cout << std::endl;
    return 0;
}

输出

Keys in the fusion tree: 10 5 3 7

说明

提供的代码使用 C++ 在 Fusion Tree 数据结构中实现了缓冲节点分裂方法。此方法通过减少节点分裂操作的频率来优化 Fusion Tree 的性能，从而提高效率。

FusionTreeNode 类

此类表示 Fusion Tree 中的一个节点。它维护用于存储键和用于在插入期间临时存储键的缓冲区的向量。

insert() 方法将新键插入节点。如果缓冲区未满，则将键添加到缓冲区。一旦缓冲区达到限制，键就会移至主键列表。如果主键列表超过最大大小，则节点将分裂成两个子节点。

splitNode() 方法将节点分成两个子节点，并在保持平衡的同时在它们之间重新分配键。

FusionTree 类

此类管理 Fusion Tree 结构。它包含指向根节点的指针。insert() 方法通过将插入操作委托给根节点来将新键插入 Fusion Tree。printKeys() 方法执行 Fusion Tree 的中序遍历以以排序顺序打印所有键。

主函数

它创建了一个 FusionTree 实例。使用 insert() 方法，将多个键插入 Fusion Tree。调用printKeys() 方法打印 Fusion Tree 中的所有键。

缓冲节点分裂

此方法的一个关键特性是使用节点内的缓冲区。此缓冲区在插入操作期间临时保存键。节点分裂被推迟到主键列表超过一定大小，从而降低了分裂操作的频率并提高了效率。

复杂度分析

时间复杂度

插入操作

将键插入 Fusion Tree 节点时，其复杂度取决于节点中已存在的键的数量以及缓冲区的大小。

在最佳情况下，当缓冲区有可用空间时，插入是O(1），因为它只是将键附加到缓冲区。在最坏情况下，当缓冲区已满并发生分裂时，插入是 O(logn)，其中 n 是主键列表中的键数。

总体而言，考虑到这两种情况以及分裂的频率，插入的均摊时间复杂度可近似为O(logn)。

节点分裂操作

当主键列表在包含缓冲区中的键后超过最大节点大小时，会发生节点分裂。分裂节点的复杂度为 O(n)，其中 n 是主键列表中的键数。这涉及在两个子节点之间重新分配键。然而，节点分裂被推迟到主键列表达到一定大小时，从而降低了分裂操作的频率并均摊了其成本。

遍历操作（打印键）

遍历 Fusion Tree 以打印所有键涉及中序遍历。中序遍历的时间复杂度为 O(n)，其中 n 是 Fusion Tree 中的总键数。这是因为每个键都会被访问一次。遍历复杂度不受缓冲机制和分裂操作的影响。

空间复杂度

内存使用

Fusion Tree 的空间复杂度主要取决于节点数量以及其中存储的键。每个 Fusion Tree 节点都需要内存来存储键、缓冲区和指向子节点的指针。

空间复杂度为O(n)，其中 n 是存储在 Fusion Tree 中的总键数。此外，维护缓冲区和指针也存在开销，这会增加空间复杂度。

缓冲区大小

缓冲区的空间复杂度为O(1)，因为它固定且独立于 Fusion Tree 中的键数。缓冲区大小参数和最大节点大小会影响内存需求，但不会显著影响总体空间复杂度。

总而言之，Fusion Tree 中的缓冲节点分裂方法为键操作提供了高效的时间和空间复杂度。尽管偶尔会发生分裂，但插入和遍历操作分别保持 O(logn) 和 O(n) 的复杂度。空间复杂度为O(n)，主要受 Fusion Tree 中存储的键数影响。总而言之，此方法优化了 Fusion Tree 的性能，使其适用于具有大型动态数据集的应用程序。

下一主题Goulds-sequence-in-cpp

C++ 中的融合树

关键技术

方法 1：使用按位提取和压缩。

按位提取

示例

方法 2：缓冲节点分裂方法

程序

联系信息

关注我们

教程

面试题

在线编译器

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：缓冲节点分裂方法

程序

相关帖子

C++ std::chrono::steady_clock

C++ 中用 Sundaram 筛法打印小于 n 的所有素数

C++ 中的重复数字

C++ std::to_underlying 函数

C++ 中的双基半完全数

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

C++ 中的弹跳数字

C++ 中 std::sort 和 std::stable_sort() 函数的区别

C++ 中的三法则

C++ 中如何处理 SIGABRT 信号

订阅 Tpoint Tech

联系信息

关注我们

教程