ماذا يعني rank في الخوارزميات وهياكل البيانات؟ شرح مبسّط مع أمثلة

باختصار: كلمة rank (الرُّتبة) في الخوارزميات وهياكل البيانات تعني موقع عنصر ما لو رتّبنا المجموعة كلها، أو بتعبير أدق: عدد العناصر الأصغر منه. فإذا كان لديك المصفوفة [10, 30, 20, 50] ورتّبتها تصاعديًا، تصبح رتبة العدد 20 هي 1 (يسبقه عنصر أصغر واحد فقط، وهو 10)، ورتبة العدد 50 هي 3. هذا هو المعنى الأساسي الذي يبحث عنه معظم الناس، وبقية المقال يوضح المعاني الأخرى المتقاربة حتى لا تختلط عليك.

التعريف الدقيق: الرتبة = عدد العناصر الأصغر

في الأدبيات الأكاديمية تُعرَّف الرتبة على أنها:

rank(x) = عدد العناصر في المجموعة التي قيمتها أصغر من x.

لاحظ نقطتين مهمتين:

• البداية من صفر أم من واحد؟ بعض المراجع تجعل أصغر عنصر رتبته 0، وبعضها يجعلها 1. لا يوجد "صحيح مطلق"، لكن يجب أن تثبت على اتفاقية واحدة داخل الكود، وهذا مصدر أخطاء شائع.
• العنصر الأوسط (median) هو ببساطة العنصر الذي رتبته n/2. لهذا يرتبط مفهوم الرتبة ارتباطًا مباشرًا بما يُسمى الإحصاء الترتيبي (Order Statistic): العنصر ذو الرتبة k هو "k-th smallest".

المعاني المختلفة لكلمة rank

المشكلة أن الكلمة نفسها تظهر في سياقات متعددة، وخلطها يسبب لبسًا حقيقيًا:

السياق	ما يعنيه rank هنا
الإحصاء الترتيبي / الفرز	ترتيب العنصر في المجموعة المرتّبة (عدد الأصغر منه)
هياكل بيانات البت (Bit Vectors)	rank(i) = عدد الآحاد (1) حتى الموضع i
شجرة الإحصاء الترتيبي	رتبة عقدة داخل الشجرة، تُحسب من أحجام الشجيرات الفرعية
PageRank (محركات البحث)	مصطلح مختلف تمامًا: ترتيب أهمية صفحة ويب، وليس رتبة عنصر في مصفوفة
رتبة المصفوفة (Matrix Rank)	مفهوم من الجبر الخطي (عدد الصفوف المستقلة خطيًا)، لا علاقة له بهياكل البيانات

خذ العمودين الأخيرين بحذر: إن جاءتك كلمة "rank" في سياق SEO أو الجبر الخطي فهي شيء آخر كليًا رغم تشابه الاسم.

rank مقابل select: زوج لا ينفصل

في هياكل البيانات المتقدمة (خصوصًا الهياكل المُوجَزة/Succinct) تأتي rank دائمًا مع توأمها select، وهما عمليتان عكسيتان:

العملية	السؤال الذي تجيب عنه	مثال
rank(x)	كم عنصرًا يسبق x؟	ما رتبة القيمة 20؟
select(k)	ما العنصر الذي رتبته k؟	ما القيمة صاحبة الرتبة 3؟

فهم هذه الثنائية يفتح لك الباب لهياكل مثل Wavelet Tree وFM-Index المستخدمة في ضغط النصوص والبحث في الجينوم.

كيف تحسب الرتبة عمليًا؟

الطريقة تعتمد على شكل بياناتك:

1. مصفوفة غير مرتّبة، حساب لمرة واحدة: مرّ على العناصر واعدُد كم عنصرًا أصغر من هدفك. التعقيد O(n)، مناسب إن كنت تحتاج رتبة عنصر واحد فقط.
2. مصفوفة مرتّبة: استخدم البحث الثنائي (Binary Search) لإيجاد موقع العنصر، فتحصل على الرتبة في O(log n).
3. بيانات تتغير باستمرار (إضافة/حذف مع استعلامات رتبة): هنا لا تكفي المصفوفة. استخدم شجرة الإحصاء الترتيبي (شجرة توازن مثل AVL أو الحمراء-السوداء، مع تخزين حجم كل شجيرة فرعية في عقدتها). هذا يعطيك rank وselect معًا في O(log n) لكل عملية.
4. البحث عن العنصر ذي الرتبة k دون فرز كامل: استخدم خوارزمية Quickselect بمتوسط تعقيد O(n)، وهي أسرع من الفرز الكامل الذي يكلّف O(n log n).

نصيحة عملية وخطأ شائع

الخطأ الأكثر تكرارًا هو الخلط بين الرتبة والفهرس (index). الفهرس هو موضع العنصر في الترتيب الحالي للمصفوفة (قبل الفرز)، أما الرتبة فهي موضعه بعد الفرز حسب القيمة. عنصر فهرسه 0 قد تكون رتبته الأخيرة إن كان أكبر القيم.

خطأ ثانٍ شائع: عند وجود قيم مكررة، يجب أن تقرر مسبقًا هل تحسب الرتبة بـ"أصغر تمامًا" (strictly less) أم "أصغر أو يساوي". هذا القرار يغيّر النتيجة، ويجب توثيقه في الكود لتجنّب أخطاء يصعب تتبّعها لاحقًا.

الأسئلة الشائعة

هل rank هو نفسه index (الفهرس)؟ لا. الفهرس موضع فيزيائي في المصفوفة كما هي، والرتبة موضع منطقي بعد الترتيب حسب القيمة. يتطابقان فقط إذا كانت المصفوفة مرتّبة أصلًا.

ما أسرع طريقة لإيجاد العنصر صاحب الرتبة k؟ خوارزمية Quickselect بمتوسط O(n)، وهي أكفأ من فرز المصفوفة كاملة إذا كنت تريد عنصرًا واحدًا فقط (مثل الوسيط).

هل PageRank من محركات البحث له علاقة بهذا المفهوم؟ لا. PageRank خوارزمية لترتيب أهمية صفحات الويب اعتمادًا على الروابط، والتشابه في الاسم فقط لا في المعنى.

لماذا نحتاج شجرة خاصة بدل المصفوفة المرتّبة؟ لأن المصفوفة المرتّبة تكلّف O(n) عند كل إدراج أو حذف للحفاظ على الترتيب. شجرة الإحصاء الترتيبي تنفّذ الإدراج والحذف واستعلام الرتبة جميعها في O(log n)، وهو ما تحتاجه البيانات المتغيّرة باستمرار.