обход по порядку в b-дереве (c ++) - PullRequest
Новая
       27

обход по порядку в b-дереве (c ++)

2 голосов
/ 02 декабря 2010

Я работаю над b-деревом (или это BTree?) Для класса, который я сейчас посещаю.У меня большая часть этого реализована правильно (я думаю).Тем не менее, я испытываю затруднения при нахождении обхода заказа.Вот моя основная функция: 

Tree<char, 5>* tree = new Tree<char, 5>();

char entries[] = {'a', 'g', 'f', 'b', 'k', 'd', 'h', 'm', 'j', 'e', 's', 
                  'i', 'r', 'x', 'c', 'l', 'n', 't', 'u', 'p' };

for (int i = 0; i < 20; i++) {
    tree->insert(entries[i]);
    cout << i << ":\t";
    tree->inorder();
    cout << endl;
}

Итак, я создаю btree с 5 путями, которое содержит символы.Я вставляю каждый из символов в дерево, а затем показываю обход inorder для каждой итерации в целях отладки.Вот вывод, который я получаю: 

0:  a
1:  ag
2:  afg
3:  abfg
4:  abffgk
5:  abdgfgk
6:  abdgfghk
7:  abdgfghkm
8:  abdgfghjjkm
9:  abdefghjjkm
10: abdefghjjkms
11: abdefghimjkms
12: abdefghimjkmrs
13: abdefghimjkmrrsx
14: abccdefghimjkmrrsx
15: abccdefghimjklmsrsx
16: abccdefghimjklmnrsx
17: abccdefghimjklmnrstx
18: abccdefghimjklmnrstux
19: abccdefghimjjklmmnprstux

Почти во всех из них некоторые символы дублируются, но не всегда между вставками, так что (мне) не кажется, что дублирующиеся данные получаютв. Кажется, в этом нет смысла, но вот мой метод inorder: 

template <class Record, int order>
void Tree<Record, order>::inorder()
{
    inorder(root);
}

template <class Record, int order>
void Tree<Record, order>::inorder(Node<Record, order> *current)
{
    for (int i = 0; i < current->count+1; i++) {
        if (current->branch[i])
            inorder(current->branch[i]);
        if (i < order-1 && current->data[i])
            cout << current->data[i];
    }
}

В моей реализации узла count - это число 'data' (каждый символ) в дереве.count + 1 будет означать, сколько ветвей выходит из узла для неконечных узлов.ветвь - это массив следующего нижнего набора узлов, данные - это массив символов.

Вот моя реализация Node: 

template <class Record, int order>
struct Node
{
    int count;
    Record data[order - 1];
    Node<Record, order>* branch[order];
    Node() : count(0) {}
};

Вот все, что используется для вставки: 

template <class Record, int order>
ErrorCode Tree<Record, order>::insert(const Record& new_entry)
{
    Record median;
    Node<Record, order> *right_branch, *new_root;
    ErrorCode result = push_down(root, new_entry, median, right_branch);

    if (result == overflow) {
        new_root = new Node<Record, order>();
        new_root->count = 1;
        new_root->data[0] = median;
        new_root->branch[0] = root;
        new_root->branch[1] = right_branch;
        root = new_root;
        result = success;
    }

    return result;
}

template <class Record, int order>
ErrorCode Tree<Record, order>::push_down(
                Node<Record, order> *current,
                const Record &new_entry,
                Record &median,
                Node<Record, order> *&right_branch)
{
    ErrorCode result;
    int position;

    if (current == NULL) {
        median = new_entry;
        right_branch = NULL;
        result = overflow;
    }
    else {
        if (search_node(current, new_entry, position) == success)
            result = duplicate_error;
        else {
            Record extra_entry;
            Node<Record, order> *extra_branch;
            result = push_down(current->branch[position], new_entry, 
                                extra_entry, extra_branch);
            if (result == overflow) {
                if (current->count < order - 1) {
                    result = success;
                    push_in(current, extra_entry, extra_branch, position);
                }
                else
                    split_node(current, extra_entry, extra_branch, position, 
                                right_branch, median);
            }
        }
    }

    return result;
}

template <class Record, int order>
void Tree<Record, order>::push_in(Node<Record, order> *current, 
                const Record &entry,
                Node<Record, order> *right_branch,
                int position)
{
    for (int i = current->count; i > position; i--) {
        current->data[i] = current->data[i-1];
        current->branch[i+1] = current->branch[i];
    }

    current->data[position] = entry;
    current->branch[position+1] = right_branch;
    current->count++;
}

Ответы [ 2 ]

1 голос
/ 03 декабря 2010

Хех, я думаю, что мы в одном классе. Я только что закончил свой, и я увидел проблему в вашем обходе inorder, а также с новым. В эту секунду, если: 

if (i < order-1 && current->data[i])
cout << current->data[i];

он делает это для порядка, а не для того, сколько данных в данный момент находится в узле, так что это будет немного больше Я изменил его на i<current->data, и теперь он работает просто отлично. ^^ b Только что закончил. Если это не работает для вас, извините. ^^;

1 голос
/ 02 декабря 2010

Ваша проблема в том, что ваш цикл for идет от 0 к счету (включительно), но ваш массив Node :: data не определен в data [count], он определен только до data [count-1], поэтому последний итерация вашего цикла this всегда получает мусор, который иногда может быть ненулевым и не отображаться, но в других случаях это могут быть случайные символы.

Вам нужен специальный кейс для кода, когда "i == order", например, так 

if (current->branch[i])
    inorder(current->branch[i]);
if (i < order-1 && current->data[i])
    cout << current->data[i];
...