تنفيذ شجرة بحث ثنائية

2024 مؤلف: Angel Austin | [email protected]. آخر تعديل: 2023-12-17 05:16

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

يشار إليها غالبًا باسم BST ، والتي لها خاصية خاصة: تقع العقد الأكبر من الجذر على يمينها ، والعقد الأصغر على اليسار.

النظرية العامة والمصطلحات

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

مصطلحات الشجرة:

1. عمق العقدة هو عدد الحواف المحددة من الجذر إليها.
2. ارتفاع العقدة هو عدد الحواف المحددة منها إلى أعمق ورقة.
3. يتم تحديد ارتفاع الشجرة بارتفاع الجذر.
4. شجرة البحث الثنائية هي تصميم خاص ، فهي توفر أفضل نسبة ارتفاع وعدد العقد.
5. الارتفاع h مع العقد N على الأكثر O (تسجيل N).

يمكنك إثبات ذلك بسهولة عن طريق حساب العقد في كل مستوى ، بدءًا من الجذر ، بافتراض أنها تحتوي على أكبر عدد منها: n=1 + 2 + 4 +… + 2 h-1 + 2 h=2 h + 1 - 1 حل هذا من أجل h يعطي h=O (log n)

فوائد الخشب:

1. تعكس العلاقات الهيكلية للبيانات.
2. تستخدم لتمثيل التسلسلات الهرمية.
3. تأكد من التثبيت والبحث الفعال.
4. الأشجار هي بيانات مرنة للغاية ، مما يسمح لك بتحريك الأشجار الفرعية بأقل جهد.

طريقة البحث

بشكل عام ، لتحديد ما إذا كانت القيمة موجودة في BST ، ابدأ شجرة بحث ثنائية في جذرها وحدد ما إذا كانت تفي بالمتطلبات:

• كن في الجذر ؛
• كن في الشجرة الفرعية اليسرى للجذر ؛
• في الشجرة الفرعية اليمنى للجذر.

إذا لم يتم استيفاء أي سجل أساسي ، فسيتم إجراء بحث متكرر في الشجرة الفرعية المقابلة. يوجد في الواقع خياران أساسيان:

1. الشجرة فارغة - إرجاع خطأ.
2. القيمة في العقدة الجذرية - إرجاع صحيح.

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

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

50

/

10

15

30

/

20

تحتوي هذه الشجرة على 5 عقد والارتفاع=5. سيتطلب البحث عن القيم في النطاق 16-19 و21-29 المسار التالي من الجذر إلى الورقة (العقدة التي تحتوي على القيمة 20) ، أي ، سوف يستغرق وقتًا يتناسب مع عدد العقد. في أحسن الأحوال ، لديهم جميعًا طفلان ، وتقع الأوراق على نفس العمق.

تحتوي شجرة البحث الثنائية هذه على 7 عقد والارتفاع=3. بشكل عام ، شجرة مثل هذه (الشجرة الكاملة) سيكون ارتفاعها تقريبًا سجل 2 (N) ، حيث N هو عدد العقد في الشجرة. قيمة السجل 2 (N) هي عدد المرات (2) التي يمكن فيها قسمة N قبل الوصول إلى الصفر.

التلخيص: أسوأ وقت مطلوب للبحث في BST هو O (ارتفاع الشجرة). أسوأ شجرة "خطية" هي O (N) ، حيث N هو عدد العقد في الشجرة. في أفضل الأحوال ، تكون الشجرة "الكاملة" هي O (سجل N).

BST إدراج ثنائي

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

1. التكرارات غير مسموح بها ، محاولة إدراج قيمة مكررة ستؤدي إلى استثناء.
2. تستخدم طريقة الإدراج العامة طريقة "مساعدة" مساعدة متكررة للإدراج فعليًا.
3. يتم دائمًا إدراج العقدة التي تحتوي على قيمة جديدة كورقة في BST.
4. يعيد التابع public insert فارغًا ، لكن الطريقة المساعدة تُرجع BSTnode. يقوم بذلك للتعامل مع الحالة التي تكون فيها العقدة التي تم تمريرها إليها فارغة.

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

الحذف في الخوارزمية الثنائية

كما قد تتوقع ، يتضمن حذف عنصر العثور على عقدة تحتوي على القيمة المراد إزالتها. هناك عدة أشياء في هذا الرمز:

