التعامل مع التكرار مفاتيح داخل شجرة AVL

Question

أريد أن أجعل بلدي avl-tree دعم المفاتيح المكررة ولكن هناك مشكلة في السلوك الافتراضي لـ binary search tree مع التكرارات أن الدوران يمكن أن يجعل العقد ذات المفتاح المتساوي على اليسار ويمين الوالد.

على سبيل المثال ، عند إضافة ثلاث عقد مع مفتاح A سوف يتسبب في أن تكون الشجرة القيام بالتناوب لشيء من هذا القبيل:

   A
  /  \ 
 A    A

لذا فإن الحصول على جميع الإدخالات مع هذا المفتاح سيكون مشكلة ... والبحث في كلا الاتجاهين ليس جيدًا.

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

هل هناك أي طرق أخرى للتعامل مع التكرارات؟

Answer 1

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

للبحث عن مفتاح دون معرفة القيمة ، يمكنك بعد ذلك القيام بشيء مثل (الكود الزائف):

searchResult = myTree.SearchGreaterOrEqual(Key);
found = (searchResult != null) && (searchResult.Key == Key);

Answer 2

اطلب من كل عقدة تحتوي على عدد: إضافة التكرارات ستزيد العدد ، ستؤدي عمليات الإزالة إلى تقليل العدد إلا إذا كانت 1 ، وفي هذه الحالة ستتم إزالة العقدة بأكملها.