شجرة فنويك

شجرة فنويك أوالشجرة الثنائية المفهرسة هي بنية معطيات يمكن فيها القيام بتعديل عنصر وحساب مجاميع البوادئ في جدول من القيم الحسابية بطريقة فعالة.

اقترح بوريس ريابكوعام 1989 بنية المعطيات هذه، ثم أضاف إليها مجموعة من التنقيحات عام 1992، ولكنها حظيت بشهرة واسعة تحت اسم شجرة فنويك بعدما نشر بيتر فنويك شرحاً مفصلاً عنها في ورقة بحثية عام 1994.

بالمقارنة مع مصفوفة أحادية البعد تستطيع شجرة فنويك الموازنة بين عملية تعديل العنصر وحساب مجاميع البودائ بطريقة أفضل. في مصفوفة أحادية البعد مكونة من ${\displaystyle O(\log n)$

كيفية العمل

إن لشجرة فنويك بنيان شجري، وعلى الرغم من ذلك يتم تحقيق هذه الشجرة بشكل مضمّن في مصفوفة أحادية البعد بشكل مماثل لتحقيق شجرة الكومة. يتم حساب والد أوابن عنصر ما عن طريق التلاعب ببتات ذلك العنصر. يحتوي جميع عنصر من المصفوفة على مجموع مجال ما من الأعداد، وعن طريق إضافة مجاميع العقد الآباء وصولاً إلى جذر الشجرة يتم حساب مجموع جميع المجالات المتتالية وبالتالي نحصل على مجموع كافة العناصر وصولاً إلى ذلك العنصر. عند تعديل قيمة ما من المصفوفة، يتم تعديل جميع مجاميع المجالات المتضمنة ذلك العنصر من خلال القيام باجتياز عمودي للشجرة شبيه بالاجتياز المشروح سابقاً. يتم وضع مجاميع المجالات الجزئية ضمن عقد الشجرة المتنوعة بطريقة يمكن من القيام بحساب مجاميع البوادئ وتعديل عناصر المجموعة بنفس التعقيد الزمني(تعقيد حالةٍ أسواً ${\displaystyle O(\log n)$ ).

التحقيق

فيما يلي تحقيق لشجرة فنويك بلغة سي

#define LSB(i) ((i) & -(i)) // يقوم هذا الماكروبتصفير جميع البتات عدا البت الأقل أهمية

int A[SIZE];

int sum(int i) // i تعيد هذه الدالة مجموع كافة العناصر من صفر وحتى العنصر
{
    int sum = 0;
    while (i > 0) 
        sum += A[i], i -= LSB(i);
    return sum;
 
 
void add(int i, int k) // تقوم هذه الدالة بإضافة (كي) إلى العنصر (آي)
{
    while (i < SIZE) 
        A[i] += k, i += LSB(i);

المراجع

^ بوريس ريابكو(1989). "A fast on-line code" (PDF). Soviet Math. Dokl. 39 (3): 533–537. مؤرشف من الأصل (PDF) في 17 يوليو2019.
^ بوريس ريابكو(1992). "A fast on-line adaptive code" (PDF). IEEE Trans.on Inform.Theory. 28 (1): 1400–1404. مؤرشف من الأصل (PDF) في 14 يوليو2019.
^ بيتر فنويك (1994). "A new data structure for cumulative frequency tables". Software: Practice and Experience. 24 (3): 327–336. CiteSeerX = 10.1.1.14.8917 10.1.1.14.8917. doi:10.1002/spe.4380240306. مؤرشف من الأصل في 31 مايو2015.