1. BST يستخدم طريقة حذف مساعدة محملة بشكل زائد. إذا لم يكن العنصر الذي تبحث عنه في الشجرة ، فسيتم استدعاء الطريقة المساعدة في النهاية مع n==null. هذا لا يعتبر خطأ ، الشجرة ببساطة لا تتغير في هذه الحالة. طريقة حذف المساعد ترجع قيمة - مؤشر إلى الشجرة المحدثة.
2. عند إزالة ورقة ، تؤدي الإزالة من شجرة البحث الثنائية إلى تعيين المؤشر الفرعي المقابل لوالدها على "فارغ" ، أو تعيين الجذر على "فارغ" إذا كان العنصر الذي يتم إزالتهالعقدة هي جذر وليس لها أبناء.
3. لاحظ أن استدعاء الحذف يجب أن يكون واحدًا مما يلي: root=delete (root، key)، n.setLeft (delete (n.getLeft ()، key))، n.set Right (delete (n. getRight () ، مفتاح)). وبالتالي ، في جميع الحالات الثلاث ، من الصحيح أن طريقة الحذف ترجع ببساطة فارغة.
4. عندما ينجح البحث عن العقدة التي تحتوي على القيمة المراد حذفها ، هناك ثلاثة خيارات: العقدة المراد حذفها هي ورقة (ليس لها أطفال) ، والعقدة المراد حذفها لها طفل واحد ، ولديها اثنان الأطفال.
5. عندما يكون للعقدة التي يتم إزالتها طفل واحد ، يمكنك ببساطة استبدالها بطفل ، وإعادة المؤشر إلى الطفل.
6. إذا كانت العقدة المراد حذفها تحتوي على صفر أو 1 تابع ، فإن طريقة الحذف "ستتبع المسار" من الجذر إلى تلك العقدة. لذا فإن أسوأ وقت يتناسب مع ارتفاع الشجرة لكل من البحث والإدخال.

إذا كان للعقدة المراد إزالتها طفلان ، يتم اتباع الخطوات التالية:

1. ابحث عن العقدة المراد حذفها ، باتباع المسار من الجذر إليها.
2. ابحث عن أصغر قيمة لـ v في الشجرة الفرعية اليمنى ، واستمر على طول المسار إلى الورقة.
3. قم بإزالة قيمة v بشكل متكرر ، اتبع نفس المسار كما في الخطوة 2.
4. وهكذا ، في أسوأ الحالات ، يتم تنفيذ المسار من الجذر إلى الورقة مرتين.

ترتيب العبور

الاجتياز عملية تزور جميع العقد في الشجرة. نظرًا لأن شجرة البحث الثنائية C عبارة عن بنية بيانات غير خطية ، فلا يوجد اجتياز فريد. على سبيل المثال ، في بعض الأحيان عدة خوارزميات الاجتيازمجمعة في النوعين التاليين:

• عبور العمق ؛
• أول تمريرة.

هناك نوع واحد فقط من تقاطع العرض - تجاوز المستوى. يزور هذا الاجتياز مستوى العقد لأسفل ولليسار ولأعلى ولليمين.

هناك ثلاثة أنواع مختلفة من معابر العمق:

1. تمرير الطلب المسبق - قم أولاً بزيارة الوالد ثم الطفل الأيسر والأيمن.
2. Passing InOrder - زيارة الطفل الأيسر ، ثم الوالد والطفل الأيمن.
3. تجاوز PostOrder - زيارة الطفل الأيسر ، ثم الطفل الأيمن ، ثم الأب.

مثال لأربع عمليات اجتياز لشجرة بحث ثنائية:

1. الأمر المسبق - 8 ، 5 ، 9 ، 7 ، 1 ، 12 ، 2 ، 4 ، 11 ، 3.
2. داخل الطلب - 9 ، 5 ، 1 ، 7 ، 2 ، 12 ، 8 ، 4 ، 3 ، 11.
3. PostOrder - 9 ، 1 ، 2 ، 12 ، 7 ، 5 ، 3 ، 11 ، 4 ، 8.
4. المستوى - 8 ، 5 ، 4 ، 9 ، 7 ، 11 ، 1 ، 12 ، 3 ، 2.

يوضح الشكل الترتيب الذي تتم فيه زيارة العقد. الرقم 1 هو العقدة الأولى في اجتياز معين ، و 7 هو العقدة الأخيرة.

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

التنقل والتصحيح

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

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

وظيفة Konsolenausgabe

تقوم هذه الوظيفة بمسح الشجرة بأكملها إلى وحدة التحكم وبالتالي فهي مفيدة للغاية. الترتيب الذي يتم تنفيذ هدف ناتج الشجرة به هو:

