كيفية تحويل شجرة ثنائية إلى شجرة البحث الثنائية في مكانها ، أي لا يمكننا استخدام أي مساحة إضافية

Question

كيفية تحويل شجرة ثنائية إلى شجرة البحث الثنائية في مكانها ، أي لا يمكننا استخدام أي مساحة إضافية.

Answer 1

لا تعطي الكثير لتستمر ، ولكن إذا كان الشرط هو ما أعتقد أنه ، لديك شجرة ثنائية تم إنشاؤها بالفعل وتجلس في الذاكرة ، ولكن لا يتم فرزها (الطريقة التي تريد فرزها ، على أي حال).

أفترض أن العقد الشجرة تبدو مثل

struct tree_node {
    struct tree_node * left;
    struct tree_node * right;
    data_t data;
};

أفترض أيضًا أنه يمكنك قراءة C.

على الرغم من أننا يمكن أن نجلس حولنا نتساءل عن سبب إنشاء هذه الشجرة من أي وقت مضى دون أن يتم إنشاؤه بترتيب فرز لا يفينا بأي شيء ، لذلك سأتجاهلها وأتعامل مع فرزها.

شرط عدم استخدام أي مساحة إضافية أمر غريب. مؤقتا سيكون هناك مساحة إضافية ، إذا فقط على المكدس. سأفترض أن هذا يعني أن استدعاء Malloc أو شيء من هذا القبيل وأيضًا أن الشجرة الناتجة لا يجب أن تستخدم ذاكرة أكثر من الشجرة الأصلية غير المصنفة.

الحل الأول والأسهل هو القيام بعملية اجتياز مسبقة للشجرة غير المصنفة لإزالة كل عقدة من تلك الشجرة وإجراء إدخال فرز في شجرة جديدة. هذا هو (ن+نالسجل (ن)) ، وهو O (نسجل (ن)).

إذا لم يكن هذا ما يريدون وسيتعين عليك استخدام التناوب والأشياء ..... فهذا أمر فظيع!

اعتقدت أنه يمكنك القيام بذلك عن طريق القيام بنسخة فردية من نوع الكومة ، لكنني واجهت مشاكل. شيء آخر يتبادر إلى الذهن ، والذي سيكون بطيئًا بشكل فظيع ، أن يفعل نسخة غريبة من نوع الفقاعة على الشجرة.

يتم مقارنة كل هذه العقدة وربما تبديلها مع كل من أطفالها المباشرين (وبالتالي مع والدها) مرارًا وتكرارًا حتى تعبر الشجرة ولا تجد أي مقايضات مطلوبة. إن القيام بعمل شاكر (فرز الفقاعة الذي يتراوح من اليسار إلى اليمين واليمين إلى اليسار) من هذا سيكون على أفضل وجه ، وبعد التمريرة الأولية لن تحتاج إلى اجتياز الأشكال الفرعية التي لم تكن تبدو غير مرتبة فيما يتعلق بالوالد .

أنا متأكد من أن هذا algorthm كان يفكر فيه شخص آخر أمامي وله اسم رائع لا أعرفه ، أو أنه معيب بشكل أساسي بطريقة لا أراه.

إن الخروج بحسابات وقت التشغيل للاقتراح الثاني أمر معقد للغاية. في البداية اعتقدت أنه سيكون ببساطة O (n^2) ، مثل أنواع الفقاعات وشاكر ، لكن لا يمكنني إرضاء نفسي بأن تجنب اجتياز الشجرة الفرعية قد لا يفوز بما يكفي لجعله أفضل قليلاً من O (N^ 2). تحصل أنواع الفقاعة والشاكر بشكل أساسي على هذا التحسين أيضًا ، ولكن فقط في النهايات التي يحدث فيها الفرز الكلي مبكرًا ويمكنك تقطيع الحدود. مع إصدار الشجرة هذه ، تحصل على الفاكهة لتجنب القطع في منتصف المجموعة أيضًا. حسنًا ، كما قلت ، ربما يكون معيبًا قاتلاً.

Answer 2

تحويل شجرة ثنائية إلى قائمة مرتبطة بشكل مضاعف- يمكن القيام به في مكان في O (N)
ثم فرزه باستخدام دمج الفرز ، nlogn
تحويل القائمة مرة أخرى إلى شجرة - O (N)

حل Nlogn بسيط.

Answer 3

قم بتجاوز postorder ومن ذلك إنشاء شجرة بحث ثنائية.

struct Node * newroot = '\0';

struct Node* PostOrder(Struct Node* root)
{
      if(root != '\0')
      {
          PostOrder(root->left);
          PostOrder(root->right);
          insertBST(root, &newroot);
      }
}

insertBST(struct Node* node, struct Node** root)
{
   struct Node * temp, *temp1;
   if( root == '\0')
   {
      *root == node;
       node->left ==  '\0';
       node->right == '\0';
   }
   else
   {
       temp = *root;
       while( temp != '\0')
       {
           temp1= temp;
           if( temp->data > node->data)
               temp = temp->left;
           else
               temp = temp->right;
       }
       if(temp1->data > node->data)
       {
           temp1->left = node;
       }
       else
       {
           temp1->right = node;
       }
       node->left = node->right = '\0';
    }
}

Answer 4

هل تتبع الخوارزمية للوصول إلى الحل.

1) ابحث عن خلف الطلب دون استخدام أي مساحة.

Node InOrderSuccessor(Node node)
{ 
    if (node.right() != null) 
    { 
        node = node.right() 
        while (node.left() != null)  
            node = node.left() 
        return node 
    }
    else
    { 
        parent = node.getParent(); 
        while (parent != null && parent.right() == node)
       { 
            node = parent 
            parent = node.getParent() 
        } 
        return parent 
    } 
} 

