توليد الأولوية في بنية بيانات tap

Question

أنا أدرس بنية بيانات الخطوة.عند إدراج العقدة، تقوم الخطوة بشكل عشوائي بإنشاء أولوية العقدة.ولكن ماذا لو كانت الأولوية التي تم إنشاؤها لـ 69 عقدة هي 13 في الصورة أعلاه؟

يجب أن تكون أولوية الوالدين أعلى من أولوية الطفل.هل تتعارض سمة الشجرة الثنائية لـ treap مع سمة الكومة؟

أريد أن أعرف.شكرًا.

Answer 1

بافتراض أن لديك خطوة من صورتك بدون 69 عقدة وتريد إضافة عقدة (69، 13):
1. ينقسم الخطوة الحالية إلى درجتين L وR بواسطة المفتاح 69 (هنا ستكون كل الخطوات القديمة هي L)
2. يخلق المعالجة M بعقدة واحدة (69، 13)
3. دمج M مع L، ثم النتيجة مع R
بالنسبة لهذه الحالة، تصبح العقدة (69، 13) جذرًا جديدًا، وستكون الخطوة القديمة هي الفرع الفرعي المتبقي لها.

Answer 2

إذا كان العقدة 69 أولوية 13، فستكون أصل الشجرة والعقدة 31 ستكون طفلها الأيسر.سيكون أحفاد العقدة 31 كما هو الحال في الرسم البياني الخاص بك، باستثناء بالطبع للعقدة 69.

من الممكن دائما ترتيب Treap بحيث يحترم كلا من كومة خصائص البحث الثنائية.في الواقع، في حالة عدم وجود قيم متساوية أو أولويات متساوية، لا يوجد سوى ترتيب واحد ممكن.

المهمة العشوائية للأولويات تجعل من المحتمل أن تكون التريب متوازنة بشكل معقول.قد لا تكون متوازنة تماما، ولكن على الجانب الإيجابي في بناء Treap سريع وغير معقدة.