الأحمر-الأسود الأشجار
https://stackoverflow.com/questions/20734
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
رأيت الأشجار الثنائية الثنائية البحث ذكر في العديد من الكتب التي قرأتها مؤخرا, ولكن ما زلت في بداية دراستي في علوم الكمبيوتر ، يجب أن تأخذ فئة حقا التعامل مع الخوارزميات وهياكل البيانات بطريقة خطيرة.
لقد تحققت جميع أنحاء نموذجية مصادر (ويكيبيديا ، Google) و معظم أوصاف فائدة تنفيذ (على وجه الخصوص) الأحمر-الأسود الأشجار تؤتي ثمارها كما كثيفة من الصعب أن نفهم.أنا متأكد من شخص مع الخلفية اللازمة ، فإنه يجعل الشعور بالكمال ، ولكن في هذه اللحظة يقرأ مثل اللغة الأجنبية تقريبا.
وذلك ما يجعل الأشجار الثنائية مفيدة في بعض المهام المشتركة تجد نفسك تفعل حين البرمجة ؟ أبعد من ذلك, الأشجار التي تفضل استخدام (يرجى إدراج عينة التنفيذ) و لماذا ؟
المحلول
الأحمر الأسود الأشجار جيدة لخلق متوازن الأشجار.المشكلة الرئيسية مع أشجار البحث الثنائية هو أنه يمكنك جعلها غير متوازن بسهولة جدا.تخيل الأولى عدد 15.ثم جميع الأرقام بعد ذلك على نحو متزايد أقل من 15.سيكون لديك الشجرة التي هي ثقيلة جدا على الجانب الأيسر على الجانب الأيمن.
الأحمر الأسود الأشجار حل ذلك عن طريق إجبار شجرة الخاص بك أن تكون متوازنة كلما إدراج أو حذف.فإنه يحقق هذا من خلال سلسلة من التناوب بين الجد العقد و العقد الأطفال.الخوارزمية هو في الواقع بسيط جدا ، على الرغم من أنها قليلا طويلة.أقترح التقاط CLRS (Cormen, Lieserson, Rivest و شتاين) كتاب "مقدمة إلى الخوارزميات" و القراءة على RB الأشجار.
التنفيذ هو أيضا لا حقا قصيرة جدا حتى أنها ربما لا حقا أفضل أن تدرج هنا.ومع ذلك, الأشجار تستخدم على نطاق واسع عالية الأداء في التطبيقات التي تحتاج إلى الوصول إلى الكثير من البيانات.أنها توفر وسيلة فعالة جدا في إيجاد العقد مع صغيرة نسبيا النفقات العامة من إدراج/حذف.مرة أخرى أقترح أن تبحث في CLRS أن تقرأ على كيفية استخدامها.
في حين BSTs لا يجوز استخدام صراحة - مثال على استخدام الأشجار في عام تقريبا في كل الحديثة RDBMS.وبالمثل ، فإن نظام الملفات الخاص بك هو بالتأكيد يمثل نوع من هيكل الشجرة و الملفات أيضا فهرسة بهذه الطريقة.الأشجار السلطة جوجل.الأشجار السلطة فقط عن كل موقع على شبكة الإنترنت.
نصائح أخرى
أود أن أخاطب فقط السؤال: "ما الذي يجعل الأشجار الثنائية مفيدة في بعض المهام المشتركة تجد نفسك تفعل حين البرمجة؟"
هذا هو موضوع كبير أن العديد من الناس يختلفون في.البعض يقول أن الخوارزميات التي تدرس في CS درجة مثل أشجار البحث الثنائية وإخراج الرسوم البيانية في يوم البرمجة و بالتالي لا صلة لها بالموضوع.ويعترض آخرون ، قائلا أن هذه الخوارزميات وهياكل البيانات هي الأساس لجميع برامجنا ومن الضروري أن يفهم منها ، حتى لو كان لديك أبدا أن أكتب واحدة لنفسك.هذه المرشحات في المحادثات عن جيد المقابلات وممارسات التوظيف.على سبيل المثال ، ستيف Yegge مقالا على إجراء المقابلات في جوجل يتناول هذا السؤال.تذكر هذه المناقشة ؛ شهدت الناس يختلفون.
في الأعمال النموذجية البرمجة قد لا تحتاج إلى إنشاء الأشجار الثنائية أو حتى الأشجار في كثير من الأحيان على الإطلاق.ومع ذلك ، سوف تستخدم العديد من الفئات التي داخليا تعمل باستخدام الأشجار.العديد من صميم تنظيم دروس في كل لغة استخدام الأشجار و التجزئات لتخزين والوصول إلى البيانات.
إذا كنت تشارك في أكثر عالية الأداء المساعي أو الحالات التي تعتبر إلى حد ما خارج القاعدة من أعمال البرمجة, سوف تجد الأشجار أن تكون فورية صديق.كما ملصق آخر قال الأشجار البيانات الأساسية هياكل قواعد البيانات والفهارس من جميع الأنواع.فهي مفيدة في استخراج البيانات والتصور ، الرسومات المتقدمة (2d و 3d), و مجموعة أخرى من المشكلات الحسابية.
لقد استخدمت الأشجار الثنائية في شكل BSP (ثنائي مساحة التقسيم) الأشجار في 3d الرسومات.أنا حاليا أبحث في الأشجار مرة أخرى إلى فرز كميات كبيرة من geocoded البيانات وغيرها من البيانات للحصول على معلومات التصور في فلاش/فليكس التطبيقات.كلما كنت تدفع حدود الأجهزة أو كنت تريد أن تعمل على الأجهزة المنخفضة المواصفات والتفاهم اختيار أفضل خوارزمية يمكن أن تجعل الفرق بين الفشل والنجاح.
أي من الإجابات أذكر ما هو بالضبط BSTs جيدة.
إذا ما كنت تريد القيام به هو مجرد البحث عن طريق القيم ثم hashtable هو أسرع بكثير ، س(1) إدراج بحث (المطفأة أفضل الأحوال).
BST تكون O(log N) بحث حيث N هو عدد العقد في الشجرة ، وتدرج أيضا O(log N).
RB و AVL الأشجار الهامة مثل جواب آخر ذكره بسبب هذه الخاصية ، إذا عادي BST هو خلق مع من أجل القيم ثم سوف تكون شجرة عالية مثل عدد القيم إدراج هذا هو سيء بالنسبة بحث الأداء.
الفرق بين RB و AVL الأشجار في التناوب المطلوبة لإعادة التوازن بعد إدراج أو حذف ، AVL الأشجار O(log N) من أجل إعادة توازن في حين RB الأشجار O(1).مثال على الاستفادة من هذا التعقيد المستمر في حالة حيث كنت قد يكون الحفاظ على استمرار مصدر البيانات إذا كنت بحاجة إلى تتبع التغييرات لفة مرة أخرى سيكون لديك لتتبع O(log N) ممكن يتغير مع شجرة AVL.
لماذا أنت على استعداد لدفع ثمن تكلفة شجرة على تجزئة الجدول ؟ النظام!الجداول التجزئة لا النظام ، BSTs من ناحية أخرى هي دائما أمر طبيعي بحكم بنيتها.حتى إذا كنت تجد نفسك رمي حفنة من البيانات في مجموعة أو حاوية أخرى ثم الفرز في وقت لاحق ، BST قد يكون أفضل حل.
الشجرة من أجل الملكية يوفر لك عددا من أمر التكرار القدرات في النظام, أولا عمق واتساع-أولا قبل النظام ما بعد النظام.هذه التكرار الخوارزميات هي مفيدة في ظروف مختلفة إذا كنت ترغب في البحث عنها.
الأحمر الأسود الأشجار تستخدم داخليا في كل أمر حاوية من اللغة المكتبات, C++ مجموعة الخريطة .صافي SortedDictionary, جافا TreeSet ، الخ...
حتى الأشجار مفيدة جدا, و قد تستخدمها في كثير من الأحيان حتى دون أن يعرفوا ذلك.كنت على الأرجح لن تحتاج أن تكتب بنفسك ، على الرغم من وأود أن أوصي به كما مثيرة للاهتمام البرمجة ممارسة الرياضة.
الأحمر الأسود الأشجار ب-الأشجار تستخدم في جميع أنواع التخزين المستمر;لأن الأشجار متوازنة أداء اتساع وعمق traversals تخفيفها.
ما يقرب من جميع نظم قواعد البيانات استخدام الأشجار لتخزين البيانات.
BSTs يجعل العالم جولة الذهاب ، كما قال مايكل.إذا كنت تبحث عن شجرة جيدة لتنفيذ نلقي نظرة على AVL الأشجار (ويكيبيديا).لديهم موازنة الحالة ، حتى أنها مضمونة O(logn).هذا النوع من البحث من الكفاءة يجعل من المنطقي أن تضع في أي نوع من عملية الفهرسة.الشيء الوحيد الذي سيكون أكثر كفاءة قد يكون وظيفة التجزئة ، ولكن تلك يسوء بسرعة, سريع, في عجلة من امرنا.أيضا ، يمكنك تشغيل في عيد ميلاد مفارقة (المعروف أيضا باسم كوة المشكلة).
ما الكتاب الذي تستخدمه ؟ كنا هياكل البيانات وتحليلها في جافا مارك ألين فايس.أنا في الواقع قد فتح في حضني وأنا أكتب هذا.وقد قسم كبير عن الأحمر والأسود الأشجار ، حتى يشمل البرمجية اللازمة لتنفيذ جميع الأشجار يتحدث عن.
الأحمر-الأسود الأشجار البقاء متوازنا حتى لا تضطر إلى اجتياز عميق للحصول على البنود.الوقت حفظ يجعل RB الأشجار O(log()ن)) في أسوأ الأحوال ، بينما سيئ الحظ الأشجار الثنائية يمكن أن ندخل في لوب من جانب التكوين وتسبب الاسترجاع في O(n) حالة سيئة.هذا لا يحدث في الواقع أو على بيانات عشوائية.حتى إذا كنت بحاجة الى وقت حرج رمز (قاعدة بيانات الاسترجاع ، شبكة الخادم.... الخ) يمكنك استخدام RB الأشجار لدعم أمرت أو غير مرتبة القوائم/مجموعات .
ولكن RBTrees هي ودي!إذا كنت تفعل منظمة العفو الدولية و تحتاج إلى إجراء بحث كنت تجد لك شوكة الدولة المعلومات الكثير.يمكنك استخدام المستمرة الأحمر-الأسود إلى شوكة الدول الجديدة في O(log(n)).استمرار أحمر أسود شجرة يحتفظ بنسخة من الشجرة قبل و بعد العملية المورفولوجية (إدراج/حذف) ، ولكن بدون نسخ الشجرة بأكملها (عادة O(log(n)) العملية).لقد فتح مصدرها المستمر الأحمر-الأسود شجرة جافا
أفضل وصف الأحمر-الأسود الأشجار رأيت في Cormen, Leisersen و Rivest هو مقدمة إلى الخوارزميات'.حتى أستطيع أن أفهم ما فيه الكفاية جزئيا تنفيذ واحدة (الإدراج فقط).هناك أيضا عدد غير قليل من التطبيقات مثل هذا واحد على صفحات الإنترنت المختلفة أن تحريك العملية تسمح لك لمشاهدة خطوة من خلال تمثيل رسومي من خوارزمية بناء بنية شجرة.
بما أنك سألت أي شجرة من الناس ، عليك أن تعرف أن الأحمر الأسود الشجرة هو بشكل أساسي 2-3-4 ب-شجرة (أنا.e a B-شجرة من أجل 4).ب-شجرة لا أي ما يعادل شجرة ثنائية(كما طلب في السؤال).
هناالصورة ممتازة الموارد واصفا الأولي التجريد المعروف متماثل الثنائية ب-الشجرة التي تطورت لاحقا إلى RBTree.سوف تحتاج إلى فهم جيد على ب-الأشجار قبل أن يجعل الشعور.لتلخيص:a 'الأحمر' رابط على أحمر أسود الشجرة هي وسيلة لتمثيل العقد التي هي جزء من شجرة B عقدة (القيم ضمن مجموعة رئيسية) ، في حين أن "الأسود" الروابط هي العقد التي ترتبط عموديا في B-شجرة.
حتى هنا هو ما تحصل عليه عند ترجمة قواعد الأحمر الأسود شجرة في شروط ب-شجرة (أنا باستخدام تنسيق الأحمر الأسود شجرة القاعدة => ب شجرة ما يعادلها):
1) عقدة إما أحمر أو أسود.=> عقدة في شجرة b يمكن أن يكون إما جزءا من عقدة أو عقدة في مستوى جديد.
2) الجذر الأسود.(هذه القاعدة هو حذف بعض الأحيان ، لأنه لا يؤثر على التحليل) => عقدة الجذر يمكن أن تكون إما كجزء من داخلي عقدة الجذر وهو طفل وهمي عقدة الأم.
3) جميع الأوراق (النيل) سوداء.(جميع الأوراق بنفس لون الجذر.) => لأن طريقة واحدة تمثل RB الشجرة عن طريق حذف الأوراق ، يمكننا استبعاد هذا.
4)كل من الأطفال من كل أحمر عقدة سوداء.=> أطفال داخلي عقدة في شجرة B تكمن دائما في مستوى آخر.
5)كل مسار بسيط من عقدة معينة إلى أي من نسل أوراق تحتوي على نفس العدد من الأسود العقد.=> B-شجرة تبقى متوازنة كما أنه يتطلب أن جميع أوراق العقد على نفس العمق (وبالتالي ارتفاع شجرة B عقدة يمثله عدد من الأسود الروابط من الجذر إلى الورقة الحمراء شجرة سوداء)
أيضا هناك أبسط "غير قياسي" تنفيذ روبرت Sedgewick هنا:(هو مؤلف الكتاب خوارزميات جنبا إلى جنب مع واين)
الكثير و الكثير من الحرارة هنا ولكن ليس الكثير من الضوء ، لذلك دعونا نرى ما اذا كنا نستطيع تقديم بعض.
أولا, ، RB شجرة النقابي بنية البيانات ، على النقيض من مجموعة التي لا تأخذ مفتاح والعودة بها القيمة ، حسنا ، إلا إذا كان ذلك صحيحا "مفتاح" في 0% متفرق مؤشر متجاورة الاعداد الصحيحه.مجموعة لا يمكن أن تنمو في الحجم إما (نعم, أنا أعرف عن realloc() أيضا ولكن تحت الأغطية التي تتطلب مجموعة جديدة ثم memcpy ()) ، لذلك إذا كان لديك أي من هذه المتطلبات ، صفيف لن تفعل.مجموعة الذاكرة كفاءة مثالية.صفر نفايات ، ولكن ليست ذكية جدا ، أو مرنة - realloc() لا تحمل.
الثاني, في مقابل bsearch() على مجموعة من العناصر ، وهو النقابي البيانات هيكل ، RB يمكن أن تنمو شجرة (وتقليص) نفسها في الحجم بشكل حيوي.على bsearch() يعمل بشكل جيد الفهرسة بنية البيانات من حجم المعروف الذي سيبقى هذا الحجم.حتى إذا كنت لا تعرف حجم البيانات الخاصة بك في وقت مبكر ، أو عناصر جديدة تحتاج إلى إضافة ، أو حذف ، bsearch() هو.Bsearch() و qsort() كلاهما مدعومة جيدا في الكلاسيكية ج ، لديها ذاكرة جيدة الكفاءة ، ولكن ليست ديناميكية كافية للعديد من التطبيقات.وهي الشخصية المفضلة على الرغم لأنهم سريعة وسهلة إذا كنت لا تتعامل مع الوقت الحقيقي تطبيقات في كثير من الأحيان هي مرنة بما فيه الكفاية.وبالإضافة إلى ذلك, في C/C++ يمكنك فرز مجموعة من المؤشرات إلى سجلات البيانات ، لافتا إلى هيكل{} عضو ، على سبيل المثال ، كنت ترغب في مقارنة ، ثم إعادة ترتيب المؤشر في مجموعة المؤشر مثل أن قراءة المؤشرات في الترتيب في نهاية المؤشر نوعا ما ينتج البيانات الخاصة بك في ترتيب فرزها.باستخدام هذا مع الذاكرة المعنونة ملفات البيانات للغاية كفاءة الذاكرة السريعة و سهلة إلى حد ما.كل ما عليك القيام به هو إضافة بضع "*"s الخاص بك وظيفة مقارنة/s.
الثالث, في المقابل hashtable ، والتي يجب أيضا أن يكون حجم ثابت و لا يمكن أن تزرع مرة واحدة يتم ملء RB شجرة التلقائى تنمو نفسها والتوازن نفسها للحفاظ على O(log(n)) ضمان الأداء.خاصة إذا كان RB شجرة الرئيسية هو الباحث ، فإنه يمكن أن يكون أسرع من تجزئة ، لأنه على الرغم من hashtable تعقيد O(1) ، 1 يمكن أن تكون مكلفة جدا تجزئة الحساب.شجرة متعددة 1-الساعة صحيح يقارن غالبا ما يتفوق 100 على مدار الساعة+ تجزئة العمليات الحسابية ، ناهيك عن التطرق لذلك ، malloc()ing مساحة التجزئة التصادم و يعيد قولبة.أخيرا, إذا كنت تريد عصام الوصول ، وكذلك مفتاح الوصول إلى البيانات الخاصة بك ، تجزئة يحكم بها ، كما أن هناك عدم ترتيب البيانات الكامنة في hashtable ، على النقيض من الطبيعي ترتيب البيانات في أي شجرة التنفيذ.الكلاسيكية استخدام جدول تجزئة هو توفير مرتبطا الوصول إلى جدول من الكلمات المحجوزة على مترجم.إنها الذاكرة كفاءة ممتازة.
الرابع, و منخفضة جدا على أي قائمة ، هو مرتبط ، أو مرتبطة على نحو مضاعف القائمة على النقيض من صفيف ، بطبيعة الحال يدعم عنصر الإدراج والحذف ، كما أنه يعني تغيير حجم.إنه أبطأ من جميع هياكل البيانات ، حيث أن كل عنصر يعرف فقط كيفية الوصول إلى العنصر التالي ، لذلك عليك أن البحث في المتوسط (element_knt/2) وصلات إلى العثور على مسند.انها تستخدم في الغالب من حيث الإدراج والحذف في مكان ما في منتصف القائمة المشتركة ، خصوصا ، حيث قائمة دائرية يغذي عملية مكلفة مما يجعل الوقت لقراءة روابط صغيرة نسبيا.اللواء RX هو أن تستخدم بشكل تعسفي مجموعة كبيرة بدلا من قائمة مرتبطة إذا كان الشرط الوحيد هو أن تكون قادرة على زيادة في الحجم.إذا كنت قد نفد من حجم مجموعة ، يمكنك realloc() أكبر مجموعة.المحكمة الخاصة بلبنان يعني هذا بالنسبة لك "تحت الأغطية" عند استخدام ناقلات.الخام ، ولكن يحتمل أن تكون 1,000 s من مرات أسرع إذا كنت لا تحتاج إلى الإدراج أو الحذف أو مرتبطا عمليات البحث.إنها الذاكرة كفاءة الفقراء ، وخاصة بالنسبة مضاعف-القوائم المرتبطة.في الواقع مرتبطة على نحو مضاعف قائمة تتطلب اثنين من المؤشرات ، هو بالضبط مثل الذاكرة غير فعالة الأحمر-الأسود شجرة في حين وجود أي من جاذبية سريع ، طلب استرجاع الخصائص.
الخامسة, والأشجار دعم العديد من عمليات إضافية على فرز البيانات من أي دولة أخرى بنية البيانات.على سبيل المثال, العديد من استعلامات قاعدة البيانات الاستفادة من حقيقة أن مجموعة من أوراق القيم يمكن بسهولة تحديد طريق تحديد المشتركة الوالدين ، ثم تركز المعالجة اللاحقة على جزء من شجرة الأم "يملك".إمكانيات متعددة خيوط المعالجة التي يقدمها هذا النهج ينبغي أن يكون واضحا ، فقط منطقة صغيرة من شجرة يحتاج إلى أن يكون مؤمنا - وهي فقط العقد الوالد يملك و الأم نفسها.
باختصار, الأشجار كاديلاك من هياكل البيانات.دفع ثمنا باهظا من حيث الذاكرة المستخدمة, ولكن يمكنك الحصول على الذاتي تماما الحفاظ على بنية البيانات.هذا هو السبب ، كما أشار في ردود أخرى هنا ، قواعد بيانات المعاملة استخدام الأشجار على وجه الحصر تقريبا.
إذا كنت تود أن ترى كيف الأحمر-الأسود شجرة من المفترض أن تبدو بيانيا ، لقد مشفرة تنفيذ الأحمر-الأسود الشجرة التي يمكنك تحميل هنا
IME تقريبا لا أحد يفهم RB خوارزمية شجرة.الناس يمكن تكرار القواعد إليك, لكنهم لا يفهمون لماذا تلك القواعد حيث أنها تأتي من.أنا لست استثناء :-)
لهذا السبب أنا أفضل AVL الخوارزمية ، لأنه من السهل أن فهم.مرة واحدة عليك أن تدرك ذلك ، يمكنك ثم رمز من الصفر ، لأنه معنى لك.
الأشجار يمكن أن تكون سريعة.إذا كان لديك مليون العقد بطريقة متوازنة شجرة ثنائية ، فإنه يأخذ عشرين مقارنات في المتوسط إلى العثور على أي عنصر واحد.إذا كان لديك مليون عقد في قائمة مرتبطة ، يستغرق خمس مائة آلاف مقارنات في المتوسط إلى العثور على نفس البند.
إذا كانت الشجرة غير متوازن ، على الرغم من أنه يمكن أن يكون مجرد بطيئة مثل القائمة ، و أيضا أن تأخذ المزيد من الذاكرة لتخزين.تخيل شجرة فيها معظم العقد حق الطفل ، ولكن لا تترك الطفل ؛ ذلك هو قائمة, ولكن لا يزال لديك لعقد مساحة الذاكرة وضعه في ترك العقدة إذا كان أحد يظهر.
على أي حال ، شجرة AVL كان أول ثنائية متوازنة خوارزمية شجرة ، مقالة ويكيبيديا على أنها واضحة جدا.مقالة ويكيبيديا عن الأحمر والأسود الأشجار واضح الطين بصراحه....
وراء الأشجار الثنائية ، ب-الأشجار هي الأشجار حيث كل عقدة يمكن أن يكون العديد من القيم.ب-شجرة لا شجرة ثنائية ، يحدث لمجرد أن يكون اسم منه.انهم حقا مفيدة لاستخدام الذاكرة كفاءة ؛ كل عقدة في شجرة يمكن أن يكون الحجم لتناسب في كتلة واحدة من الذاكرة ، حتى أن كنت لا (ببطء) الذهاب العثور على طن من مختلف الأشياء في الذاكرة التي تم ترحيلها إلى القرص.وهنا الهائل مثال ب-شجرة.
