2-3-4 члена узла дерева

Question

2-3-4 члена узла дерева

Я был бы очень признателен за разъяснение в 2-3-4 деревьях … Предположим, у вас есть дерево, определенное следующим образом:


class N234{  //node class
public:
int firstData, secondData, thirdData;
N234 *firstChild,*secondChild,*thirdChild,*fourthChild,*parent;
};

class T234{  //tree with root node
public:
T234(){
this->root->parent=NULL;
this->root->firstChild=NULL;
this->root->secondChild=NULL;
this->root->thirdChild=NULL;
this->root->fourthChild=NULL;
}
private:
N234* root;
};

Мой вопрос на самом деле, как я узнаю, заполнен ли узел (имеет все три значения в нем), когда его переменные (firstData, secondData, thirdData) уже имеют какое-то значение в них, как?

например:
корень: | 4 | левый потомок корня: | 1,2 |
правый ребенок корня | 7,9 |

Здесь корень имеет одно значение (4). Мой вопрос заключается в том, как мы узнаем, что оно на самом деле имеет одно значение, поскольку все его другие переменные (secondData, thirdData) имеют некоторое значение (даже если это мусор) .. Заранее спасибо!

0

2-3-4-tree c++data-structures

Решение

Другие решения

Вам необходимо добавить переменную-член "общее количество ключей" в ваш класс узла

class N234{  //node class
public:

N234(int x) : totalItems(1) { keys[0] = x; children[0] = 0; }

N234(int x, int y) : totalItems(2) {keys[0] = x; keys[1] = y; children[0] = 0;}

N234(int x, int y, int z) : totalItems(3) { keys[0] = x; keys[1] = y;
keys[2] = z; children[0] = 0; }

bool isLeaf() { return child[0] == 0 ? true : false }
bool isFourNode() { return totalItems == 4 : true : false}
private:
totalItems;
int keys[3];
N234 *children[4];
};

Затем проверьте, если это 4-узел.

0

Источник

Accepted Answer

Если бы у нас были только внутренние узлы, о которых стоило бы беспокоиться, самым простым способом было бы взглянуть на дочерние указатели:

Если thirdChild равно нулю, то узел является 2-узлом, поэтому он имеет только одно значимое значение (firstData), и остальное (secondData, thirdData) содержат мусор.

Если thirdChild не нуль, но fourthChild является нулем, то это 3-узел; первые две переменные данных содержат значимые значения.

Если все дочерние указатели ненулевые, то это 4-узел.

Единственная проблема с этим подходом состоит в том, что он требует, чтобы указатель был нулевым, если он на самом деле недействительным (например, thirdChild 2-узла), а не только неиспользованный. Но не все действительные дочерние указатели будут использоваться (например, firstChild 2-узла, который является листом).

Так что одним из решений является создайте узел, на который указывают все недействительные указатели, и который не используется никаким другим способом. В некотором смысле он действует как второй NULL, отличный от обычного.

Обратите внимание, что не имеет значения, какой тип указателя (недействительный или действительный, но неиспользуемый) указывает на NULL, а какой указывает на фальшивый узел. (Также обратите внимание, что вы можете использовать любое значение, отличное от NULL, для «второго NULL», это не обязательно должен быть адрес фактического узла, но вы должны быть уверены, что оно никогда не мог стать адрес фактического узла, и в любом случае это заставило бы меня нервничать при использовании такого подхода.)

0