شجرة البحث
تعريفًا بالموضوع، شجرة البحث في سياق علوم الحاسب هي هيكل بيانات على شكل شجرة مُرتبة بطريقة معينة، حيث تكون قيمة كل عقدة أصلية أكبر من قيمة أي عقدة فرعية لها على اليسار، وأقل من قيمة أي عقدة فرعية لها على اليمين، وتُستعمل شجرة البحث في البحث عن عقدة من ضمن عقدها (ويسمى القيمة أو مفتاح) مستعملة اقتران الاسم والقيمة. تتميز شجرة البحث بفعالية وقت البحث إذا كانت شجرة متوازنة (أي عُقد أوراقها (العُقد الطرفية) تقع في نفس المستوى)، وتتنوع أشكال شجرة البحث، ويسمح العديد منها بإدراج وحذف العناصر بكفاءة، بشكل يحافظ على توازن الشجرة. وفيما يلي تفاصيل أوسع عن ذلك.
أنواع شجرة البحث
شجرة البحث الثلاثية
وفي هذا السياق، شجرة بحث يمكن أن تحتوي على 3 عقد فرعية: عقدة فرعية منخفضة، وعقدة فرعية متساوية، وعقدة فرعية مرتفعة. تقوم كل عقدة بتخزين حرف واحد ويتم ترتيب الشجرة نفسها بنفس طريقة ترتيب شجرة البحث الثنائية، باستثناء عقدة ثالثة محتملة.
شجرة ب
كذلك، تحتوي الشجرة (أ، ب) على عدد من العقد الفرعية لا يقل عن ولا يزيد عن .
من جهة ثانية، تُمثل الشجرة ب تعميما لأشجار البحث الثنائية، حيث يمكن لكل عقدة أصلية أن تحتوي على عدد متغير من العقد الفرعية ضمن نطاق محدد مسبقًا، إلا أنها لن تكون جميعها بالضرورة مملوءة بالبيانات، مما يعني أن الشجرة ب يمكن أن تهدر بعض المساحة. والميزة فيها هي أنها لا تحتاج إلى إعادة التوازن بشكل متكرر، وتُستعمل الشجرة ب بشكل شائع في قواعد البيانات.
شجرة (a،b)
شجرة البحث الثنائية
ومن جهة أخرى، شجرة البحث الثنائية هي شجرة بحث تحتوي كل عقدة أصلية على عقدتين فرعيتين كحد أقصى.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