شجرة ب في بنية البيانات: البحث والإدراج والحذف Operaمثال

ما هي الشجرة ب؟

شجرة ب عبارة عن بنية بيانات ذاتية التوازن تعتمد على مجموعة محددة من القواعد الخاصة بالحد الأدنىarchiإدخال وحذف البيانات بطريقة أسرع وفعالة في الذاكرة. ومن أجل تحقيق ذلك، اتبعwing يتم اتباع القواعد لإنشاء شجرة B.

شجرة B هي نوع خاص من الأشجار في بنية البيانات. في عام 1972، تم تقديم هذه الطريقة لأول مرة بواسطة ماكرايت، وأطلق عليها باير اسم شجرة البحث ذات الاتجاه المتوازن للارتفاع. يساعدك على الحفاظ على البيانات مرتبة ومتاحة لمختلف operaأشياء مثل الإدراج، حد ذاتهاarchiنانوغرام، والحذف في وقت أقل.

قواعد شجرة B

فيما يلي قواعد مهمة لإنشاء B_Tree

  • سيتم إنشاء جميع الأوراق على نفس المستوى.
  • يتم تحديد B-Tree بعدد من الدرجات، وهو ما يسمى أيضًا “النظام” (يتم تحديده بواسطة فاعل خارجي، مثل المبرمج)، ويشار إليه باسم
    m

    فصاعدا. قيمة ال

    m

    يعتمد على حجم الكتلة الموجودة على القرص الذي توجد عليه البياناتmariيقع.

  • سيكون للشجرة الفرعية اليسرى للعقدة قيم أقل من الجانب الأيمن من الشجرة الفرعية. وهذا يعني أنه يتم فرز العقد أيضًا بترتيب تصاعدي من اليسار إلى اليمين.
  • يتم حساب الحد الأقصى لعدد العقد الفرعية والعقدة الجذرية بالإضافة إلى العقد الفرعية الخاصة بها بواسطة هذه الصيغة:
    m – 1

    فمثلا:

    m = 4
    max keys: 4 – 1 = 3
    

قواعد شجرة B

  • يجب أن تحتوي كل عقدة، باستثناء الجذر، على الحد الأدنى من المفاتيح
    [m/2]-1

    فمثلا:

    m = 4
    min keys: 4/2-1 = 1
    
  • الحد الأقصى لعدد العقد الفرعية التي يمكن أن تحتوي عليها العقدة يساوي درجتها، وهي
    m
  • الحد الأدنى للأطفال الذي يمكن أن تحتوي عليه العقدة هو نصف الترتيب، وهو m/2 (يتم أخذ قيمة السقف).
  • يتم فرز جميع المفاتيح الموجودة في العقدة بترتيب متزايد.

لماذا نستخدم شجرة بي

فيما يلي أسباب استخدام B-Tree

  • يقلل من عدد القراءات التي تتم على القرص
  • يمكن تحسين أشجار B بسهولة لضبط حجمها (أي عدد العقد الفرعية) وفقًا لحجم القرص
  • إنها تقنية مصممة خصيصًا للتعامل مع كمية كبيرة من البيانات.
  • إنها خوارزمية مفيدة لقواعد البيانات وأنظمة الملفات.
  • خيار جيد للاختيار عندما يتعلق الأمر بقراءة وكتابة مجموعات كبيرة من البيانات

تاريخ شجرة B

  • يتم تخزين البيانات على القرص في كتل، وتسمى هذه البيانات، عند إدخالها إلى الذاكرة الرئيسية (أو ذاكرة الوصول العشوائي)، بنية البيانات.
  • في حالة وجود بيانات ضخمة، حد ذاتهاarchiيتطلب سجل واحد في القرص قراءة القرص بأكمله؛ يؤدي هذا إلى زيادة الوقت واستهلاك الذاكرة الرئيسية بسبب ارتفاع تردد الوصول إلى القرص وحجم البيانات.
  • للتغلب على ذلك، يتم إنشاء جداول الفهرس التي تحفظ مرجع السجل للسجلات بناءً على الكتل الموجودة فيها. وهذا يقلل بشكل كبير من استهلاك الوقت والذاكرة.
  • وبما أن لدينا بيانات ضخمة، يمكننا إنشاء جداول فهرس متعددة المستويات.
  • يمكن تصميم فهرس متعدد المستويات باستخدام B Tree للحفاظ على فرز البيانات بطريقة التوازن الذاتي.

بحث Operaالإنتاج

البحث operaنشوئها هو أبسط operaنشوئها على شجرة B.

التاليwing يتم تطبيق الخوارزمية:

  • دع المفتاح (القيمة) يتم البحث عنه بواسطة "k".
  • ابدأ بنفسكarchiنانوغرام من الجذر واجتياز بشكل متكرر إلى أسفل.
  • إذا كانت k أقل من قيمة الجذر، فابحث في الشجرة الفرعية اليسرى، وإذا كانت k أكبر من قيمة الجذر، فابحث في الشجرة الفرعية اليمنى.
  • إذا كانت العقدة تحتوي على k الذي تم العثور عليه، فما عليك سوى إرجاع العقدة.
  • إذا لم يتم العثور على k في العقدة، فانتقل إلى الطفل باستخدام مفتاح أكبر.
  • إذا لم يتم العثور على k في الشجرة، فإننا نعيد NULL.

