توضيح طريقة اجتياز الأشجار الثنائية الحمراء والأسود وجافا

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

• كل عقدة حمراء أو أسود.
• عقدة الجذر سوداء.
• كل عقدة ورقة نيل أسود.
• إذا كانت العقدة حمراء ، فإن طفليها أسود ؛ (لا يمكن أن يكون هناك عقدان حمراء متتاليان على كل مسار)
• يحتوي المسار من أي عقدة إلى جميع عقد أوراق النسل على نفس عدد العقد السوداء.

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

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

2 العقدة الأصل P للعقدة الجديدة N أسود
لا حاجة لضبط.

3 العقدة الأصل P للعقدة الجديدة n هي حمراء
نظرًا لأن الشجرة الحمراء والأسود لا تسمح بعقدتين حمراء متتاليين (الخاصية 4) ، يجب تعديلها. وفقًا لون عقدة العم لـ N ، يتم تقسيمها إلى حالتين: (نأخذ عقدة الوالدين من N كطفل الأيسر كمثال ، و P كطفل مناسب كوضع مماثل ، لذلك لن أشرح ذلك بالتفصيل)
3.1 عقدة العم u للعقدة الجديدة n هي حمراء. يتم رسم العقدة الأصل P و Uncle U of New Node n على أنها سوداء ، ويتم رسم عقدة الجد G على أنها حمراء ، وذلك لضمان أن عدد العقد السوداء الموجودة على المسار من G إلى كل عقدة فارغة متسقة مع العقد الأصلي. ولكن نظرًا لأننا نحول G إلى أحمر ، إذا كان والد G حمراء أيضًا ، فقد يؤدي ذلك إلى عقدين حمراء متتاليين (انتهاك الطبيعة 4) ، لذلك من الضروري إعادة التحقق مما إذا كان G ينتهك طبيعة الشجرة الحمراء والأسود.

3.2 عقدة العم u للعقدة الجديدة n سوداء. إذا كانت العقدة الجديدة N هي الطفل الأيسر للعقدة الأصل P: ارسم عقدة الأصل P كأسود ، ارسم عقدة Grandfather G كحمر ، ثم تدوير G مباشرةً.

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

2. حذف العملية
تتمثل الطريقة في "مقدمة إلى الخوارزميات" و Wikipedia في حذف عقدة سوداء D "، ودفع" أسود D إلى عقدة طفلها C ، أي أن C لديه طبقة إضافية من اللون الأسود بالإضافة إلى لونها الأسود ، ثم يستمر في تحريك الطبقة الإضافية على طول الشجرة حتى تواجه نودًا أحمر ، وينتقل إلى اللون الأسود لتأكد من أن العدد الأسود في المسار غير المتبقي. بحيث يتم تقليل عدد العقد السوداء على جميع المسارات بواحد ويظل متساويًا. أثناء الحركة الصعودية ، قد تحتاج بعض ألوان العقدة إلى تدوير وتعديل لضمان أن عدد العقد السوداء على المسار يظل دون تغيير.
قد يكون هذا النهج مفيدًا لتنفيذ الكود (الذي يمكن استخدامه بطرق تكرارية) ، لكن ليس من المناسب فهم (الاعتقاد شخصيًا). لغرض فهم الأولوية ، قمت بالتصنيف التالي بناءً على ما إذا كان طفل العقدة المحذوفة D هو NIL:
1 كلا الطفلين الذين تم حذف عقدة D لا شيء
1.1 إذا كانت العقدة المحذوفة D حمراء ، فما عليك سوى استبدال D بـ NIL.

1.2 العقدة المحذوفة D هي سوداء (لنأخذ D كمثال)
1.2.1 كلا أطفال العقدة B ، الذي تم حذف شقيقه D ، لا شيء
تم رسم عقدة الأخ D'S Brother B على أنها عقدة حمراء ووالد P على أنها أسود.

نصف اللون الأحمر والنصف الأسود في الشكل يعني أن العقدة قد تكون حمراء أو سوداء. إذا تحولت P إلى اللون الأحمر ، فإن عدد العقد السوداء على المسار بعد التعديل هو نفسه كما كان قبل الحذف D ؛ إذا تحولت إلى أن P أسود ، فإن حذف D سيؤدي إلى عدد أقل من العقد السوداء على المسار من قبل الحذف ، لذلك تحتاج إلى متابعة ما إذا كان التغيير في عدد العقد السوداء على المسار الذي يمر عبر P يؤثر على خصائص الشجرة الحمراء والأسود.
1.2.2 العقدة Brother B للعقدة D لديها طفل وليس لا شيء
يجب أن يكون الطفل أحمر ، وإلا فإن عدد العقد السوداء على المسار من عقدة الوالدين D إلى كل عقدة ورقة سيختلف (انتهاك 5).
إذا كان هذا الطفل هو الطفل المناسب ، ارسم الطفل المناسب لـ B كأسود ، ارسم B كون أصلي للعقدة الأم P ، ارسم P أسودًا ، ثم قم بتدوير P مع يسار واحد.

