Рекурсивный метод для определения глубины любого (не обязательно полного) двоичного дерева

Question

Я пытаюсь вычислить глубину любого (не обязательно полного) BST за O (log n) времени рекурсивно.

Вот алгоритм, который я придумал:

//max() - returns the max of two numbers
int depth(root)
{
    if(root->left==NULL && root->right==NULL) //leaf
        return 0;
    else if(root->left!=NULL && root->right==NULL) //with right leaf
        return( max(depth(root->left),0)+1);
    else if(root->left==NULL && root->right!=NULL) //with left leaf
        return( max(0,depth(root->right)+1);
    else if(root->left->left==NULL && root->left->right==NULL && root->right->left==NULL&&root->right->right==NULL) // this a parent of two leaves
        return 1; 
    else// for the condition that this a parent of two sub roots
        return( max(depth(root->right),depth(root->left))+1);
}

Этот алгоритм подходит для расчета глубины за O (log n)?

Есть ли лучший способ?

Answer 1

Это O (n) время, так как вы можете пройти через каждый узел, делающий это. Вы можете выполнить поиск по бинарному дереву поиска в O (log n), но вы не можете найти глубину бинарного дерева в чем-либо меньшем, чем O (n), если вы не кешируете глубины, когда создаете его или делаете что-то подобное.

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

A идеальное двоичное дерево может иметь глубину, определенную в O (log n). Это означает, что каждый лист находится на одном уровне.

Завершено и сбалансированное двоичное дерево может иметь глубину приблизительно в O (log n) или в O (1), если число узлов известно , Однако это будет приблизительно (+/- 1 обычно).

Answer 2

Вы можете найти самый глубокий узел неизвестного, неуравновешенного дерева, посмотрев на каждый листовой узел, который требует обхода лота, как вы делаете - O (n).

Что касается "лучшего" способа, вы не можете сделать его меньшим Порядком, но вам не нужен такой сложный код для достижения вашего результата. Вот немного менее эффективная реализация (потому что она повторяется на один уровень глубже), которая гораздо более читабельна и более надежна (если вы передадите нулевой корневой указатель, она не выскочит):

int depth(root)
{
    if (root == NULL)
        return(0);

    return(1 + max(depth(root->left), depth(root->right)));
}

Answer 3

Единственный способ получить время выполнения O (log (n)) - это если вы исследуете только один путь, и единственный способ, которым вы сможете избежать изучения одного пути, - это если вы знаете, что дерево имеет форму высота, и это только в случае с полными бинарными деревьями, что конкретно указано в вашем вопросе.

Следовательно, не существует алгоритма O (log (n)), который бы определял глубину заданного двоичного дерева.

Answer 4

Проблема в C состоит в том, что стек функций не динамически распределяется в куче, поэтому в какой-то момент у нас не хватит места. Особенно, когда каждый рекурсивный вызов порождает две функции. Другими словами, если ваше дерево несколько сбалансировано, вы в конечном итоге вызовете функции log (N) ^ 2. Если вместо этого вы итерируете по левым ветвям и вернетесь к правым, стек будет расти не так быстро.

int
depth(struct bt *root, int dl)
{
        int dr, dmr;

        for(dmr=dr=dl; root != NULL; dl++){
                if((dr = depth(root->right, dl+1)) > dmr) 
                        dmr = dr;
                root = root->left;
        }
        return(dl > dmr ? dl : dmr);
}

Это способ I.E. Быстрая сортировка реализована во многих операционных системах:

http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/qsort.c?rev=1.10;content-type=text%2Fx-cvsweb-markup

Answer 5

int TreeDepthRec(Tree *pt){
  if(!*pt)
      return 0;
  int a = TreeDepthRec(&(*pt)->left);
  int b = TreeDepthRec(&(*pt)->right);
  return (a>b)? 1+a : 1+b;
}

Я думаю, что сравнение двух целочисленных переменных занимает меньше времени, чем вызов функции.

Answer 6

int maxDepth(BST *root)
{
    int ldepth=0,rdepth=0,maxdepth=0;

    if(root==NULL)
      return(0);

    ldepth=maxDepth(root->left);
    rdepth=maxDepth(root->right);

    maxdepth=MAX(ldepth,rdepth);
    return(maxdepth+1);   

}