العثور على الحد الأدنى لقيمة الشجرة 2-3-4

Question

أولا، هذا السؤال ليس واجبا منزليا.أقرأ حاليًا كتاب "هياكل البيانات والخوارزميات الإصدار الثاني" لروبرت لافور.في الفصل العاشر، تعلمنا عن 2-3-4 أشجار ثم طلبنا كتابة طريقة للعثور على الحد الأدنى من القيمة في الشجرة المذكورة.

من وجهة نظر المفهوم، أفهم أين توجد القيمة الدنيا.إنه مجرد عنصر البيانات الموجود على اليسار في الورقة.

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

  public long minValue() {
   Node curNode = root; // current node = root
   long min = curNode.getMin();
   while(!curNode.isLeaf()) { // while current node is NOT a leaf
       curNode = getNextChild(curNode, min);
   } // end while
   return min;
} // end minValue()

ما يفعله هذا (على الأقل ما أعتقد أنه يجب أن يفعله هو إنشاء curNode يبدأ من العقدة الجذرية.ثم قم بإنشاء قيمة دقيقة تخزن curNode.getMin.يحصل getMin() فقط على القيمة الموجودة في المصفوفة عند الفهرس 0 (حيث يجب الاحتفاظ بأقل قيمة).بعد ذلك، على الرغم من أن العقدة الحالية ليست ورقة، فيجب علينا الانتقال إلى العقدة الفرعية التالية من النقطة الدنيا.بمجرد أن تصبح العقدة الحالية ورقة، يجب أن تُرجع الحد الأدنى من القيمة.

هذا لا يعمل رغم ذلك.هل لدى أي شخص فكرة عن كيفية تنفيذ ذلك؟تلميحات أو اقتراحات أو أي شيء آخر؟

يحرر:لرؤية كل فئة وكيفية تفاعلها، إليك روابط لكل فئة منفصلة.لقد وضعت طريقة القيمة الدنيا في صف Tree234 الخاص بي

DataItem, العقدة, شجرة234, وأين يتم تشغيل البرنامج Tree234App

Answer 1

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

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

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

أظن أنك بحاجة إلى القيام بشيء مثل:

  public long minValue() {
      Node curNode = root;
      long min = curNode.getMin();
      while(!curNode.isLeaf()) { // 
           curNode = getNextChild(curNode, min); //it's not immediately clear what min is doing here 
       } 
       //curNode is now the leftmost non-leaf element in the tree
       min = curNode.getMin();
       return min;

لاحظ أن التغيير الوحيد الذي قمت به هو إدراج السطر الموجود أعلى بيان الإرجاع، والذي يتم إعادة تعيينه min إلى الحد الأدنى للقيمة المرتبطة بالعنصر الموجود في أقصى اليسار في الشجرة.

Answer 2

لمزيد من الكفاءة، لاحظ أنك لا تحتاج إلى الاتصال getNextChild(curNode, min), نظرًا لأن العناصر الموجودة في العقدة يتم فرزها دائمًا بترتيب تصاعدي في شجرة 2-3-4 ويكون العنصر الأصغر دائمًا في الفهرس 0.إعلان الحد الأدنى ليس ضروريًا أيضًا في البداية.لذلك يمكن أن يكون برنامجك مثل هذا:

public long minValue() {
    Node curNode = root;
    while (!curNode.isLeaf()) {
        curNode = curNode.getChild(0);
    }
    return curNode.getMin();
}