شجرة البحث

شكل 1: شجرة بحث لأن أي عقدة فرعية علي اليسار أقل من العقدة الأصلية لها، وأي عقدة فرعية على اليمين أكبر من العقدة الأصلية لها.
شكل 2: ليست شجرة بحث، لأن العقدة الفرعية اليمني 2 أقل من العقدة الأصلية لها 7.
(ملاحظة: كلا الشجرتين من النوع الثنائي)

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

أنواع شجرة البحث

شجرة البحث الثنائية

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

شجرة البحث الثلاثية

شجرة بحث يمكن أن تحتوي على 3 عقد فرعية: عقدة فرعية منخفضة، وعقدة فرعية متساوية، وعقدة فرعية مرتفعة. تقوم كل عقدة بتخزين حرف واحد ويتم ترتيب الشجرة نفسها بنفس طريقة ترتيب شجرة البحث الثنائية، باستثناء عقدة ثالثة محتملة.

شجرة ب

تُمثل الشجرة ب تعميما لأشجار البحث الثنائية، حيث يمكن لكل عقدة أصلية أن تحتوي على عدد متغير من العقد الفرعية ضمن نطاق محدد مسبقًا، إلا أنها لن تكون جميعها بالضرورة مملوءة بالبيانات، مما يعني أن الشجرة ب يمكن أن تهدر بعض المساحة. والميزة فيها هي أنها لا تحتاج إلى إعادة التوازن بشكل متكرر، وتُستخدم الشجرة ب بشكل شائع في قواعد البيانات.

شجرة (a،b)

تحتوي الشجرة (أ، ب) على عدد من العقد الفرعية لا يقل عن $a$ ولا يزيد عن $b$.