خلع شجرة الإدراج

Question

من خلال بعض عمليات التقييم لشحن مهاراتي شجرة ثنائية، قررت تنفيذ شجرة Splay، كما هو موضح في ويكيبيديا: شجرة الجش.

شيء واحد لا أحصل عليه هو الجزء حول الإدراج.

انها تقول:

أولا، نحن نبحث X في شجرة Splay. إذا كان x غير موجود بالفعل، فلن نجد ذلك، لكن عقدة الوالدين ذ. ثانيا، نقوم بإجراء عملية Splay على y والتي ستنتقل ذ إلى جذر شجرة Splay. ثالثا، نحن أدخل العقدة الجديدة X كجذر بطريقة مناسبة. بهذه الطريقة إما Y اليسار أو اليمين الطفل الجذر الجديد x.

سؤالي هو هذا: يبدو النص أعلاه مقارنة بالمادة الأخرى مقارنة بالأمثلة الأخرى في المقالة، لماذا هذا؟ يبدو أن هناك بعض gotchas تركت هنا. على سبيل المثال، بعد عبيد Node y إلى الجذر، لا يمكنني استبدال الجذر بشكل أعمى ب X، و Tack y OnTo X إما الطفل المتبقي أو اليمين.

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

لدي هذه الشجرة:

           10
          /  \
         5    15
        / \    \
       1   6    20

وأريد إدراج 8. مع الوصف أعلاه، سأقوم بالعثور على العقدة المكونة من 6، وفي شجرة ثنائية عادية، ستتم إضافة 8 كطفل يمين في العقدة السادسة، ولكن هنا يجب أن أقوم أولا بالتعبئة 6 عقدة تصل إلى الجذر:

            6
           / \
          5   10
         /     \
        1       15
                 \
                  20

ثم أي من هذين اثنين مخطئين ببراعة:

          8                                  8
           \                                /
            6                              6
           / \                            / \
          5   10                         5   10
         /     \                        /     \
        1       15                     1       15
                 \                              \
                  20                             20

    6 is not greater than 8          10 is not less than 8

يبدو لي أن الطريقة الوحيدة للقيام الجيب أولا، ثم بإضافة القيمة الجديدة بشكل صحيح حيث أن الجذر يعني أنه لا بد لي من التحقق من المعايير التالية (لإضافة العقدة الجيدة مثل الطفل الأيسر من الجذر الجديد):

1. العقدة التي أجعلها الجذر أقل من الجذر الجديد (6 <8)
2. الطفل الصحيح في أقصى اليمين من العقدة التي صفعت إلى الجذر هو أقل من الجذر الجديد (20 8)

ومع ذلك، إذا كنت قد قمت بتقسيم العقدة، فستفيد، من خلال أخذ الطفل المناسب وإلحاقه بأنه الطفل المناسب للعقدة الجديدة، وأود أن أحصل على هذا:

                        8
                       / \
                      6   10
                     /     \
                    5       15
                   /         \
                  1           20

ولكن، هل هذا التغيير البسيط سوف يعطيني دائما شجرة صحيحة؟ أواجه صعوبة في الخروج بمثال، ولكن هل يمكن أن يؤدي ذلك إلى ما يلي:

• القيمة الجديدة التي أرغبت في إضافتها أعلى من الجذر المؤقت (العقدة التي أقوم بها إلى الجذر)، ولكن أيضا أعلى من أقصى اليسار للطفل المناسب للجذر المؤقت؟

بمعنى آخر. شجرة من شأنها أن تبدو أساسا مثل هذا بعد الجيب، ولكن قبل استبدال الجذر؟

                        10
                       /  \
                      5    15
                          /  \
                        11    20

وأريد أن أضيف 13، مما يجعل الشجرة الجديدة مثل هذا:

                        13
                       /  \
                     10    15
                     /    /  \
                    5   11    20  <-- 11, on the wrong side of 13

أو هل يمكن أن يحدث هذا أبدا؟

سؤالي الثاني هو: لن يكون من الأسهل بكثير إعادة كتابة العملية كما يلي:

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

التركيز الألغام لإظهار ما تغير.

Answer 1

لا أرى كيف يمكن أن تحدث المشكلة التي تصفها. إذا كنت ترغب في إدراج 13 في هذه الشجرة، فعليك أولا العثور على المكان الذي سيكون عليه:

                    10
                   /  \
                  5    15
                      /  \
                    11    20

من 10، تذهب إلى اليمين، من 15 تذهب إلى اليسار، من 11 تذهب إلى اليمين ... ثم ليس لديك المزيد من العناصر. إذا كان 13 كان في الشجرة، فكن قد وجدنا ذلك كطفل يمين من 11. لذلك وفقا للحكم، فإننا نقوم بعملية Splay في 11 والتي ستنتقل 11 إلى جذر شجرة Splay:

                    11
                   /  \
                  10   15
                 /       \
                5         20

ثم نضيف 13 كجذر جديد، مع 11 كطفل يساري:

                    13
                   /  \
                  11   15
                 /       \
                10        20
               /
              5

الآن لا توجد مشكلة.

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

هذا يبدو لي وكأنه سيعمل أيضا، ولكن إذا كنت أنت، فسأحاول فقط تنفيذ الإصدار كما هو موضح في ويكيبيديا منذ اختبار الكثير من الناس أنه تم توثيقه جيدا بالفعل.

Answer 2

"شجرة Splay" جعلني على الفور تذكر مقال في كوج قرأت منذ فترة، قد تجد بعض البصيرة هناك: تنفيذ شجرة Splay في C ++.

ثالثا، نحن أدخل العقدة الجديدة X كجذر بطريقة مناسبة. بهذه الطريقة إما Y اليسار أو اليمين الطفل الجذر الجديد x.

نعم، ولكن هذا الجذر الجديد X يجب أن يكون لديك طفلان، ولهذا السبب قد يبدو أن هذه الجملة مربكة.

Answer 3

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