Как получить размер бинарного дерева?

Question

У меня очень простая двоичная древовидная структура, что-то вроде:

struct nmbintree_s {
    unsigned int size;
    int (*cmp)(const void *e1, const void *e2);
    void (*destructor)(void *data);
    nmbintree_node *root;
};

struct nmbintree_node_s {
    void *data;
    struct nmbintree_node_s *right;
    struct nmbintree_node_s *left;
};

Иногда мне нужно извлечь «дерево» из другого, и мне нужно получить размер для «извлеченного дерева», чтобы обновить размер исходного «дерева».

Я думал о двух подходах:

1) Использование рекурсивной функции, что-то вроде:

unsigned int nmbintree_size(struct nmbintree_node* node) {
  if (node==NULL) {
    return(0);
  } 
  return( nmbintree_size(node->left) + nmbintree_size(node->right) + 1 );
} 

2) Предварительный / обратный / обратный обход, выполненный итерационным (с использованием стека / очереди) + подсчет узлов

Какой подход, по вашему мнению, является более «стойким к сбоям памяти» / быстродействующим?

Любые другие предложения / советы?

ПРИМЕЧАНИЕ : Вероятно, я собираюсь использовать эту реализацию в будущем для своих небольших проектов. Так что я не хочу неожиданно потерпеть неудачу :).

Answer 1

Просто используйте рекурсивную функцию. Это просто реализовать таким образом, и нет необходимости делать его более сложным.

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

Если вы позже обнаружите, что значительное количество времени в вашей программе тратится на вычисление размеров деревьев (что, вероятно, не произойдет), вы все равно можете начать профилировать вещи и попробовать, как работает ручная реализация. Но тогда также может быть лучше сделать алгоритмические улучшения, такие как отслеживание изменений размера в процессе извлечения.

Answer 2

Если ваше «очень простое» двоичное дерево не сбалансировано, то рекурсивная опция страшна из-за глубины неограниченной рекурсии. Итеративные обходы имеют ту же проблему времени, но, по крайней мере, стек / очередь находятся под вашим контролем, поэтому вам не нужно аварийно завершать работу. Фактически, с флагами и дополнительным указателем на каждом узле и эксклюзивным доступом, вы можете выполнять итерацию по своему дереву без какого-либо стека / очереди вообще.

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

Если дерево сбалансировано, тогда оно не очень глубокое. Все параметры защищены от сбоев, а производительность оценивается по измерениям :-) Но на основе структуры вашего узла дерева, либо она не сбалансирована, либо вы играете в глупые игры с флагами в младших битах указателей ...

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

Answer 3

Насколько велико это дерево, и как часто вам нужно знать его размер? Как уже говорилось, рекурсивная функция является самой простой и, вероятно, самой быстрой.

Если дерево похоже на 10 ^ 3 узлов, и вы изменяете его 10 ^ 3 раза в секунду, тогда вы можете просто сохранить внешний счетчик, который уменьшается при удалении узла, и увеличивается при добавлении одного. Кроме этого, просто лучше всего.

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