مجلة زوران-منوعات-19-7-2021
في علوم الكمبيوتر ، و شجرة الانصهار هو نوع من بنية البيانات شجرة التي تطبق على مجموعة النقابي على ث صحيحة بت.
عند العمل على مجموعة من أزواج قيمة المفتاح n ، فإنه يستخدم مساحة O ( n ) ويقوم بإجراء عمليات البحث في وقت O (log w n ) ، وهو أسرع بشكل مقارب من شجرة البحث الثنائية التقليدية ذات التوازن الذاتي ، وأيضًا أفضل من شجرة van Emde Boas لقيم كبيرة من w .
يحقق هذه السرعة من خلال استغلال عمليات معينة في الوقت الثابت يمكن إجراؤها على كلمة آلة .
اخترعت الأشجار الانصهار في عام 1990 من قبل ميتشايل فريدمان و دان ويلارد .
تم إحراز العديد من التطورات منذ ورقة فريدمان وويلارد الأصلية عام 1990.
في عام 1999 تم توضيح كيفية تنفيذ أشجار الاندماج وفقًا لنموذج حساب تنتمي فيه جميع العمليات الأساسية للخوارزمية إلى AC 0 ، وهو نموذج من تعقيد الدائرة يسمح بعمليات الجمع والعمليات المنطقية على مستوى البت ولكنه لا يسمح بعمليات الضرب المستخدمة في خوارزمية شجرة الاندماج الأصلية.
تم اقتراح نسخة ديناميكية من أشجار الاندماج باستخدام جداول التجزئة في عام 1996 والتي تطابقت مع وقت تشغيل الهيكل الأصلي O (log w n ) في التوقعات.
نسخة ديناميكية أخرى باستخدام الشجرة الأسيةتم اقتراحه في عام 2007 والذي ينتج عنه أوقات تشغيل أسوأ حالة لـ O (log w n + log n ) لكل عملية.
يبقى مفتوحًا ما إذا كانت أشجار الاندماج الديناميكي يمكنها تحقيق O (log w n ) لكل عملية باحتمال كبير.
