рекурсия — сбалансированное дерево C ++ / порядок вызовов в рекурсивной функции

Question

рекурсия — сбалансированное дерево C ++ / порядок вызовов в рекурсивной функции

Я сейчас пишу реализацию дерева CART, которое является двоичным деревом, используемым в машинном обучении. Он обучается рекурсивно, как показано в следующем коде:

struct Node
{
Node * parent;
Node * left;
Node * right;
};

void train(Node* node)
{
//perform training algorithm on node

train(node->left);
train(node->right);
}

Теперь предположим, что я ограничиваю количество итераций отслеживания выбранным значением, скажем, nTraining=4,

Затем, разворачивая рекурсивные вызовы функций, я ожидаю, что только left ветвь развита. Итак, первые четыре звонка:

    train(node);
train(node->left);
train(node->left->left);
train(node->left->left->left);
//only now train(node->left->left->right); would follow

что дает совершенно несбалансированное дерево, похожее на

          O
/ \
O   O
/ \
O   O
/ \
O   O
/ \
O   O

Кто-нибудь может предложить, каким образом я могу в дальнейшем использовать рекурсивный подход к обучению и все же получить сбалансированное дерево?

0

c++machine-learning recursion tree tree-balancing

Решение

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

Других решений пока нет …

Источник

Accepted Answer

Я бы сказал, не используйте рекурсию (DFS). Используйте BFS, то есть очередь вместо этого, чтобы дерево проходило уровень за уровнем:

std::queue<Node*> q;
Node* root;
q.push(root);
for (int i = 0; i < nTraining; ++i) {
Node* node = q.front();
q.pop();
train(node);
q.push(node->left);
q.push(node->right);
}

2