ما المقصود بشجرة البحث الثنائية ذاتي التوازن؟ - تعريف من techopedia

التعريف - ماذا تعني شجرة البحث الثنائي ذاتي التوازن؟

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

تُعرف شجرة البحث الثنائية ذاتي التوازن أيضًا باسم شجرة البحث الثنائية أو شجرة البحث الثنائية المتوازنة مع الارتفاع.

يوضح Techopedia شجرة البحث الثنائي ذاتي التوازن

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

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

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