إدراج Operaالإنتاج

نظرًا لأن B Tree عبارة عن شجرة ذاتية التوازن، فلا يمكنك فرض إدخال مفتاح في أي عقدة فقط.

التاليwing تنطبق الخوارزمية:

  • قم بتشغيل البحث operaنشوئها والعثور على المكان المناسب للإدراج.
  • أدخل المفتاح الجديد في الموقع المناسب، ولكن إذا كانت العقدة تحتوي على الحد الأقصى لعدد المفاتيح بالفعل:
  • سيتم فصل العقدة، مع المفتاح المدرج حديثًا، عن العنصر الأوسط.
  • سيصبح العنصر الأوسط هو الأصل للعقدتين الفرعيتين الأخريين.
  • يجب على العقد إعادة ترتيب المفاتيح بترتيب تصاعدي.
TIP التاليwing غير صحيح فيما يتعلق بخوارزمية الإدراج:

نظرًا لأن العقدة ممتلئة، فسيتم تقسيمها، ومن ثم سيتم إدراج قيمة جديدة

إدراج Operaالإنتاج

في المثال أعلاه:

  • ابحث في الموضع المناسب في العقدة عن المفتاح
  • أدخل المفتاح في العقدة المستهدفة، وتحقق من القواعد
  • بعد الإدراج، هل تحتوي العقدة على أكثر من الحد الأدنى لعدد المفاتيح، وهو 1؟ في هذه الحالة، نعم، يحدث ذلك. تحقق من القاعدة التالية.
  • بعد الإدراج، هل تحتوي العقدة على أكثر من الحد الأقصى لعدد المفاتيح، وهو 3؟ في هذه الحالة، لا، لا يحدث ذلك. وهذا يعني أن الشجرة B لا تنتهك أي قواعد، وأن عملية الإدراج قد اكتملت.

إدراج Operaالإنتاج

في المثال أعلاه:

  • وصلت العقدة إلى الحد الأقصى لعدد المفاتيح
  • سيتم تقسيم العقدة، وسيصبح المفتاح الأوسط هو العقدة الجذرية للعقدتين المتبقيتين.
  • في حالة وجود عدد زوجي من المفاتيح، سيتم اختيار العقدة الوسطى عن طريق الانحياز الأيسر أو الانحياز الأيمن.

إدراج Operaالإنتاج

في المثال أعلاه:

  • تحتوي العقدة على أقل من الحد الأقصى للمفاتيح
  • تم إدراج الرقم 1 بجوار الرقم 3، ولكن تم انتهاك قاعدة الترتيب التصاعدي
  • من أجل إصلاح هذا، يتم فرز المفاتيح

وبالمثل، يمكن إدراج 13 و 2 بسهولة في العقدة لأنها تلبي قاعدة مفاتيح أقل من الحد الأقصى للعقد.

إدراج Operaالإنتاج

في المثال أعلاه:

  • تحتوي العقدة على مفاتيح تساوي الحد الأقصى للمفاتيح.
  • يتم إدخال المفتاح إلى العقدة المستهدفة، لكنه ينتهك قاعدة الحد الأقصى للمفاتيح.
  • تم تقسيم العقدة المستهدفة، وأصبح المفتاح الأوسط بالانحياز الأيسر الآن هو الأصل للعقد الفرعية الجديدة.
  • يتم ترتيب العقد الجديدة بترتيب تصاعدي.

وبالمثل، واستنادًا إلى القواعد والحالات المذكورة أعلاه، يمكن إدراج بقية القيم بسهولة في الشجرة B.

إدراج Operaالإنتاج

حذف Operaالإنتاج

الحذف operaيحتوي tion على قواعد أكثر من الإدراج والبحث operaستعقد.

التاليwing تنطبق الخوارزمية:

  • قم بتشغيل البحث operaنشوئها والعثور على المفتاح الهدف في العقد
  • يتم تطبيق ثلاثة شروط بناءً على موقع مفتاح الهدف، كما هو موضح في الصفحة التاليةwing أقسام

إذا كان المفتاح الهدف موجودًا في العقدة الطرفية

  • الهدف موجود في العقدة الطرفية، أكثر من مفاتيح دقيقة.
  • لن يؤدي حذف هذا إلى انتهاك ملكية B Tree
  • الهدف موجود في العقدة الطرفية، ويحتوي على الحد الأدنى من العقد الرئيسية
  • سيؤدي حذف هذا إلى انتهاك ملكية B Tree
  • يمكن للعقدة المستهدفة استعارة المفتاح من العقدة اليسرى المباشرة، أو العقدة اليمنى المباشرة (الشقيقة)
  • سيقول الأخ نعم فعلا إذا كان لديه أكثر من الحد الأدنى لعدد المفاتيح
  • سيتم استعارة المفتاح من العقدة الأصلية، وسيتم نقل القيمة القصوى إلى العقدة الأصلية، وسيتم نقل القيمة القصوى للعقدة الأصلية إلى العقدة المستهدفة، وإزالة القيمة المستهدفة
  • الهدف موجود في العقدة الطرفية، ولكن لا يوجد أي أشقاء لديهم أكثر من الحد الأدنى لعدد المفاتيح
  • ابحث عن المفتاح
  • دمج مع الأشقاء والحد الأدنى من العقد الأصل
  • سيكون إجمالي المفاتيح الآن أكثر من دقيقة
  • سيتم استبدال المفتاح الهدف بالحد الأدنى من العقدة الأصلية

