最简单的B树:2-3树

2015年12月28日 原创
关键词: C++ 数据结构 算法 B树 变治法
摘要 2-3树是一颗平衡查找树,是最简单的B树。对2-3树进行插入,查找和删除的时间复杂度都是Θ(logn)的,因此很适合用来做数据量很大的查找和存储。数据库里主要运用的数据结构也是B树。

2-3树是一种可以包含两种类型节点的树:2节点和3节点。一个2节点只包含一个键K和两个子女:左子女作为一棵所有键都小于K的子树的根,而右子女作为一棵所有键都大于K的子树的根。(换句话说,一个2节点和一棵经典二叉查找树的节点类型是相同的。)一个3节点包含两个有序的键K1和K2(K1<K2)并且有3个子女。最左边的子女作为键值小于K1的子树的根,中间的子女作为键值位于K1和K2之间的子树的根,最右边的子女作为键值大于K2的子树的根(如图所示)。

2-3树的最后一个要求是,树中的所有叶子必须位于同一层,也就是说,一棵2-3树总是高度平衡的:对于每个叶子来说,从树的根到叶子的路径长度都是相同的。为了这个特性,我们付出的“代价”是允许查找树的一个节点包含不止一个键。

在2-3树中查找一个给定的键K是非常简单的。我们从根开始。如果根是一个2节点,我们就把它当做是一个二叉查找树来操作:如果K等于根的键值,算法停止;如果K小于或大于根的键值,我们分别在左子树或右子树中继续进行查找。如果根是一个3节点,在不超过2次比较之后,我们就能知道,是停止查找,还是应该在根的3棵子树的哪一棵中继续进行查找。

在2-3树中插入一个新建的做法如下。首先,除非空树,否则我们总是把一个新的键K插入到一个叶子里。通过查找K我们来确定一个合适的插入位置。如果找到的叶子是一个2节点,根据K是小于还是大于节点中原来的键,我们把K作为第一个键或者第二个键进行插入。如果叶子是一个3节点,我们把叶子分裂成两个节点:三个键(两个原来的键和一个新键)中最小的放到第一个叶子里,最大的键放到第二个叶子中,同时中间的键提升到原来叶子的父母中去(如果这个叶子恰好是树的根,我们就创建一个新的根来接纳这个中间键)。注意,中间键提升到父母中去可能会导致父母的溢出(如果它是一个3节点),并且因此会导致沿着该叶子的祖先链条发生多个节点的分裂。

下面是一个由列表9,5,8,3,2,4,7构造的一棵2-3树的过程:

就像所有的查找树一样,字典操作的效率依赖于树的高度。因此我们先来确定这个高度的上界。一个具有最少节点的高度为h的2-3树是一个全部由2节点构成的满树。所以,对于任何包含n个节点、高度为h的2-3树,有以下不等式:

n≥1+2+······+2h=2h+1-1

并且因此h≤log2(n+1)-1。换句话说,一个具有最多节点的高度为h的2-3树是一棵全部由3节点构成的满树,每个节点都包含两个键和三个子女。所以,对于任何n个节点的2-3树,

n≤2x1+2x3+······+2x3h=2(1+3+······+3h)=3h+1-1

并且因此h≥log3(n+1)-1。所以高度h的上下界是:log3(n+1)-1≤h≤log2(n+1)-1

这意味着,无论在最差情况还是在平均情况下,查找、插入和删除的时间效率都属于Θ(logn)。2-3树有一种重要的一般性形式,就是所谓的B树。

下面的代码从input.txt中读取了数据并构造了一个2-3树,然后在2-3树中搜索特定的值,并显示出搜索结果(耗费次数)。

2-3tree.cpp

// 2-3Tree.cpp : 定义控制台应用程序的入口点。
//