2) افعل من أجل اجتياز دون استخدام الفضاء.

أ) ابحث عن العقدة الأولى من اجتياز inorder. يجب أن يترك معظم أطفال الشجرة إذا كان لديها ، أو يسار الطفل الأيمن الأول إذا كان لديه ، أو طفل يمين نفسه. ب) استخدام الخوارزمية أعلاه لمعرفة خلف inoder للعقدة الأولى. ج) كرر الخطوة 2 لجميع الخليفة التي تم إرجاعها.

استخدم أعلاه 2 خوارزمية وقم بالقيام بالتجاوز على الشجرة الثنائية دون استخدام مساحة إضافية. تشكيل شجرة البحث الثنائية عند القيام بالتجاوز. لكن التعقيد O(N2) الحالة الأسوأ.

Answer 5

حسنًا ، إذا كان هذا سؤالًا مقابلة ، فإن أول شيء كنت أخرجه (بدون تفكير فعلي) هو: تكرار الثنائي بأكمله بشكل متكرر وأجد أصغر عنصر. أخرجها من الشجرة الثنائية. الآن ، كرر العملية التي تكررها الشجرة بأكملها والعثور على أصغر عنصر ، وأضفها كوالد للعنصر الأخير الموجود (مع أن العنصر السابق يصبح الطفل الأيسر للعقدة الجديدة). كرر عدة مرات حسب الضرورة حتى تصبح الشجرة الأصلية فارغة. في النهاية ، تُركت مع أسوأ شجرة ثنائية محتملة - قائمة مرتبطة. يشير مؤشرك إلى عقدة الجذر ، والتي هي أكبر عنصر.

هذه خوارزمية فظيعة في جميع الأوقات - o (n^2) وقت التشغيل مع أسوأ إخراج شجرة ثنائية ممكنة ، لكنها نقطة انطلاق لائقة قبل الخروج بشيء أفضل ولديك ميزة أن تكون قادرًا على كتابة الرمز في حوالي 20 خطًا على السبورة.

Answer 6

شجرة ثنائية عادة هو شجرة البحث الثنائية ، وفي هذه الحالة لا يلزم التحويل.

ربما تحتاج إلى توضيح بنية ما تقوم بتحويله منه. هل شجرة المصدر الخاصة بك غير متوازنة؟ أليس طلب من المفتاح الذي تريد البحث عنه؟ كيف وصلت إلى شجرة المصدر؟

Answer 7

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;

struct tree_node {
    struct tree_node * left;
    struct tree_node * right;
    data_t data;
};

        /* a bonsai-tree for testing */
struct tree_node nodes[10] =
{{ nodes+1, nodes+2, 1}
,{ nodes+3, nodes+4, 2}
,{ nodes+5, nodes+6, 3}
,{ nodes+7, nodes+8, 4}
,{ nodes+9, NULL, 5}
,{ NULL, NULL, 6}
,{ NULL, NULL, 7}
,{ NULL, NULL, 8}
,{ NULL, NULL, 9}
        };

struct tree_node * harvest(struct tree_node **hnd)
{
struct tree_node *ret;

while (ret = *hnd) {
        if (!ret->left && !ret->right) {
                *hnd = NULL;
                return ret;
                }
        if (!ret->left ) {
                *hnd = ret->right;
                ret->right = NULL;;
                return ret;
                }
        if (!ret->right) {
                *hnd = ret->left;
                ret->left = NULL;;
                return ret;
                }
        hnd = (rand() &1) ? &ret->left : &ret->right;
        }

return NULL;
}

void insert(struct tree_node **hnd, struct tree_node *this)
{
struct tree_node *ret;

while ((ret= *hnd)) {
        hnd = (this->data  < ret->data ) ? &ret->left : &ret->right;
        }
*hnd = this;
}

void show(struct tree_node *ptr, int indent)
{
if (!ptr) { printf("Null\n"); return; }

printf("Node(%d):\n", ptr->data);
printf("%*c=", indent, 'L');  show (ptr->left, indent+2);
printf("%*c=", indent, 'R');  show (ptr->right, indent+2);
}

int main(void)
{
struct tree_node *root, *this, *new=NULL;

for (root = &nodes[0]; this = harvest (&root);  ) {
        insert (&new, this);
        }

show (new, 0);
return 0;
}

Answer 8

struct Node
{
    int value;
    Node* left;
    Node* right;
};

void swap(int& l, int& r)
{
    int t = l;
    l = r;
    r = t;
}

void ConvertToBST(Node* n, Node** max)
{
    if (!n) return;

    // leaf node
    if (!n->left && !n->right)
    {
        *max = n;
        return;
    }

    Node *lmax = NULL, *rmax = NULL;
    ConvertToBST(n->left, &lmax);
    ConvertToBST(n->right, &rmax);

    bool swapped = false;
    if (lmax && n->value < lmax->value)
    {
        swap(n->value, lmax->value);
        swapped = true;
    }

    if (rmax && n->value > rmax->value)
    {
        swap(n->value, n->right->value);
        swapped = true;
    }

    *max = n;
    if (rmax && rmax->value > n->value) *max = rmax;

    // If either the left subtree or the right subtree has changed, convert the tree to BST again
    if (swapped) ConvertToBST(n, max);
}

Answer 9

قم بالتجاوز عبر الشجرة الثنائية وتخزين النتيجة. فرز النتيجة في ترتيب Actending تشكل شجرة البحث الثنائية عن طريق أخذ العنصر الأوسط من القائمة المصنفة كجذر (يمكن القيام بذلك باستخدام البحث الثنائي). لذلك نحصل على شجرة بحث ثنائية متوازنة.

Answer 10

كومة فرز الشجرة .. التعقيد nlogn ..