إذا كان المفتاح الهدف موجودًا في عقدة داخلية

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

إذا كان المفتاح الهدف موجودًا في العقدة الجذرية

  • استبدل بالحد الأقصى لعنصر الشجرة الفرعية السابقة بالترتيب
  • إذا كان الهدف، بعد الحذف، يحتوي على أقل من مفاتيح الحد الأدنى، فستقترض العقدة المستهدفة الحد الأقصى لقيمة من شقيقها عبر والد الأخ.
  • سيتم أخذ القيمة القصوى للأصل بواسطة الهدف، ولكن مع عقد القيمة القصوى للأخ.

الآن دعونا نفهم الحذف operaمع مثال.

حذف Operaالإنتاج

يعرض الرسم البياني أعلاه حالات الحذف المختلفة operaنشوئها في شجرة B. شجرة B هذه من الرتبة 5، مما يعني أن الحد الأدنى لعدد العقد الفرعية التي يمكن أن تحتوي عليها أي عقدة هو 3، والحد الأقصى لعدد العقد الفرعية التي يمكن أن تحتوي عليها أي عقدة هو 5. في حين أن الحد الأدنى والحد الأقصى لعدد المفاتيح في أي عقدة يمكن أن يكون 2 و 4، على التوالي.

حذف Operaالإنتاج

في المثال أعلاه:

  • تحتوي العقدة المستهدفة على مفتاح الهدف المراد حذفه
  • تحتوي العقدة المستهدفة على مفاتيح أكثر من الحد الأدنى من المفاتيح
  • ببساطة قم بحذف المفتاح

حذف Operaالإنتاج

في المثال أعلاه:

  • تحتوي العقدة المستهدفة على مفاتيح تساوي الحد الأدنى من المفاتيح، لذا لا يمكن حذفها مباشرة لأنها ستخالف الشروط

الآن، اتبعwing يوضح الرسم البياني كيفية حذف هذا المفتاح:

حذف Operaالإنتاج

  • سوف تستعير العقدة المستهدفة مفتاحًا من الأخ المباشر، في هذه الحالة، السلف بالترتيب (الأخ الأيسر) لأنه لا يوجد لديه أي خليفة بالترتيب (الأخ الأيمن)
  • سيتم نقل الحد الأقصى لقيمة الترتيب السابق إلى العقدة الأم، وسيقوم الأصل بنقل القيمة القصوى إلى العقدة المستهدفة (انظر الرسم البياني أدناه)

التاليwing يوضح المثال كيفية حذف مفتاح يحتاج إلى قيمة من خليفته بالترتيب.

حذف Operaالإنتاج

  • ستستعير العقدة المستهدفة مفتاحًا من الأخ المباشر، في هذه الحالة، العقدة اللاحقة في الترتيب (الأخ الأيمن) لأن سابقتها في الترتيب (الأخ الأيسر) لديها مفاتيح مساوية للحد الأدنى من المفاتيح.
  • سيتم نقل الحد الأدنى لقيمة العقدة اللاحقة بالترتيب إلى العقدة الأم، وسيقوم الأصل بنقل القيمة القصوى إلى العقدة المستهدفة.

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

راجع إجراء حذف هذا المفتاح:

حذف Operaالإنتاج

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

حذف Operaالكود الزائف

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

الناتج:

يتم حذف العنصر الأكبر من B-Tree.

نبذة عامة

  • B Tree عبارة عن بنية بيانات ذاتية التوازن للبحث بشكل أفضل عن البيانات وإدراجها وحذفها من القرص.
  • يتم تنظيم شجرة B بالدرجة المحددة
  • ب- يتم ترتيب مفاتيح وعقد الشجرة بترتيب تصاعدي.
  • البحث operaيعد B Tree هو الأبسط، والذي يبدأ دائمًا من الجذر ويبدأ في التحقق مما إذا كان المفتاح الهدف أكبر أو أقل من قيمة العقدة.
  • الملحق operaإن عملية B Tree مفصلة إلى حد ما، حيث تجد أولاً موضع الإدراج المناسب للمفتاح الهدف، وتقوم بإدراجه، وتقييم صلاحية B Tree مقابل حالات مختلفة، ثم إعادة هيكلة عقد B Tree وفقًا لذلك.
  • الحذف operaتبحث B Tree أولاً عن المفتاح الهدف المراد حذفه، وتحذفه، وتقيم الصلاحية بناءً على عدة حالات مثل الحد الأدنى والحد الأقصى لمفاتيح العقدة المستهدفة، والأشقاء، والأصل.