الفرق بين LinkedList وشجرة البحث الثنائية

Question

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

Answer 1

القائمة المرتبطة:

Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7)

شجرة ثنائية:

                 Node(1)
                /
            Node(2)
           /    \
          /      Node(3)
  RootNode(4)
          \      Node(5)
           \    /
            Node(6)
                \
                 Node(7)

في القائمة المرتبطة، يتم ربط العناصر معًا من خلال مؤشر تالي واحد.في الشجرة الثنائية، يمكن أن تحتوي كل عقدة على 0 أو 1 أو 2 عقد فرعية، حيث (في حالة شجرة البحث الثنائية) يكون مفتاح العقدة اليسرى أقل من مفتاح العقدة ومفتاح العقدة اليمنى أكبر من العقدة.وطالما أن الشجرة متوازنة، يكون مسار البحث لكل عنصر أقصر بكثير من ذلك الموجود في القائمة المرتبطة.

مسارات البحث:

------ ------ ------
key    List   Tree
------ ------ ------
1      1      3
2      2      2
3      3      3
4      4      1
5      5      3
6      6      2
7      7      3
------ ------ ------
avg    4      2.43
------ ------ ------

من خلال الهياكل الأكبر، يصبح متوسط ​​مسار البحث أصغر بكثير:

------ ------ ------
items  List   Tree
------ ------ ------
     1      1   1
     3      2   1.67
     7      4   2.43
    15      8   3.29
    31     16   4.16
    63     32   5.09
------ ------ ------

Answer 2

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

الآن أ قائمة مرتبطة يتكون من سلسلة من العقد، تحتوي كل منها على قيم عشوائية ومرجع واحد أو اثنين يشيران إلى العقد التالية و/أو السابقة.

Answer 3

في علوم الكمبيوتر، أ شجرة البحث الثنائية (BST) عبارة عن بنية بيانات شجرة ثنائية لها الخصائص التالية:

• كل عقدة (عنصر في الشجرة) لها قيمة مميزة؛
• يجب أن تكون كل من الشجرتين الفرعيتين اليمنى واليسرى أيضًا عبارة عن شجرتين للبحث؛
• تحتوي الشجرة الفرعية اليسرى للعقدة على قيم أقل من قيمة العقدة فقط؛
• تحتوي الشجرة الفرعية اليمنى للعقدة على قيم أكبر من أو تساوي قيمة العقدة فقط.

في علوم الكمبيوتر، أ قائمة مرتبطة هي إحدى هياكل البيانات الأساسية، ويمكن استخدامها لتنفيذ هياكل البيانات الأخرى.

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

Answer 4

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

وعلى الفور يمكنك بعض المقايضات: القوائم المرتبطة الحفاظ على النظام الإدراج وادخال أقل تكلفة أشجار البحث الثنائية عادة ما تكون أسرع للبحث

Answer 5

وهناك قائمة مرتبطة هو رقم تسلسلي من "العقد" مرتبطة بعضها البعض، أي:

public class LinkedListNode
{
     Object Data;
     LinkedListNode NextNode;
}

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

public class BSTNode
{
    Object Data
    BSTNode LeftNode;
    BSTNode RightNode;
} 

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

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

وبسبب هذا، وقائمة متصلة هو O (N) بنية بيانات اجتياز، في حين أن BST هو O (N) بنية بيانات اجتياز في أسوأ الحالات، وO (تسجيل N) في أفضل الأحوال.

Answer 6

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

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

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

Answer 7

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

و1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. (وهذا الأخير هو محاولة أسكي الفن في لاغية تنتهي)

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

    5
   / \
  3   9
 / \   \
1   2   12

و9 لا يوجد لديه طفل الأيسر، و 1 و 2 و 12 هي "أوراق" - ليس لديهم فروع

.

تأكد معنى؟

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

Answer 8

وهذه المسألة مع قائمة مرتبطة بالبحث داخلها (سواء للاسترجاع أو إدراج).

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

وهناك شجرة ثنائية تسمح للبحث أكثر سرعة والإدراج التي يجري فرز بطبيعتها وللملاحة.

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

Answer 9

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

ويمكن أن تكون هذه العلاقات ثنائية الاتجاه أو أحادي الاتجاه، اعتمادا على كيفية تحتاج إلى أن تكون قادرة على اجتياز هيكل.

Answer 10

هناك أوجه تشابه بينهما، ولكن الاختلاف الرئيسي هو أن شجرة البحث الثنائية مصممة لدعم البحث الفعال عن عنصر أو "مفتاح".

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

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

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

Answer 11

وقائمة مرتبط هي بيانات متتالية الخطية مع العقد المجاورة على اتصال مع بعضها البعض على سبيل المثال A-> B-> C. يمكنك أن تنظر فيه بوصفه سياج على التوالي.

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

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

Answer 12

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

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

وهناك شجرة البحث الثنائية هي شجرة الذي يقسم تصل مساهمتها إلى نصفين تقريبا متساوية على أساس ثنائي خوارزمية مقارنة البحث. وهكذا، فإنه يحتاج فقط لعدد قليل جدا من عمليات البحث للعثور على عنصر. على سبيل المثال، إذا كان لديك شجرة مع 1-10 وكنت في حاجة للبحث عن ثلاثة، أولا العنصر في الجزء العلوي سيتم فحص، وربما سيكون 5 أو 6. ثلاثة يكون أقل من ذلك، وذلك فقط في النصف الأول من بعد ذلك يتم فحص شجرة. إذا كانت القيمة التالية هي 3، لديك، وإلا، ويتم مقارنة وغيرها، حتى إما لم يتم العثور عليه أو يتم إرجاع البيانات الخاصة به. وهكذا فإن شجرة سريعة للبحث، ولكن ليس nessecarily بسرعة لالإدراج أو الحذف. هذه هي الأوصاف صعبة للغاية.

قائمة مرتبط من ويكيبيديا، و <لأ href = "HTTP: // داخلي. wikipedia.org/wiki/Binary_Search_Tree "يختلط =" نوفولو noreferrer "> ثنائي البحث شجرة ، وأيضا من ويكيبيديا.

Answer 13

وهم بنيات بيانات مختلفة تماما.

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

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