当前位置： 首页 > article >正文

B树B+树

article 2024/12/28 22:58:33 
#include <stdio.h>
#include <stdlib.h>

// 定义 B 树的最小度数（每个节点至少有 t 个孩子，最多有 2t - 1 个键值）
#define T 3

// B 树节点结构
typedef struct BTreeNode {
    int *keys;               // 存储键值的数组
    int t;                   // 最小度数
    struct BTreeNode **C;    // 子节点指针数组
    int n;                   // 当前节点的键值个数
    int leaf;                // 是否是叶子节点
} BTreeNode;

// 创建一个新的 B 树节点
BTreeNode *createNode(int t, int leaf) {
    BTreeNode *node = (BTreeNode *)malloc(sizeof(BTreeNode));
    if (!node) {
        fprintf(stderr, "Memory allocation failed for BTreeNode.\n");
        exit(EXIT_FAILURE);
    }

    node->t = t;
    node->leaf = leaf;
    node->keys = (int *)malloc((2 * t - 1) * sizeof(int));
    node->C = (BTreeNode **)malloc(2 * t * sizeof(BTreeNode *));
    node->n = 0;

    if (!node->keys || !node->C) {
        fprintf(stderr, "Memory allocation failed for keys or children.\n");
        exit(EXIT_FAILURE);
    }

    return node;
}

// 遍历 B 树（中序遍历）
void traverse(BTreeNode *root) {
    if (root == NULL) return;

    // 遍历每个键值前的子树
    for (int i = 0; i < root->n; i++) {
        if (!root->leaf) {
            traverse(root->C[i]);
        }
        printf("%d ", root->keys[i]); // 打印键值
    }

    // 遍历最后一个子树
    if (!root->leaf) {
        traverse(root->C[root->n]);
    }
}

// 搜索键值
BTreeNode *search(BTreeNode *root, int k) {
    int i = 0;

    // 在当前节点中查找键值的位置
    while (i < root->n && k > root->keys[i]) {
        i++;
    }

    // 如果找到键值，返回当前节点
    if (i < root->n && root->keys[i] == k) {
        return root;
    }

    // 如果是叶子节点，直接返回 NULL
    if (root->leaf) {
        return NULL;
    }

    // 在对应的子节点递归查找
    return search(root->C[i], k);
}

// 分裂子节点 y
void splitChild(BTreeNode *parent, int i, BTreeNode *y) {
    int t = y->t;

    // 创建新节点 z，存储 y 的后半部分键值和子节点
    BTreeNode *z = createNode(t, y->leaf);
    z->n = t - 1;

    // 将 y 的后半部分键值复制到 z
    for (int j = 0; j < t - 1; j++) {
        z->keys[j] = y->keys[j + t];
    }

    // 如果 y 不是叶子节点，将 y 的后半部分子节点指针复制到 z
    if (!y->leaf) {
        for (int j = 0; j < t; j++) {
            z->C[j] = y->C[j + t];
        }
    }

    y->n = t - 1; // 更新 y 的键值个数

    // 将 z 插入到 parent 的子节点列表中
    for (int j = parent->n; j >= i + 1; j--) {
        parent->C[j + 1] = parent->C[j];
    }
    parent->C[i + 1] = z;

    // 将 y 的中间键提升到 parent
    for (int j = parent->n - 1; j >= i; j--) {
        parent->keys[j + 1] = parent->keys[j];
    }
    parent->keys[i] = y->keys[t - 1];
    parent->n++;
}

