شجرة إحصاءات الترتيب

في علوم الحاسوب ، تعد شجرة الإحصاء الترتيبي نوعًا من أنواع شجرة البحث الثنائية (أو بشكل عام، شجرة B ^{[ 1 ]} ) التي تدعم عمليتين إضافيتين بالإضافة إلى الإدراج والبحث والحذف:

Select( i ) – ابحث عن أصغر عنصر رقم i المخزن في الشجرة
Rank( x ) – إيجاد رتبة العنصر x في الشجرة، أي فهرسه في قائمة العناصر المرتبة للشجرة

يمكن تنفيذ كلتا العمليتين في أسوأ الحالات الزمنية $O (log n)$ عند استخدام شجرة متوازنة ذاتيًا كهيكل بيانات أساسي.

تطبيق شجرة البحث المعززة

لتحويل شجرة بحث عادية إلى شجرة إحصائية ترتيبية، يجب أن تخزن عقد الشجرة قيمة إضافية، وهي حجم الشجرة الفرعية المتجذرة عند تلك العقدة (أي عدد العقد الموجودة أسفلها). يجب على جميع العمليات التي تُعدّل الشجرة تعديل هذه المعلومات للحفاظ على الثابت الذي

حجم[س] = حجم[يسار[س ]] + حجم[يمين[س ]] + 1

حيث size[nil] = 0بحسب التعريف. يمكن بعد ذلك تنفيذ Select على النحو التالي ^{[ 2 ]}^{: 342}

دالة Select(t, i) // تُعيد العنصر رقم i (بدءًا من العنصر رقم 1) من العناصر الموجودة في t p ← size[left[t ]] +1 إذا كان i = p أعد t وإلا إذا كان i < p، فأرجع Select(left[t], i) وإلا فأرجع Select(right[t], i - p)

يمكن تنفيذ الترتيب باستخدام الدالة الأصلية p[x]، كما في ^{[ 3 ]}^{: 342}

دالة Rank(T, x) // تُعيد موضع العنصر x (مفهرسًا بدءًا من 1) في القائمة الخطية المرتبة لعناصر الشجرة T r ← size[left[x ]] + 1 ص ← س طالما أن y ≠ T.root إذا كان y = right[p[y ]] r ← r + size[left[p[y ]] ] + 1 y ← p[y] إرجاع r

يمكن تعديل أشجار إحصاءات الترتيب بإضافة معلومات محاسبية للحفاظ على التوازن (على سبيل المثال، يمكن إضافة ارتفاع الشجرة للحصول على شجرة إحصاءات ترتيب AVL ، أو بت اللون للحصول على شجرة إحصاءات ترتيب أحمر-أسود ). بدلاً من ذلك، يمكن استخدام حقل الحجم مع آلية موازنة الأوزان دون أي تكلفة تخزين إضافية. ^{[ 4 ]}

مراجع

↑ "أشجار الفئة ب المعدودة" . 11 ديسمبر 2004. تم الاطلاع عليه في 18 يناير 2014 .
↑ كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001) [1990]. مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ISBN 0-262-03293-7.
^ كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009) [1990]. مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN 0-262-03384-4.
↑ رورا، سلفادور (2001). طريقة جديدة لموازنة أشجار البحث الثنائية . المؤتمر الدولي لبرمجة الحاسوب والتعلم الآلي (ICALP ). سلسلة محاضرات في علوم الحاسوب. المجلد 2076. الصفحات 469-480 . doi : 10.1007/3-540-48224-5_39 . ISBN 978-3-540-42287-7.

انظر أيضاً

خيانة ضمنية
يمكن استخدام شجرة القطاعات لاستعلامات العد، والترتيب هو استعلام عد، كما لو أن كل عقدة تخزن 1 ويتم جمعها من البداية إلى العنصر

روابط خارجية

شجرة إحصائيات الترتيب على موقع PineWiki، جامعة ييل.
تستخدم حزمة بايثون blist أشجار B الإحصائية المرتبة لتنفيذ القوائم مع إدراج سريع في مواقع عشوائية.
إضافة G++ إلى مكتبة STL: هياكل البيانات القائمة على السياسات . إضافة tree_order_statistics_node_update للحاويات المرتبة القائمة على الأشجار.

[1] "أشجار الفئة ب المعدودة" . 11 ديسمبر 2004. تم الاطلاع عليه في 18 يناير 2014 .

[2] كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001) [1990]. مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ISBN 0-262-03293-7.

[3] كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009) [1990]. مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN 0-262-03384-4.

[4] رورا، سلفادور (2001). طريقة جديدة لموازنة أشجار البحث الثنائية . المؤتمر الدولي لبرمجة الحاسوب والتعلم الآلي (ICALP ). سلسلة محاضرات في علوم الحاسوب. المجلد 2076. الصفحات 469-480 . doi : 10.1007/3-540-48224-5_39 . ISBN 978-3-540-42287-7.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]