1. للقيام بذلك ، تحتاج أولاً إلى تحديد المعلومات التي سيتم إخراجها من خلال العقدة.
2. وتحتاج أيضًا إلى معرفة مدى عرض الشجرة وطولها لحساب مقدار المساحة التي يجب تركها.
3. تحسب الوظائف التالية هذه المعلومات للشجرة وكل شجرة فرعية. نظرًا لأنه لا يمكنك الكتابة إلا على وحدة التحكم سطرًا بسطر ، فستحتاج أيضًا إلى طباعة شجرة سطرًا بسطر.
4. الآن نحن بحاجة إلى طريقة أخرى للانسحابالشجرة بأكملها ، وليس فقط سطرا سطرا.
5. بمساعدة وظيفة التفريغ ، يمكنك قراءة الشجرة وتحسين خوارزمية الإخراج بشكل كبير ، فيما يتعلق بالسرعة.

ومع ذلك ، سيكون من الصعب استخدام هذه الوظيفة على الأشجار الكبيرة.

نسخ المُنشئ والمدمر

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

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

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

إنشاء شجرة بحث ثنائية

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

1. تحتوي العقدة الأصلية على عقدتين فرعيتين على الأكثر.
2. العقدة الفرعية اليسرى دائمًا أقل من العقدة الأصلية.
3. العقدة الفرعية الصالحة تكون دائمًا أكبر من أو تساوي العقدة الأصلية.

المصفوفة التي سيتم استخدامها لبناء شجرة البحث الثنائية:

1. مصفوفة عدد صحيح أساسي من سبع قيم بترتيب غير مفرز.
2. القيمة الأولى في المصفوفة هي 10 ، لذا فإن الخطوة الأولى في بناء الشجرة هي إنشاء 10 عقدة جذر ، كما هو موضح هنا.
3. مع مجموعة من العقد الجذرية ، ستكون جميع القيم الأخرى تابعة لهذه العقدة. بالإشارة إلى القواعد ، فإن الخطوة الأولى التي يجب اتخاذها لإضافة 7 إلى الشجرة هي مقارنتها بعقدة الجذر.
4. إذا كانت القيمة 7 أقل من 10 ، ستصبح العقدة الفرعية اليسرى.
5. إذا كانت القيمة 7 أكبر من أو تساوي 10 ، فسوف تنتقل إلى اليمين. نظرًا لأنه من المعروف أن الرقم 7 أقل من 10 ، فقد تم تعيينه على أنه العقدة الفرعية اليسرى.
6. إجراء مقارنات بشكل متكرر لكل عنصر.
7. باتباع نفس النمط ، قم بإجراء نفس المقارنة مع القيمة 14 في المصفوفة.
8. مقارنة القيمة 14 بعقدة الجذر 10 ، مع العلم أن 14 هو الطفل الصحيح.
9. المشي عبر المصفوفة ،تعال إلى 20.
10. ابدأ بمقارنة المصفوفة بـ 10 ، أيهما أكبر. انتقل إلى اليمين وقارنه بـ 14 ، فهو أكبر من 14 عامًا وليس لديه أطفال على اليمين.
11. الآن هناك قيمة 1. باتباع نفس النمط مثل القيم الأخرى ، قارن 1 إلى 10 ، والانتقال إلى اليسار والمقارنة بـ 7 وأخيراً مع الطفل الأيسر 1 من العقدة السابعة.
12. إذا كانت القيمة 5 ، قارنها بـ 10. بما أن 5 أقل من 10 ، مرر إلى اليسار وقارنها بـ 7.
13. مع العلم أن 5 أقل من 7 ، استمر في النزول على الشجرة وقارن 5 بقيمة 1.
14. إذا كان الرقم 1 ليس له أطفال و 5 أكبر من 1 ، فإن 5 يكون تابعًا صالحًا لعقدة واحدة.
15. أخيرًا أدخل القيمة 8 في الشجرة.
16. عندما تكون 8 أقل من 10 ، حركها إلى اليسار وقارنها بـ 7 ، 8 أكبر من 7 ، لذا انقلها إلى اليمين وأكمل الشجرة ، مما يجعل 8 طفلًا مناسبًا لـ 7.

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

مشاكل البحث الثنائي المحتملة

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

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

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

أمثلة حساب البحث الثنائي

نحتاج إلى تحديد نوع الشجرة التي ستنتج إذا تم إدراج 25 في شجرة البحث الثنائية التالية:

10

/

/

5 15

/ /

/ /

2 12 20

عند إدخال x في شجرة T لا تحتوي بعد على x ، يتم وضع المفتاح x دائمًا في ورقة جديدة. فيما يتعلق بهذا ، ستبدو الشجرة الجديدة كما يلي:

10

/

/

5 15

/ /

/ /

2 12 20

25

ما نوع الشجرة التي ستحصل عليها إذا أدخلت 7 في شجرة البحث الثنائية التالية؟

10

/

/

5 15

/ /

/ /

2 12 20

الجواب:

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

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