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

Question

Я был бы очень признателен за разъяснения в 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) имеют некоторое значение (даже если это мусор).. Заранее спасибо!

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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-узел.