تنفيذ IntervalTree DeleteNode جافا

Question

وأحتاج إلى IntervalTree أو تنفيذ RangeTree بلغة جافا، وأواجه صعوبة في العثور على واحد مع العمل دعم الحذف.

وهناك المدمج في واحدة على sun.jvm.hotspot.utilities.IntervalTree ، ولكن في طريقة deleteNode في الدول الطبقة المتفوقة RBTree:

/**
 * FIXME: this does not work properly yet for augmented red-black
 * trees since it doesn't update nodes. Need to figure out exactly
 * from which points we need to propagate updates upwards.
 */

ومحاولة حذف العقد من شجرة ينتهي رمي استثناء:

<اقتباس فقرة>   

ولم يتم تحديث نقطة النهاية ماكس عقدة ل   صحيح

ومدى صعوبة سيكون لتنفيذ بشكل صحيح وظائف delete في فئة فرعية من sun.jvm.hotspot.utilities.IntervalTree؟ أم أن هناك تنفيذ آخر الفاصل شجرة الذي ينفذ بالفعل هذا صحيح؟

وحاليا أنا مجرد محو الشجرة وإعادة ملء-في كل مرة هناك الحذف، وهي بعيدة عن المثالية (ملاحظة: وضع DEBUGGING = كاذبة في RBTree اسرعت الامور بشكل هائل)

.

Answer 1

وانتهى بي الأمر تعديل sun.jvm.hotspot.utilities.IntervalTree للحفاظ على مجموعة من العقد حذفها. عند القيام بعملية بحث، واستبعاد أي من البنود في هذه المجموعة. ليست مثالية، ولكن هذا أسهل بكثير من الحصول على "الحقيقي" الحذف العمل. وبمجرد أن يحصل على مجموعة حذف كبيرة جدا، I إعادة إنشاء شجرة.

Answer 2

هذا المشروع لديها تنفيذ RangeTree التي قد تكون أكثر فائدة لك. قد يكون حزم الشمس طيب للاستخدام السريع وقذرة، ولكن أنا لا أوصي بناء أي شيء مهم الاعتماد عليها. الشمس قد لا الحفاظ على استقرارها.

Answer 3

وأنا لا أعرف متطلباتك بالضبط ولكن شجرة الجزء غير ثابت قد عمل لك. إذا كان الأمر كذلك، إلقاء نظرة على تخطيط إدارة SW ، وتحديدا SegmentTree حزمة . فمن لديه ميزة إزالة التي تحتاج إليها.

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

Answer 4

وهناك تيار # التنفيذ بناء على شجرة AVL تضاف @ http://code.google.com/ ع / intervaltree / . الترجمة إلى جافا لا ينبغي أن يكون صعبا للغاية.

Answer 5

ولقد وجدت تنفيذ مفتوحة المصدر مع الحذف، لكنه neeeds بعض الجهد لجعلها تعمل بكامل طاقتها.

وانها وحدة من مشروع مفتوح المصدر الأكبر Gephi ، ولكن هنا في مصادر و <لأ href =" HTTP: //gephi.org/docs/toolkit/org/gephi/data/attributes/type/IntervalTree.html "يختلط =" نوفولو "> جافادوك . إذا كنت ترغب في جرة يمكنك تثبيت Gephi، وانها في:

/gephi/modules/org-gephi-data-attributes-api.jar

وطريقة حذف هناك، ويزيل كل فترات متداخلة مع فاصل المدخلات (بدلا من مجرد إدخال واحد). ومع ذلك وجدت في soruces أن هناك طرق خاصة التي تعمل على إزالة عقدة معينة (الذي يخزن فاصل واحد). أيضا طرق البحث خاصة تعود العقد.

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