شجرة البحث

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

إن أسوأ تعقيد زمني للبحث في شجرة بحث ثنائية هو ارتفاع الشجرة ، والذي يمكن أن يكون صغيرًا مثل O(log n) لشجرة تحتوي على n عنصرًا.

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

نظراً لنطاق طول العقد المتغير، فإن أشجار B مُحسَّنة للأنظمة التي تقرأ كتلًا كبيرة من البيانات، كما أنها تُستخدم بشكل شائع في قواعد البيانات.

التعقيد الزمني للبحث في شجرة B هو O(log n).

شجرة (أ، ب) هي شجرة بحث تكون فيها جميع أوراقها بنفس العمق. تحتوي كل عقدة على ما لا يقل عن أ من الأبناء وما لا يزيد عن ب من الأبناء، بينما يحتوي الجذر على ما لا يقل عن 2 من الأبناء وما لا يزيد عن ب من الأبناء.

يمكن تحديد قيمتي a و b باستخدام الصيغة التالية: ^{[ 2 ]}

${\displaystyle 2\leq a\leq {\frac {(b+1)}{2}}}$

التعقيد الزمني للبحث في شجرة (a,b) هو O(log n).

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

يتضمن البحث في شجرة بحث ثلاثية تمرير سلسلة نصية لاختبار ما إذا كان أي مسار يحتوي عليها.

التعقيد الزمني للبحث في شجرة بحث ثلاثية متوازنة هو O(log n).

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

ابحث بشكل متكرر (المفتاح، العقدة) إذا كانت العقدة فارغة، فأرجع شجرة فارغة إذا كان المفتاح < مفتاح العقدة أعد البحث التكراري (المفتاح، العقدة.اليسار) وإلا إذا كان المفتاح أكبر من مفتاح العقدة أعد البحث التكراري (المفتاح، العقدة.اليمين) وإلا فأعد العقدة

searchIterative(key, node) العقدة الحالية := العقدة طالما أن العقدة الحالية ليست فارغة ، إذا كان مفتاح العقدة الحالية يساوي المفتاح، فأرجع العقدة الحالية، وإلا إذا كان مفتاح العقدة الحالية أكبر من المفتاح. currentNode := currentNode.left وإلا فإن العقدة الحالية := العقدة الحالية.يمين

في الشجرة المرتبة، يقع الحد الأدنى عند العقدة الأبعد إلى اليسار، بينما يقع الحد الأقصى عند العقدة الأبعد إلى اليمين. ^{[ 3 ]}

إذا كانت قيمة `node` تساوي `NULL`، فسيتم استدعاء الدالة `findMinimum(node)`، ثم يتم إرجاع `EMPTY_TREE`. الحد الأدنى := عقدة طالما أن min.left ليس فارغًا min := min.left إرجاع المفتاح الأدنى

إذا كانت قيمة العقدة NULL، فسيتم استدعاء الدالة findMaximum(node) ثم يتم إرجاع EMPTY_TREE الحد الأقصى := العقدة طالما أن max.right ليس NULL الحد الأقصى := الحد الأقصى.يمين إرجاع max.key