حذف عنصر من شجرة KD ذات الأبعاد

Question

أرغب في تمديد فئة شجرة KD (2D) لتتمكن من إزالة العقد (النقاط). يجب إجراء هذه الإزالة دون الحاجة إلى إعادة بناء أقسام كبيرة من الشجرة. الخوارزمية الموصوفة في هذه منزلقات, ، على الشريحة 13 يبدو أن ما أنا بعد. ومع ذلك، أنا مشكلة في اتباع وصف "findmin ()" الموجودة على الشريحة 7، والتي تستخدم في خوارزمية إزالة العقدة.

أسئلة

1. ماذا يعني "أنا" في الفصل الأخير؟ (ربما هذا خطأ من قبل المؤلف، لأنه غير مرجما في مكان آخر؟)

2. ما هو بالضبط "أي ماكسي"؟ هل هو عمق تقسيم Hyperplane الذي نريد الحصول على الأقرب إليه؟

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

Answer 1

(1) أنا فكر في أنا هو الخطأ المطبعي؛ ليس لدي أي شيء من هذا القبيل في تنفيذي، ويبدو أنه يعمل بشكل جيد (الكلمات الأخيرة الشهيرة ..).

(2) أي ماكسي هي الطائرة التي تبحث عن الحد الأدنى منها. لذلك في بيانات ثنائية الأبعاد، سيكون سواء س أو ذ. على سبيل المثال للحصول على نقاط (20،40) و (40،20)، واحد هو الحد الأدنى في X والآخر في ذ. عند البدء في البحث عن عقدة بديلة، يجب أن تعرف أي طائرة تقسيم يجب عليك البحث فيها.

(3) الشريحة مكتوبة بغرابة قليلا. تريد العثور على القيمة الدنيا في الطائرة المناسبة. ربما سيؤدي ذلك إلى توضيح القليل (C #). تنفيذي هو لمجموعة بيانات باستخدام شرقيات الشمال كما x و y. Minaxis مجرد خدعة، حيث أن لدي طائرتين فقط.

bool winner = minAxis ? (left.Easting < right.Easting) : (left.Northing < right.Northing);
return winner ? left : right;

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

Answer 2

إذا كنت ترغب في حذف Nodea في شجرة KD معينة

(1) إذا كانت NODEA عقدة ورقة، فما عليك سوى جعله فارغا

(2) إذا كانت NODEA ليست عقدة ورقة

Assume nodeA split by x , you have two choice

1. find the largest nodeB (whose X is the largest) in left   
2. find the minimum nodeB (whoes X is the minimum) in right  (This pdf prefer it)

ملحوظة:

إذا وضعت NodeB يساوي NOTEA تحت Nodea.right، يجب عليك اختيار 2

إذا وضعت Nodeb يساوي NOTEA تحت NODEA.LEFT، يجب عليك اختيار 1

بعد ذلك، استبدل NODEA مع nodeb وحذف nodeb.