B-Tree Node Ссылки его «родитель»

Question

У меня есть очень простой вопрос об узлах B-Tree:

Является концептуально точной/правильно, что узел B-Tree ссылается его «родительский узел» или узел который содержит указатель на него?

Я изучал различные реализации B-Tree, и ни одна из них не включает ссылку на родительский узел в классе, который представляет узел.

Answer 1

См https://stuff.mit.edu/afs/sipb/user/gamadrid/nscript/btreep.h, который определяет узел как:

typedef struct node { 
    struct node *parent; 
    struct node *left; 
    struct node *right; 
} *btnode; 

не би-дерева, но принцип тот же.

Родительский указатель здесь как удобство, так же, как двойной связанный список позволяет вам перемещаться в обоих направлениях, не требуя, чтобы вы поддерживали стопку указателей на предыдущие узлы, как это сделал один-единственный список.

Без указателя родителя вы просто пересекаете дерево с помощью рекурсивной функции. Стек вызовов отслеживает, где вы находитесь в дереве.