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

Question

ما هي مزايا أشجار البحث الثنائية على تجزئة الجداول ؟

الجداول التجزئة يمكن البحث عن أي عنصر في ثيتا(1) هو مجرد سهلا لإضافة عنصر....ولكن لست متأكدا من المزايا سوف العكس.

Answer 1

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

على سبيل المثال ، إذا كانت وظيفة التجزئة لها نطاق R(h) = 0...100, ، فأنت بحاجة إلى تخصيص مجموعة من 100 عنصر (مؤشرات إلى) ، حتى لو كنت مجرد 20 عنصرًا. إذا كنت ستستخدم شجرة بحث ثنائية لتخزين نفس المعلومات ، فلن تخصص سوى مساحة أكبر من الحاجة ، وكذلك بعض البيانات الوصفية حول الروابط.

Answer 2

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

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

بينما ، كيف يمكنك إجراء عمليات البحث في نطاق التجزئة؟ تحتاج إما إلى تكرار كل مساحة دلو ، وهي O (n) ، أو عليك البحث عن ما إذا كان كل من 1،2،3،4 ... موجود حتى 5000. (ماذا عن المفاتيح بين 0 و 5000 هي مجموعة لا حصر لها؟ على سبيل المثال يمكن أن تكون المفاتيح عشرية)

Answer 3

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

Answer 4

بالإضافة إلى جميع تعليقات جيدة:

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

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

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

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

Answer 5

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

• ابحث عن العنصر الأقرب إلى (لا يساوي بالضرورة) بعض القيمة الرئيسية التعسفية (أو الأقرب أعلاه/أدناه)

• تكرار من خلال محتويات الشجرة بترتيب فرز

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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

إن التكرار من خلال إدخالات جدول التجزئة لا معنى له لأنها جميعها منتشرة في الذاكرة.

Answer 10

توفر BSTS أيضًا عمليات "FindPredeCessor" و "FindSuccessor" (للعثور على أصغر العناصر التالية والقادمة) في وقت O (logn) ، والتي قد تكون أيضًا عمليات مفيدة للغاية. لا يمكن أن يوفر جدول التجزئة في تلك الكفاءة في الوقت.

Answer 11

من تكسير مقابلة الترميز ، الطبعة السادسة

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

Answer 12

إذا كنت ترغب في الوصول إلى البيانات بطريقة مرتبة ، فيجب الحفاظ على قائمة مرتبة بالتوازي مع جدول التجزئة. مثال جيد هو القاموس في .NET. (نرى http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx).

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

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

Answer 13

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

مع جدول التجزئة ، يمكنك تحديد موقع أي عنصر في وقت ثابت.

إذا كنت ترغب في العثور على قيم النطاق أكبر من E41 وأقل من E8 ، فيمكن لـ BST أن تجد ذلك بسرعة.

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

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

Answer 14

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

1. مضاعفة كل دلاء حجم- malloc (دلاء n)/تغيير وظيفة التجزئة المطلوبة: يعتمد على تنفيذ malloc
2. نقل/نسخ كل من بيانات الجرافات السابقة إلى بيانات الدلاء الجديدة. هذه عملية o (n) حيث تمثل n البيانات بأكملها

نعم. ولكن إذا استخدمت قائمة LinkedList ، فلا ينبغي أن تكون هناك مشكلة في ذلك صحيح؟ نعم ، في القوائم المرتبطة ليس لديك هذه المشكلة. بالنظر إلى كل دلو لتبدأ بقائمة مرتبطة ، وإذا كان لديك 100 عنصر في دلو ، فإنك تتطلب منك اجتياز هذه العناصر المائة للوصول إلى نهاية قائمة LinkedList ومن هنا ستستغرق القائمة (العنصر E) بعض الوقت إلى-

1. تجزئة العنصر إلى دلو عادي كما في جميع التطبيقات
2. خذ وقتًا للعثور على العنصر الأخير في عملية الجرافة المذكورة.

تتمثل ميزة تطبيق LinkedList في أنك لا تحتاج إلى عملية تخصيص الذاكرة ونقل/نسخة من جميع الدلاء كما في حالة تطبيق العنوان المفتوح.

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

Answer 15

جداول التجزئة ليست جيدة للفهرسة. عندما تبحث عن مجموعة ، فإن BSTs أفضل. هذا هو السبب في أن معظم فهارس قاعدة البيانات تستخدم أشجار B+ بدلاً من جداول التجزئة

Answer 16

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

نظرًا لأن BST يحتفظ بمعلومات الطلب ، فإنه يوفر لك أربع عمليات ديناميكية إضافية لا يمكن تنفيذها (بكفاءة) باستخدام جداول التجزئة. هذه العمليات هي:

1. أقصى
2. الحد الأدنى
3. خليفة
4. السلف

كل هذه العمليات مثل كل عملية BST لها تعقيد زمني لـ O (H). بالإضافة إلى ذلك ، تظل جميع المفاتيح المخزنة في BST مما يتيح لك الحصول على تسلسل مفاتيح مصنّعة فقط عن طريق اجتياز الشجرة بالترتيب.

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

Answer 17

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

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

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

Answer 18

الميزة الرئيسية لجدول التجزئة هي أنه يقوم تقريبًا بجميع العمليات في ~ = O (1). ومن السهل جدًا الفهم والتنفيذ. إنه يحل العديد من "مشاكل المقابلة" بكفاءة. لذلك إذا كنت ترغب في كسر مقابلة ترميز ، تكوين أفضل صداقات مع جدول التجزئة ؛-)