// 插入到非满节点中
void insertNonFull(BTreeNode *node, int k) {
    int i = node->n - 1;

    // 如果是叶子节点
    if (node->leaf) {
        // 找到插入位置并移动键值
        while (i >= 0 && k < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = k; // 插入键值
        node->n++;
    } else {
        // 找到子节点的位置
        while (i >= 0 && k < node->keys[i]) {
            i--;
        }
        i++;

        // 如果子节点已满，先分裂子节点
        if (node->C[i]->n == 2 * node->t - 1) {
            splitChild(node, i, node->C[i]);

            // 判断 k 应插入到哪个子节点
            if (k > node->keys[i]) {
                i++;
            }
        }
        insertNonFull(node->C[i], k);
    }
}

// 插入键值到 B 树
void insert(BTreeNode **rootRef, int k, int t) {
    BTreeNode *root = *rootRef;

    // 如果根节点已满
    if (root->n == 2 * t - 1) {
        // 创建新根节点
        BTreeNode *newRoot = createNode(t, 0);
        newRoot->C[0] = root;

        // 分裂旧根节点
        splitChild(newRoot, 0, root);

        // 插入到合适的子节点
        int i = 0;
        if (k > newRoot->keys[0]) {
            i++;
        }
        insertNonFull(newRoot->C[i], k);

        *rootRef = newRoot; // 更新根节点
    } else {
        insertNonFull(root, k);
    }
}

// 释放 B 树节点
void freeBTree(BTreeNode *node) {
    if (node == NULL) return;

    if (!node->leaf) {
        for (int i = 0; i <= node->n; i++) {
            freeBTree(node->C[i]);
        }
    }

    free(node->keys);
    free(node->C);
    free(node);
}

// 主函数
int main() {
    // 创建空 B 树
    BTreeNode *root = createNode(T, 1);

    // 插入一些数据
    insert(&root, 10, T);
    insert(&root, 20, T);
    insert(&root, 5, T);
    insert(&root, 6, T);
    insert(&root, 12, T);
    insert(&root, 30, T);
    insert(&root, 7, T);
    insert(&root, 17, T);

    // 遍历 B 树
    printf("Traversal of the B-Tree:\n");
    traverse(root);
    printf("\n");

    // 搜索键值
    int key = 6;
    printf("Searching for key %d in the B-Tree...\n", key);
    BTreeNode *result = search(root, key);
    if (result != NULL) {
        printf("Key %d found in the B-Tree.\n", key);
    } else {
        printf("Key %d not found in the B-Tree.\n", key);
    }

    // 释放 B 树
    freeBTree(root);

    return 0;
}

C语言b树

  1. 数据结构：

    • 每个节点存储一个 keys 数组和一个 C 子节点指针数组。
    • n 表示当前键值数，leaf 表示是否为叶子节点。

  2. 主要功能：

    • 创建节点：createNode 动态分配节点。
    • 插入：插入时处理节点分裂，保证 B 树平衡。
    • 查找：递归在树中查找键值。
    • 遍历：按中序遍历输出键值。
    • 释放内存：freeBTree 确保无内存泄漏。

  3. 增强健壮性：

    • 内存分配检测：每次动态分配都检查是否成功。
    • 边界条件处理：空树或单节点插入、满节点分裂等情况均已处理。
#include <iostream>
#include <vector>
#include <memory>
using namespace std;

// 定义 B 树的最小度数
const int T = 3; // 每个节点最多 2*T-1 个键，最少 T-1 个键

// B 树节点类
class BTreeNode {
public:
    vector<int> keys;                   // 键值数组
    vector<shared_ptr<BTreeNode>> children; // 子节点指针数组
    int t;                              // 最小度数
    bool leaf;                          // 是否为叶子节点

    // 构造函数
    BTreeNode(int t, bool leaf) : t(t), leaf(leaf) {}

    // 遍历 B 树（中序遍历）
    void traverse() {
        int i;
        // 遍历每个键值前的子树
        for (i = 0; i < keys.size(); i++) {
            if (!leaf) {
                children[i]->traverse();
            }
            cout << keys[i] << " ";
        }

        // 遍历最后一个子树
        if (!leaf) {
            children[i]->traverse();
        }
    }

    // 搜索键值
    shared_ptr<BTreeNode> search(int k) {
        int i = 0;

        // 找到第一个大于或等于 k 的键
        while (i < keys.size() && k > keys[i]) {
            i++;
        }

        // 如果键值等于 k，返回当前节点
        if (i < keys.size() && keys[i] == k) {
            return shared_from_this();
        }

        // 如果是叶子节点，则键值不存在
        if (leaf) {
            return nullptr;
        }

        // 在对应的子节点递归查找
        return children[i]->search(k);
    }

    // 分裂子节点
    void splitChild(int i, shared_ptr<BTreeNode> y) {
        // 创建一个新节点 z，存储 y 的后半部分键值和子节点
        auto z = make_shared<BTreeNode>(y->t, y->leaf);
        z->keys.resize(t - 1);

        for (int j = 0; j < t - 1; j++) {
            z->keys[j] = y->keys[j + t];
        }

        // 如果 y 不是叶子节点，将 y 的后半部分子节点移动到 z
        if (!y->leaf) {
            z->children.resize(t);
            for (int j = 0; j < t; j++) {
                z->children[j] = y->children[j + t];
            }
        }

        // 调整 y 的键值数
        y->keys.resize(t - 1);

        // 在父节点中插入新的子节点 z
        children.insert(children.begin() + i + 1, z);

        // 将 y 的中间键提升到父节点
        keys.insert(keys.begin() + i, y->keys[t - 1]);
    }

    // 插入到非满节点中
    void insertNonFull(int k) {
        int i = keys.size() - 1;

        if (leaf) {
            // 如果是叶子节点，找到插入位置并插入
            while (i >= 0 && k < keys[i]) {
                i--;
            }
            keys.insert(keys.begin() + i + 1, k);
        } else {
            // 找到子节点位置
            while (i >= 0 && k < keys[i]) {
                i--;
            }
            i++;

            // 如果子节点已满，先分裂子节点
            if (children[i]->keys.size() == 2 * t - 1) {
                splitChild(i, children[i]);

                // 判断插入位置
                if (k > keys[i]) {
                    i++;
                }
            }
            children[i]->insertNonFull(k);
        }
    }
};

// B 树类
class BTree {
private:
    shared_ptr<BTreeNode> root; // 根节点
    int t;                      // 最小度数

public:
    // 构造函数
    BTree(int t) : t(t), root(nullptr) {}

    // 遍历 B 树
    void traverse() {
        if (root != nullptr) {
            root->traverse();
        }
    }

    // 搜索键值
    shared_ptr<BTreeNode> search(int k) {
        if (root == nullptr) {
            return nullptr;
        } else {
            return root->search(k);
        }
    }

    // 插入键值
    void insert(int k) {
        if (root == nullptr) {
            // 如果根节点为空，创建一个新节点
            root = make_shared<BTreeNode>(t, true);
            root->keys.push_back(k);
        } else {
            // 如果根节点已满
            if (root->keys.size() == 2 * t - 1) {
                // 创建一个新根节点
                auto newRoot = make_shared<BTreeNode>(t, false);

                // 将旧根节点作为新根的子节点
                newRoot->children.push_back(root);

                // 分裂旧根节点
                newRoot->splitChild(0, root);

                // 插入到合适的子节点
                if (k > newRoot->keys[0]) {
                    newRoot->children[1]->insertNonFull(k);
                } else {
                    newRoot->children[0]->insertNonFull(k);
                }

                root = newRoot; // 更新根节点
            } else {
                root->insertNonFull(k);
            }
        }
    }
};

// 主函数
int main() {
    // 创建 B 树
    BTree tree(T);

    // 插入一些数据
    tree.insert(10);
    tree.insert(20);
    tree.insert(5);
    tree.insert(6);
    tree.insert(12);
    tree.insert(30);
    tree.insert(7);
    tree.insert(17);

    // 遍历 B 树
    cout << "Traversal of the B-Tree:\n";
    tree.traverse();
    cout << endl;

    // 搜索键值
    int key = 6;
    cout << "Searching for key " << key << " in the B-Tree..." << endl;
    auto result = tree.search(key);
    if (result != nullptr) {
        cout << "Key " << key << " found in the B-Tree.\n";
    } else {
        cout << "Key " << key << " not found in the B-Tree.\n";
    }

    return 0;
}

CPP版本b树

  1. 数据结构设计：

    • BTreeNode 类表示 B 树的节点，包含键值数组 (keys) 和子节点指针数组 (children)。
    • BTree 类表示 B 树，封装了树的根节点和相关操作。

  2. 核心操作：

    • 创建节点：通过构造函数动态创建新节点。
    • 插入：
      • 如果根节点已满，会创建一个新根节点并分裂旧根。
      • 插入操作通过递归调整子节点，确保 B 树的平衡性。
    • 查找：在节点中二分查找键值并递归到子节点。
    • 遍历：中序遍历所有键值。

  3. 增强健壮性：

    • 使用 vector 自动管理数组内存，避免手动分配和释放。
    • 使用 shared_ptr 管理节点的生命周期，防止内存泄漏。
    • 异常检测和边界条件处理（如空树或满节点）。

  4. 输入输出：

    • 插入一组数据构建 B 树。
    • 遍历 B 树，输出所有键值。
    • 搜索指定键值，输出是否存在。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 定义 B+树的最小度数 T
#define T 3

// 定义 B+树节点结构
typedef struct BPTreeNode {
    int *keys;                      // 键值数组
    struct BPTreeNode **children;   // 子节点指针数组
    int n;                          // 当前节点的键值数量
    bool isLeaf;                    // 是否为叶子节点
    struct BPTreeNode *next;        // 用于叶子节点的链表指针
} BPTreeNode;

// 创建一个新节点
BPTreeNode *createNode(bool isLeaf) {
    BPTreeNode *node = (BPTreeNode *)malloc(sizeof(BPTreeNode));
    if (!node) {
        fprintf(stderr, "Memory allocation failed for BPTreeNode.\n");
        exit(EXIT_FAILURE);
    }

    node->keys = (int *)malloc((2 * T - 1) * sizeof(int));
    node->children = (BPTreeNode **)malloc(2 * T * sizeof(BPTreeNode *));
    node->n = 0;
    node->isLeaf = isLeaf;
    node->next = NULL;

    if (!node->keys || !node->children) {
        fprintf(stderr, "Memory allocation failed for keys or children.\n");
        exit(EXIT_FAILURE);
    }

    return node;
}

// 遍历 B+树的叶子节点（范围查询）
void traverse(BPTreeNode *root) {
    if (!root) return;

    // 找到最左叶子节点
    while (!root->isLeaf) {
        root = root->children[0];
    }

    // 遍历所有叶子节点
    while (root) {
        for (int i = 0; i < root->n; i++) {
            printf("%d ", root->keys[i]);
        }
        root = root->next;
    }
    printf("\n");
}

// 搜索键值
BPTreeNode *search(BPTreeNode *root, int key) {
    if (!root) return NULL;

    int i = 0;

    // 找到键值范围
    while (i < root->n && key > root->keys[i]) {
        i++;
    }

    if (root->isLeaf) {
        // 如果是叶子节点，检查是否找到
        if (i < root->n && root->keys[i] == key) {
            return root;
        }
        return NULL;
    }

    // 如果不是叶子节点，递归到子节点
    return search(root->children[i], key);
}

// 分裂非叶子节点的子节点
void splitNonLeafChild(BPTreeNode *parent, int idx, BPTreeNode *child) {
    // 创建新节点
    BPTreeNode *newNode = createNode(child->isLeaf);
    newNode->n = T - 1;

    // 将后半部分的键值复制到新节点
    for (int i = 0; i < T - 1; i++) {
        newNode->keys[i] = child->keys[i + T];
    }

    // 如果不是叶子节点，将子节点指针复制到新节点
    if (!child->isLeaf) {
        for (int i = 0; i < T; i++) {
            newNode->children[i] = child->children[i + T];
        }
    }

    child->n = T - 1;

    // 插入新的子节点到父节点
    for (int i = parent->n; i >= idx + 1; i--) {
        parent->children[i + 1] = parent->children[i];
    }
    parent->children[idx + 1] = newNode;

    // 将中间键值插入到父节点
    for (int i = parent->n - 1; i >= idx; i--) {
        parent->keys[i + 1] = parent->keys[i];
    }
    parent->keys[idx] = child->keys[T - 1];
    parent->n++;
}

// 分裂叶子节点
void splitLeafChild(BPTreeNode *parent, int idx, BPTreeNode *leaf) {
    // 创建一个新叶子节点
    BPTreeNode *newLeaf = createNode(true);
    newLeaf->n = T - 1;

    // 将后半部分的键值复制到新叶子节点
    for (int i = 0; i < T - 1; i++) {
        newLeaf->keys[i] = leaf->keys[i + T - 1];
    }

    leaf->n = T - 1;

    // 设置叶子节点的链表指针
    newLeaf->next = leaf->next;
    leaf->next = newLeaf;

    // 插入新叶子节点到父节点
    for (int i = parent->n; i >= idx + 1; i--) {
        parent->children[i + 1] = parent->children[i];
    }
    parent->children[idx + 1] = newLeaf;

    // 将新叶子节点的第一个键值插入到父节点
    for (int i = parent->n - 1; i >= idx; i--) {
        parent->keys[i + 1] = parent->keys[i];
    }
    parent->keys[idx] = newLeaf->keys[0];
    parent->n++;
}

// 插入到非满节点中
void insertNonFull(BPTreeNode *node, int key) {
    int i = node->n - 1;

    if (node->isLeaf) {
        // 找到插入位置
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->n++;
    } else {
        // 找到子节点位置
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;

        // 如果子节点已满
        if (node->children[i]->n == 2 * T - 1) {
            if (node->children[i]->isLeaf) {
                splitLeafChild(node, i, node->children[i]);
            } else {
                splitNonLeafChild(node, i, node->children[i]);
            }

            // 确定插入位置
            if (key > node->keys[i]) {
                i++;
            }
        }
        insertNonFull(node->children[i], key);
    }
}

// 插入键值到 B+树
void insert(BPTreeNode **rootRef, int key) {
    BPTreeNode *root = *rootRef;

    if (!root) {
        // 如果根节点为空，创建一个新节点
        root = createNode(true);
        root->keys[0] = key;
        root->n = 1;
        *rootRef = root;
        return;
    }

    // 如果根节点已满
    if (root->n == 2 * T - 1) {
        // 创建一个新根节点
        BPTreeNode *newRoot = createNode(false);
        newRoot->children[0] = root;

        // 分裂根节点
        if (root->isLeaf) {
            splitLeafChild(newRoot, 0, root);
        } else {
            splitNonLeafChild(newRoot, 0, root);
        }

        // 插入到新根节点的合适位置
        int i = (key > newRoot->keys[0]) ? 1 : 0;
        insertNonFull(newRoot->children[i], key);

        *rootRef = newRoot;
    } else {
        insertNonFull(root, key);
    }
}

// 释放 B+树节点
void freeBPTree(BPTreeNode *node) {
    if (!node) return;

    if (!node->isLeaf) {
        for (int i = 0; i <= node->n; i++) {
            freeBPTree(node->children[i]);
        }
    }

    free(node->keys);
    free(node->children);
    free(node);
}

// 主函数
int main() {
    BPTreeNode *root = NULL;

    // 插入数据
    insert(&root, 10);
    insert(&root, 20);
    insert(&root, 5);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 30);
    insert(&root, 7);
    insert(&root, 17);

    // 遍历 B+树
    printf("Traversal of the B+ Tree:\n");
    traverse(root);

    // 搜索键值
    int key = 6;
    printf("Searching for key %d in the B+ Tree...\n", key);
    BPTreeNode *result = search(root, key);
    if (result) {
        printf("Key %d found in the B+ Tree.\n", key);
    } else {
        printf("Key %d not found in the B+ Tree.\n", key);
    }

    // 释放 B+树
    freeBPTree(root);

    return 0;
}

