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

فكرة جديدة

بحث سريع وإدراج رخيص في الوقت نفسه؟

المصفوفة المرتّبة تبحث في O(log n)، لكن الإدراج فيها يعني الإزاحة، أي O(n). والقائمة المترابطة تضيف في أولها بتكلفة قليلة، لكن العثور على أي شيء فيها يعني المشي، أي O(n). فهل توجد بنية تُجيد الأمرين؟

تعرّف إلى شجرة البحث الثنائية (binary search tree). مثل القائمة المترابطة، هي عقد تربطها مؤشّرات. لكن لكل عقدة مؤشّران اثنان: ابن أيسر وابن أيمن. والعقدة التي في القمة اسمها الجذر (root).

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

للإدراج، ابدأ من الجذر. أصغر؟ اذهب يسارًا. أكبر؟ اذهب يمينًا. كرّر حتى تجد مكانًا فارغًا، وعلّق العقدة الجديدة هناك.