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

يمكن تعريف إدخال قيمة في بحث ثلاثي بشكل تكراري أو متكرر، تمامًا كما هو الحال في عمليات البحث. تُستدعى هذه الطريقة التكرارية باستمرار على عُقد الشجرة، مع إعطاء مفتاح يتقلص طوله تدريجيًا بحذف الأحرف الأولى منه. إذا وصلت هذه الطريقة إلى عُقدة لم تُنشأ بعد، فإنها تُنشئها وتُسند إليها قيمة الحرف الأول من المفتاح. سواء أُنشئت عُقدة جديدة أم لا، تتحقق الطريقة مما إذا كان الحرف الأول في السلسلة أكبر من أو أصغر من قيمة الحرف في العُقدة، ثم تُجري استدعاءً تكراريًا على العُقدة المناسبة كما في عملية البحث. أما إذا كان الحرف الأول من المفتاح مساويًا لقيمة العُقدة، فسيتم استدعاء إجراء الإدخال على العُقدة المُساوية، ويُحذف الحرف الأول من المفتاح. ^{[ 1 ]} ومثل أشجار البحث الثنائية وغيرها من هياكل البيانات ، قد تُصبح أشجار البحث الثلاثية مُنحلة اعتمادًا على ترتيب المفاتيح. ^{[ 3 ]} يُعدّ إدخال المفاتيح بالترتيب الأبجدي إحدى طرق الحصول على أسوأ شجرة متدهورة ممكنة. ^{[ 1 ]} غالبًا ما ينتج عن إدخال المفاتيح بترتيب عشوائي شجرة متوازنة جيدًا. ^{[ 1 ]}

دالة الإدراج ( سلسلة مفتاح ) هي عقدة p := جذر // يتم تهيئتها لتكون مساوية في حالة كون الجذر فارغًا عقدة آخر := جذر عدد صحيح idx := 0 بينما p ليس فارغًا do // تكرار على الشجرة الفرعية المناسبة إذا كان المفتاح [ idx ] < p.splitchar ثم آخر : = p p := p.left وإلا إذا كان المفتاح [ idx ] > p.splitchar ثم آخر : = p p : = p.right وإلا : // المفتاح موجود بالفعل في شجرتنا إذا كان idx == طول ( المفتاح ) ثم إرجاع // حذف حرف من مفتاحنا idx := idx + 1 آخر := p p : = p.mid p : = عقدة () // إضافة p كعقدة فرعية للعقدة الأخيرة غير الفارغة (أو الجذر إذا كان الجذر فارغًا) إذا كان الجذر == فارغًا ثم الجذر := p وإلا إذا كان آخر . splitchar < المفتاح [ idx ] ثم آخر . right := p وإلا إذا كان آخر . splitchar > المفتاح [ idx ] ثم آخر . left : = p else last.mid : = p p.splitchar : = key [ idx ] idx : = idx + 1 // أدخل باقي المفتاح while idx < length ( key ) do p.mid : = node ( ) p.mid.splitchar : = key [idx ] idx += 1 p := p . mid

للبحث عن عقدة معينة أو البيانات المرتبطة بها، يلزم مفتاح نصي. تبدأ عملية البحث بفحص العقدة الجذرية للشجرة وتحديد أي من الشروط التالية قد تحقق. إذا كان الحرف الأول من النص أصغر من الحرف الموجود في العقدة الجذرية، فيمكن استدعاء بحث تكراري على الشجرة التي جذرها هو الحرف الأول من العقدة الجذرية الحالية. وبالمثل، إذا كان الحرف الأول أكبر من الحرف الموجود في العقدة الحالية في الشجرة، فيمكن إجراء استدعاء تكراري على الشجرة التي جذرها هو الحرف الثاني من العقدة الحالية. ^{[ 1 ]} في الحالة الأخيرة، إذا كان الحرف الأول من النص مساويًا للحرف الموجود في العقدة الحالية، فإن الدالة تُرجع العقدة إذا لم يكن هناك المزيد من الأحرف في المفتاح. إذا كان هناك المزيد من الأحرف في المفتاح، فيجب إزالة الحرف الأول منه، ثم يُجرى استدعاء تكراري مع العقدة ذات الحرف الأول المساوٍ والمفتاح المُعدَّل. ^{[ 1 ]} يمكن أيضًا كتابة ذلك بطريقة غير تكرارية باستخدام مؤشر إلى العقدة الحالية ومؤشر إلى الحرف الحالي من المفتاح. ^{[ 1 ]}

