شجرة البحث
شجرة البحث في سياق علوم الحاسب هي هيكل بيانات على شكل شجرة مُرتبة بطريقة معينة، حيث تكون قيمة كل عقدة أصلية أكبر من قيمة أي عقدة فرعية لها على اليسار، وأقل من قيمة أي عقدة فرعية لها على اليمين، وتُستخدم شجرة البحث في البحث عن عقدة من ضمن عقدها (ويسمى القيمة أو مفتاح) مستخدمة اقتران الاسم والقيمة. [1] تتميز شجرة البحث بفعالية وقت البحث إذا كانت شجرة متوازنة (أي عُقد أوراقها (العُقد الطرفية) تقع في نفس المستوى)، وتتنوع أشكال شجرة البحث، ويسمح العديد منها بإدراج وحذف العناصر بكفاءة، بشكل يحافظ على توازن الشجرة.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c8/%D8%B4%D8%AC%D8%B1%D8%A9_%D8%A7%D9%84%D8%A8%D8%AD%D8%AB.png/220px-%D8%B4%D8%AC%D8%B1%D8%A9_%D8%A7%D9%84%D8%A8%D8%AD%D8%AB.png)
شكل 2: ليست شجرة بحث، لأن العقدة الفرعية اليمني 2 أقل من العقدة الأصلية لها 7.
(ملاحظة: كلا الشجرتين من النوع الثنائي)
أنواع شجرة البحث
عدلشجرة البحث الثنائية
عدلشجرة البحث الثنائية هي شجرة بحث تحتوي كل عقدة أصلية على عقدتين فرعيتين كحد أقصى.
شجرة البحث الثلاثية
عدلشجرة بحث يمكن أن تحتوي على 3 عقد فرعية: عقدة فرعية منخفضة، وعقدة فرعية متساوية، وعقدة فرعية مرتفعة. تقوم كل عقدة بتخزين حرف واحد ويتم ترتيب الشجرة نفسها بنفس طريقة ترتيب شجرة البحث الثنائية، باستثناء عقدة ثالثة محتملة.
شجرة ب
عدلتُمثل الشجرة ب تعميما لأشجار البحث الثنائية، حيث يمكن لكل عقدة أصلية أن تحتوي على عدد متغير من العقد الفرعية ضمن نطاق محدد مسبقًا، إلا أنها لن تكون جميعها بالضرورة مملوءة بالبيانات، مما يعني أن الشجرة ب يمكن أن تهدر بعض المساحة. والميزة فيها هي أنها لا تحتاج إلى إعادة التوازن بشكل متكرر، وتُستخدم الشجرة ب بشكل شائع في قواعد البيانات.
شجرة (a،b)
عدلتحتوي الشجرة (أ، ب) على عدد من العقد الفرعية لا يقل عن ولا يزيد عن .
مراجع
عدل- ^ Black, Paul and Pieterse, Vreda (2005). "search tree". Dictionary of Algorithms and Data Structures نسخة محفوظة 2024-02-11 على موقع واي باك مشين.
شجرة البحث في المشاريع الشقيقة: | |
|