C语言版本b+树

  1. 数据结构：

    • BPTreeNode 表示 B+树的节点，包含 keys、children 和 next（叶子节点链表指针）。
    • 支持叶子节点链表结构，优化范围查询。

  2. 主要功能：

    • 插入：自动处理节点分裂，支持叶子和非叶子节点分裂。
    • 搜索：递归搜索键值。
    • 遍历：从叶子节点链表输出所有键值。
    • 内存释放：递归释放所有节点，避免内存泄漏。

  3. 健壮性：

    • 检查内存分配是否成功，失败时终止程序。
    • 处理空树和根节点分裂等边界情况。

  4. 测试功能：

    • 插入一组数据，输出所有键值。
    • 搜索特定键值，输出是否找到。

 

 


http://www.kler.cn/a/455560.html

相关文章：

  • 【汇编】关于函数调用过程的若干问题
  • 音视频入门基础：MPEG2-PS专题（2）——使用FFmpeg命令生成ps文件
  • 【信息系统项目管理师】高分论文：论信息系统项目的资源管理（移动警务通系统）
  • uni-app开发-识图小程序-识图功能
  • C# OpenCV机器视觉:凸包检测
  • TF-IDF（Term Frequency-Inverse Document Frequency）详解：原理和python实现（中英双语）
  • HarmonyOS：删除多层ForEach循环渲染的复杂数据而导致的一系列问题
  • 基于python+Django+mysql鲜花水果销售商城网站系统设计与实现
  • 【hackmyvm】hacked靶机wp
  • Redis——数据过期策略
  • 分析redis双检锁
  • Linux增加回收站功能
  • springcloud篇1（微服务技术栈、服务拆分与远程调用、Eureka、Nacos）
  • 【前端】整理部分语法 支持的最低版本浏览器
  • 从 x86 到 ARM64：CPU 架构的进化与未来
  • Java开发框架大比拼：若依、Jeesite与jeecgBoot的深度对比与实战案例分析
  • 助你通过AI培训师中级考试的目录索引
  • 【ANGULAR网站开发】初始环境搭建
  • Chromium GN 目标指南 - view_example 表单示例 (八)
  • elasticsearch安全认证
  • R 和 Origin 完成细菌 OTU 表、土壤理化性质数据的微生物 Beta 多样性分析
  • 多因子模型连载
  • 零信任安全体系研究
  • 抖音生活服务商系统源码怎么搭建？
  • gesp(二级)（16）洛谷：B4037：[GESP202409 二级] 小杨的 N 字矩阵
  • 面试场景题系列：设计限流器