دالة البحث ( سلسلة الاستعلام ) هي إذا كانت ( الاستعلام ) فارغة، فأرجع خطأ . العقدة p := الجذر ، عدد صحيح idx := 0، ​​طالما أن p ليس فارغًا ، إذا كان [ idx ] في الاستعلام < p.splitchar ، فإن p := p.left ، وإذا كان [ idx ] في الاستعلام > p.splitchar ، فإن p := p.right ، وإذا كان idx = طول ( الاستعلام ) ، فأرجع صحيحًا . idx := idx + 1 ، p : = p.mid ، أرجع خطأ .

تتضمن عملية الحذف البحث عن سلسلة مفتاحية في شجرة البحث، وإيجاد عقدة، تُسمى firstMid في الشفرة الزائفة أدناه، بحيث لا يحتوي المسار من الابن الأوسط لـ firstMid إلى نهاية مسار البحث عن السلسلة المفتاحية على أي أبناء يمين أو يسار. يُمثل هذا لاحقة فريدة في الشجرة الثلاثية تُطابق السلسلة المفتاحية. إذا لم يكن هناك مثل هذا المسار، فهذا يعني أن السلسلة المفتاحية إما مُضمنة بالكامل كبادئة لسلسلة أخرى، أو أنها غير موجودة في شجرة البحث. تستخدم العديد من التطبيقات حرف نهاية السلسلة لضمان حدوث الحالة الأخيرة فقط. ثم يُحذف المسار من firstMid.mid إلى نهاية مسار البحث. في حالة كون firstMid هي الجذر، فلا بد أن السلسلة المفتاحية كانت آخر سلسلة في الشجرة، وبالتالي يُعيّن الجذر إلى null بعد الحذف.

دالة الحذف ( مفتاح السلسلة ) هي إذا كانت ( المفتاح ) فارغة، فقم بإرجاع العقدة p := الجذر int idx := 0node firstMid := null while p is not null do if key [ idx ] < p.splitchar then firstMid : = null p : = p.left else if key [ idx ] > p.splitchar then firstMid : = null p : = p.right else firstMid : = p while p is not null and key [ idx ] == p.splitchar do idx : = idx + 1 p : = p.mid if firstMid == null then return // لا يوجد لاحقة سلسلة فريدة// في هذه المرحلة، يشير firstMid إلى العقدة التي تسبق اللاحقة الفريدة للسلسلة. node q : = firstMid.mid node p : = q firstMid.mid : = null // فصل اللاحقة عن الشجرة while q is not null do // السير على طول مسار اللاحقة وحذف العقد p : = q q := q.mid delete ( p ) // تحرير الذاكرة المرتبطة بالعقدة p if firstMid == root then delete ( root ) // حذف الشجرة بأكملها root := null

على الرغم من أن أشجار البحث الثلاثية أبطأ من أشجار البادئات الأخرى ، إلا أنها قد تكون أكثر ملاءمة لمجموعات البيانات الأكبر حجماً نظراً لكفاءتها في استخدام المساحة. ^{[ 1 ]}

يمكن استخدام جداول التجزئة بدلاً من أشجار البحث الثلاثية لربط السلاسل النصية بالقيم. مع ذلك، تستهلك جداول التجزئة عادةً ذاكرة أكبر من أشجار البحث الثلاثية (لكن ليس بقدر أشجار البحث الثلاثية). إضافةً إلى ذلك، تكون جداول التجزئة أبطأ في الإبلاغ عن سلسلة نصية لا تنتمي إلى نفس بنية البيانات، لأنها تقارن السلسلة بأكملها بدلاً من الأحرف القليلة الأولى فقط. تشير بعض الأدلة إلى أن أشجار البحث الثلاثية تعمل بشكل أسرع من جداول التجزئة. ^{[ 1 ]} كما أن جداول التجزئة لا تدعم العديد من استخدامات أشجار البحث الثلاثية، مثل البحث عن أقرب الجيران .

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