#include<iostream>
#include<queue>
#include<fstream>
using namespace std;
int inf = 1000000;
int nodeCurrLayer = 0;
class Node{
public:
    int keys[4];
    int keyIndex = 0;
    Node* children[4];
    Node* parent;
    int childIndex = 0;
    int inParentIndex = 0;
    int layer = 0;
    bool isLeaf = true;
    Node(int key = 0, Node* parent = NULL, int inParentIndex = 0) :parent(parent), inParentIndex(inParentIndex){
        keys[0] = keys[1] = keys[2] = keys[3] = inf;
        children[0] = children[1] = children[2] = children[3] = NULL;
        if (key != 0) {
            keys[0] = key;
            keyIndex++;
        }
    }
};
Node* root = new Node;
void combineNode(Node* node, int key) {
    if (key < node->keys[0]) {
        node->keys[2] = node->keys[1];
        node->keys[1] = node->keys[0];
        node->keys[0] = key;
    }
    else if (key < node->keys[1]) {
        node->keys[2] = node->keys[1];
        node->keys[1] = key;
    }
    else {
        node->keys[2] = key;
    }
    node->keyIndex++;
    if (node->keyIndex == 3) {
        if (node->parent == NULL) {
            node->parent = new Node();
            root = node->parent;
            root->isLeaf = false;
            node->parent->children[0] = node;
            node->parent->childIndex++;
            node->parent->layer = ++nodeCurrLayer;
        }
        //combineNode(node->parent, node->keys[1]);
        //然后把剩下的两个键分开,放在parent的children中。
        if (node->inParentIndex == 0) {
            node->parent->children[node->inParentIndex + 3] = node->parent->children[node->inParentIndex + 2];
            if (node->parent->children[node->inParentIndex + 3] != NULL)
                node->parent->children[node->inParentIndex + 3]->inParentIndex = 3;
            node->parent->children[node->inParentIndex + 2] = node->parent->children[node->inParentIndex + 1];
            if (node->parent->children[node->inParentIndex + 2] != NULL)
                node->parent->children[node->inParentIndex + 2]->inParentIndex = 2;
        }
        else if (node->inParentIndex == 1) {
            node->parent->children[node->inParentIndex + 2] = node->parent->children[node->inParentIndex + 1];
            if (node->parent->children[node->inParentIndex + 2] != NULL)
                node->parent->children[node->inParentIndex + 2]->inParentIndex = 3;
        }
        //左边的叶子
        node->parent->children[node->inParentIndex] = new Node(node->keys[0], node->parent, node->inParentIndex);
        node->parent->children[node->inParentIndex]->layer = node->layer;
        //右边的叶子
        node->parent->children[node->inParentIndex + 1] = new Node(node->keys[2], node->parent, node->inParentIndex + 1);
        node->parent->children[node->inParentIndex + 1]->layer = node->layer;
        node->parent->childIndex++;
        combineNode(node->parent, node->keys[1]);
        if (node->childIndex == 4) {
            node->parent->children[node->inParentIndex]->children[0] = node->children[0];
            if (node->children[0] != NULL) {
                node->children[0]->inParentIndex = 0;
                node->children[0]->parent = node->parent->children[node->inParentIndex];
            }
            node->parent->children[node->inParentIndex]->children[1] = node->children[1];
            if (node->children[1] != NULL) {
                node->children[1]->inParentIndex = 1;
                node->children[1]->parent = node->parent->children[node->inParentIndex];
            }
            node->parent->children[node->inParentIndex + 1]->children[0] = node->children[2];
            node->parent->children[node->inParentIndex]->childIndex += 2;
            if (node->children[2] != NULL) {
                node->children[2]->inParentIndex = 0;
                node->children[2]->parent = node->parent->children[node->inParentIndex + 1];
            }
            node->parent->children[node->inParentIndex + 1]->children[1] = node->children[3];
            if (node->children[3] != NULL) {
                node->children[3]->parent = node->parent->children[node->inParentIndex + 1];
                node->children[3]->inParentIndex = 1;
            }
            node->parent->children[node->inParentIndex + 1]->childIndex += 2;
            node->parent->children[node->inParentIndex]->isLeaf = false;
            node->parent->children[node->inParentIndex + 1]->isLeaf = false;

        }
        node->parent->isLeaf = false;
        node = NULL;
    }

}

void addNode(Node* node, int num) {
    //如果是空树
    if (node->keyIndex == 0) {
        node->keys[node->keyIndex++] = num;
        return;
    }
    if (!node->isLeaf) {
        //如果不是叶子节点,则继续寻找
        if (num<node->keys[0]) {
            //最左边的节点
            addNode(node->children[0], num);
        }
        else if (num <node->keys[1]) {
            //中间(第二个节点)
            addNode(node->children[1], num);
        }
        else {
            //右边(第三个节点)
            addNode(node->children[2], num);
        }
        return;
    }
    if (node->isLeaf) {
        //如果是叶子节点
        combineNode(node, num);
    }


}
void gen23Tree(int* data, int n) {
    for (int i = 0; i < n; i++) {
        addNode(root, data[i]);
    }
}
void addDataTo23Tree(int data) {
    addNode(root, data);
}
int data[10000];
bool search(int target, Node* node, int* times) {
    (*times)++;
    if (target == node->keys[0] || target == node->keys[1]) return true;
    if (node->childIndex < 1) return false;
    if (target < node->keys[0]) return search(target, node->children[0], times);
    if (target < node->keys[1]) return search(target, node->children[1], times);
    if (target < node->keys[2]) return search(target, node->children[2], times);
}
int main() {
    bool running = true;
    //freopen("input.txt", "r", stdin);
    ifstream fin("input.txt");
    int num,pos = 0;
    while (fin >> num) {
        data[pos++] = num;
    }
    gen23Tree(data, pos);
    while (running) {
        cout << "输入你要查找的数据:" << endl;
        int target = 0;
        cin >> target;
        int times = 0;
        bool find = search(target, root, &times);
        if (find) {
            cout << "查找到了该数据,共用了" << times << "步" << endl;
        }
        else {
            cout << "没有该数据,共用了" << times << "步" << endl;
        }
    }
    return 0;
}
input.txt

9  5  8  3  2  4  7  12  11 13 14 20 43 65 78 1 99 80 60 70 77 100 200 300 150 250 999 111 222 333 444 555 666 777 888

运行结果: