بناء مصفوفة لاحقة من شجرة لاحقة.زيارة داخلية عندما يكون للعقدة أكثر من طفلين

Question

من الملاحظات:

ليس من الصعب ملاحظة مصفوفة اللاحقة $ exttt{SA}$ من النص $ exttt{T}$ يمكن الحصول عليها من شجرة لاحقة لها$ exttt{ST}$ عن طريق إجراء زيارة بالترتيب: $ exttt{SA}$;$ exttt{lcp}$.

كيف تقوم بالزيارة الداخلية عندما يكون للعقدة أكثر من طفلين؟

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

سا في مجموعة من المؤشرات لللاحقات، مرتبة بشكل معجمي.

lcp يحتوي على أطول بادئة مشتركة بين لاحقتين متتاليتين $ ext{suff}_{SA[i]} ext{ و } ext{suff}_{SA[i+1]}$.

يمثل \$ حرفًا أصغر من كل حرف آخر.

القيمة المرتبطة بكل عقدة هي طول البادئة المكتوبة حتى الآن.

تمثل الأوراق مؤشرات اللواحق.إذا كان T = الموز\$، فإن الورقة 3 تمثل nana\$ (T[3,7])

يوجد في الصورة ما يُفترض أن يكون شجرة لاحقة، ولكن أعتقد أن هناك خطأ حيث يجب فرز الحواف وفقًا للتسمية الخاصة بها ويجب أن تكون الورقة 7 ذات الحافة المسماة "\$" هي الورقة والحافة في أقصى اليسار.

عند محاكاة الخوارزمية، تقوم أولاً بزيارة العقدة 7 (باستخدام الإصدار الثابت من الشجرة)، ثم الجذر، وبذلك يكون لديك

SA = [7, ...]
lcp = [0, ...]

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

Answer 1

إذا كانت العقدة لديها $ل$ الأطفال، مع $l \geq 2$ أثناء الزيارة الداخلية عليك علاج الأول $l-1$ الأطفال كعقد يسرى، وعليك زيارة الوالدين المتعددين ($l-1$) مرات، والكتابة عدة مرات طول البادئة المكتوبة داخل مصفوفة LCP.

سيؤدي تطبيق هذا على الشجرة الموجودة في الصورة إلى الحصول على النتيجة الصحيحة:

SA = [7, 6, 4, 2, 1, 5, 3]
lcp = [0, 1, 3, 0, 0, 2]

مع الأخذ في الاعتبار أن الحافة التي تحمل العلامة "$" بالورقة 7 يجب أن تكون في أقصى اليسار.