إذا كان هذا الطفل هو الطفل الأيسر ، ارسم الطفل الأيسر من B كأسود ، B كما حمراء ، ثم تدور B يمينًا ، سيتم تحويل المشكلة إلى وضع الطفل الأيمن.

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

إذا كان B أسود ، فيجب أن يكون طفلان B حمراء. ارسم العقدة الوالدية P كأسود ، الطفل الأيمن من B كأسود ، ولون B الأصلي مثل العقدة الأم P ، ثم قم بالتدوير P مع اليسار.

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

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

 الطبقة العامة treenode {int val ؛ اليسار treenode. ترينودي الحق Public Treenode (int x) {val = x ؛ }}

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

 حل الفئة العامة {list <integer> result = new ArrayList <integer> () ؛ القائمة العامة <integer> preorderTraversal (treenode root) {dfs (root) ؛ نتيجة العودة } private void dfs (treenode root) {if (root == null) {return ؛ } result.add (root.val) ؛ DFS (ROOT.LEFT) ؛ dfs (root.right) ؛ }}

يتطلب التنفيذ التكراري مكدسًا لتخزين العقدة الصحيحة التي لا يمكن الوصول إليها. الرمز كما يلي:

 حل الفئة العامة {قائمة عامة <integer> preDordTraversal (TreeNode Root) {list <integer> result = new ArrayList <integer> () ؛ if (root == null) {return return ؛ } stack <TreeNode> stack = new stack <TreeNode> () ؛ stack.push (الجذر) ؛ بينما (! stack.isempty ()) {treenode curr = stack.pop () ؛ النتيجة. add (curr.val) ؛ if (curr.right! = null) {stack.push (curr.right) ؛ } if (curr.left! = null) {stack.push (curr.left) ؛ }} نتيجة الإرجاع ؛ }}

2. inorder traversal
ببساطة ، فإن اجتياز الترتيب الأوسط هو الوصول أولاً إلى الطفل الأيسر ، ثم الوصول إلى العقدة الأصل ، وأخيراً الوصول إلى الطفل الأيمن ، أي اجتياز بترتيب اليسار والوالد واليمين.
الرمز العودية أسهل أيضًا ، كما هو موضح أدناه:

 حل الفئة العامة {قائمة عامة <integer> inordertraversal (TreeNode Root) {list <integer> result = new ArrayList <integer> () ؛ Recurse (الجذر ، النتيجة) ؛ نتيجة العودة } private void recurse (treenode root ، list <minger> result) {if (root == null) return ؛ Recurse (root.left ، نتيجة) ؛ النتيجة. add (root.val) ؛ Recurse (root.right ، نتيجة) ؛ }}

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

 حل الفئة العامة {قائمة عامة <integer> inordertraversal (TreeNode Root) {list <integer> result = new ArrayList <integer> () ؛ Stack <TreeNode> stack = new stack <TreeNode> () ؛ TreeNode Curr = Root ؛ بينما (curr! = null ||! stack.isempty ()) {بينما (curr! = null) {stack.push (curr) ؛ curr = curr.left ؛ } curr = stack.pop () ؛ النتيجة. add (curr.val) ؛ curr = curr.right ؛ } نتيجة الإرجاع ؛ }}

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

 حل الفئة العامة {قائمة عامة <integer> postordertraversal (treeNode Root) {list <integer> result = new ArrayList <integer> () ؛ Recurse (الجذر ، النتيجة) ؛ نتيجة العودة } private void recurse (treenode root ، list <minger> result) {if (root == null) return ؛ Recurse (root.left ، نتيجة) ؛ Recurse (root.right ، نتيجة) ؛ النتيجة. add (root.val) ؛ }}

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

 حل الفئة العامة {القائمة العامة <integer> postordertraversal (treeNode root) {list <integer> result = new LinkedList <integer> () ؛ Stack <TreeNode> stack = new stack <TreeNode> () ؛ if (root! = null) stack.push (root) ؛ treenode pre = root ؛ بينما (! stack.isempty ()) {treenode curr = stack.peek () ؛ if (curr.left == pre || curr.right == pre || (curr.left == null && curr.right == null)) {result.add (curr.val) ؛ stack.pop () ؛ pre = curr ؛ } آخر {if (curr.right! = null) stack.push (curr.right) ؛ if (curr.left! = null) stack.push (curr.left) ؛ }} نتيجة الإرجاع ؛ }}

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

 حل الفئة العامة {القائمة العامة <integer> postordertraversal (treeNode root) {list <integer> result = new LinkedList <integer> () ؛ Stack <TreeNode> stack = new stack <TreeNode> () ؛ if (root! = null) stack.push (root) ؛ بينما (! stack.isempty ()) {treenode curr = stack.pop () ؛ النتيجة. add (curr.val) ؛ if (curr.left! = null) stack.push (curr.left) ؛ if (curr.right! = null) stack.push (curr.right) ؛ } collections.reverse (نتيجة) ؛ نتيجة العودة }}

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